Question: m_recip.c / reciprocalTable[..]

[sttng]

Apologies, if this is off-topic, so please close the issue if it is... Anyway, I am trying to figure out but failing to understand the method used to create the entries of reciprocalTable[65537] in m_recip.c ?

Why does it have 65537 entries ? How / where do these entries come from (following which mathematical formula) ? Is there any explanation for this possible ? Many thanks.

[doomhack]

Hi,

The reciprocal table allows us to compute fixed point (16.16) reciprocals. Ie 1/x.

We have 65537 entries so that we can do a full accuracy 1/x divide for any x 0..1. 1 in fixed point is 65536 (1 << 16) so we need 65537 entries because the array is zero indexed.

The first entry is 0 and is returned for a divde by 0. So 1/0 = 0.

I computed the table in excel and then copy/pasted into a source file.

The formula is just

0 2^32 (4294967296) / 1 2^32 / 2 2^32 / 3 2^32 / 4 etc.

[doomhack]

With this table we can compute exact reciprocals in the range 0..1.

We can also use this table for any reciprocal by shifting the value down so it fits into 16bits then shifting back up again.

There is a loss of precision but in practice it works well enough.

So to compute the reciprocal of say 0.63:

0.63 in 16.16 fixed point is 41288. reciprocalTable[41288] = 104025 104025 in 16.16 = 1.59 1/0.63 = 1.59.

To compute the reciprocal of 2.9:

2.9 in 16.16 fixed point is 190054. This is too big for our reciprocal table. So we shift right by 2. 190054 >> 2 = 47513 reciprocalTable[47513] = 90396 Now we shift right by 2 to cancel the right shift we did earlier. 90396 >> 2 = 22599 22599 in 16.16 = 0.34 1/2.9 = 0.34.

[doomhack]

So now we can do arbitary reciprocals, we can also use this to do approx division as x/y == x*1/y.

Lets do 26.9 / 14.7.

We can do this as 26.7 * 1/14.7

As before, compute the reciprocal of 14.7.

14.7 in 16.16 fixed point is 963379. This is too big for our reciprocal table. So we shift right by 4. 963379 >> 4 = 60211 reciprocalTable[60211] = 71332 Now we shift right by 4 to cancel the right shift we did earlier. 71332 >> 4 = 4458 4458 in 16.16 = 0.07

So. Now we can compute 26.7 * 0.07 = 1.82.

26.9 / 14.7 = 1.83. We lost a bit of accuracy but it's much faster than doing a real divide.

[sttng]

Thank you so much for the great explanation and insight. This is genius !