Take the 2-minute tour ×

Is it possible to make a reciprocal of float division in form of look up table (such like 1/f -> 1*inv[f] ) ? How it could be done? I think some and mask and shift should be appled to float to make it a form of index? How would be it exectly?

share|improve this question
Are you looking for hackery like this? –  user529758 Sep 1 '12 at 10:55
Do you realize that this either loses a lot of accuracy, or results in a friggin' huge lookup table? There are a lot of floats, even if you restrict yourself to a range like [0.0, 1.0). –  delnan Sep 1 '12 at 10:58
@up I need only reciprocal - say 10 bits of accuracy (1024 floats in look_up table) - I wander if it would be faster or slower –  grunge fightr Sep 1 '12 at 11:04
@H2CO3 no, I need it for division not for inverted square root –  grunge fightr Sep 1 '12 at 11:07
@grungefightr (facepalm truncated) I know, I meant do you want to implement fast division using bit-level manipulation or you specifically want to use lookup tables? –  user529758 Sep 1 '12 at 11:33

3 Answers 3

up vote 6 down vote accepted

You can guess an approximate inverse like this:

int x = reinterpret_cast<int>(f);
x = 0x7EEEEEEE - x;
float inv = reinterpret_cast<float>(x);

In my tests, 0x7EF19D07 was slightly better (tested with the effects of 2 Newton-Raphson refinements included).

Which you can then improve with Newton-Raphson:

inv = inv * (2 - inv * f);

Iterate as often as you want. 2 or 3 iterations give nice results.

Better Initial Approximations

To minimize the relative error:

  • 0x7EF311C2 (without refinement)
  • 0x7EF311C3 (1 refinement)
  • 0x7EF312AC (2 refinements)
  • 0x7EEEEBB3 (3 refinements)

To minimize the absolute error for inputs between 1 and 2 (they work well enough outside that range, but they may not be the best):

  • 0x7EF504F3 (without refinement)
  • 0x7EF40D2F (1 refinement)
  • 0x7EF39252 (2 refinements)

For three refinement steps, the initial approximation barely affects the maximum relative error. 0x7EEEEEEE works great, and I couldn't find anything better.

share|improve this answer
:? Does it really work ? such simple thing? I will test it ... –  grunge fightr Sep 1 '12 at 16:40
@grungefightr works on my pc ;) But, more seriously, it works by negating the exponent, and the thing it does with the mantissa (or significant) I don't really understand.. but it works out alright somehow. –  harold Sep 1 '12 at 17:11
Well It works. It is funny, dl.dropbox.com/u/42887985/reciprocal_div.jpg <- (pic is ugly but funny and not so big distortion to walls) here I changed division by yrs recpirocal_div, in function that counts distance to walls (without Newt-rpahson ) It works very well, much tnx for this –  grunge fightr Sep 1 '12 at 17:43
could you please attach a complete working example for that cast ? Aren't you supposed to use pointers with a reinterpret_cast ? –  user2485710 Jul 27 '13 at 4:25
@user2485710 *reinterpret_cast<int*>(&f) then? –  harold Jul 27 '13 at 8:43

One method is:

  1. Extract the sign, exponent and mantissa from the input
  2. Use some of the most significant mantissa bits to look up its reciprocal in a table
  3. Negate the exponent, and adjust for the change of scale of the mantissa
  4. Recombine the sign, exponent and mantissa to form the output

In step 2, you'll need to choose the number of bits to use, trading between accuracy and table size. You could obtain more accuracy by using the less significant bits to interpolate between table entries.

In step 3, the adjustment is necessary because the input mantissa was in the range (0.5, 1.0], and so its reciprocal is in the range [1.0, 2.0), which needs renormalising to give the output mantissa.

I won't try to write the code for this, since there are probably some slightly fiddly edge cases that I'd miss.

You should also investigate methods involving numerical calculations, which might give better results if memory access is slow; on a modern PC architecture, a cache miss might be as expensive as dozens of arithmetic operations. Wikipedia looks like a good starting point. And of course, whatever you do, measure it to make sure it is actually faster than an FPU division operation.

share|improve this answer
You know I think I only need to MAP some binary part of float (which contains most significant bits) and use such bits (say ten) to use it as an index in look up table - no need of ordered index, converting and calculating - I know i shoul look up in float format spec : > –  grunge fightr Sep 1 '12 at 11:53
@grungefightr: Yes, that's what stage 2 does, but you also need to calculate the new exponent. –  Mike Seymour Sep 1 '12 at 11:55
damn exponent, it takes bits, ye - forgot about that :( –  grunge fightr Sep 1 '12 at 12:01
will rethink it (and accept the answer l8er then if no one gives maybe some bit of useful code example in meantime) :/ At least I could try to use it in specific division cases where I know range of the floats I subdivide by...:/ Will try it –  grunge fightr Sep 1 '12 at 12:09

If your minimum step is something like 0.01 then you can support inverse-f from a table. Each index is multiplied by 100 so you can have


10000 elements for a range of (0.00,100.00)

If you want better precision, you will need more ram.

Another example:

range................: 0.000 - 1000.000
minimum increments ..: 0.001
total element number.: 1 million

something like this: table[2343]=1.0/2.343

Another example:

range................: 0.000000 - 1.000000
minimum increments ..: 0.000001
total element number.: 1 million

something like this: table[999999]=1.0/0.999999
share|improve this answer
It is somewhat helpfull but I do not want to translate floats to integers I need a look-up table indexed by somewhat shifted and masked float –  grunge fightr Sep 1 '12 at 11:11
You are right, shifting could be faster than multiplication. But you cant use a float for indexing of primitives –  huseyin tugrul buyukisik Sep 1 '12 at 11:12

Your Answer


