Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reciprocal Approximation with 1 Subtraction

news.ycombinator.com

Post reply on HN
Print view View original

1–10 of 73 posts

Reciprocal Approximation with 1 Subtraction

#1

Post by mbitsnbites »

Today's find: You can get a floating-point approximation of 1/x that's accurate to 3 bits with a single integer subtraction instruction.

  float fast_reciprocal(float x)
  {
    unsigned i = *(unsigned *) &x; 
    i = 0x7effffffU - i;
    return *(float *) &i;
  }
The magic number 0x7effffff accomplishes two things:

1) The exponent is calculated as 253-e, which effectively negates the exponent and subtracts 1.

2) The mantissa is approximated as a 1st order polynomial in the interval [1, 2).

Interesting, but perhaps not very useful (as most CPU:s have more accurate reciprocal approximations these days).

Re: Reciprocal Approximation with 1 Subtraction

#3

Post by mbitsnbites »

magicalhippo wrote: post #2

Similar trick to that used in the fast inverse square root routine[1] popularized by Quake 3. [1]: https://en.wikipedia.org/wiki/Fast_inverse_square_root

Yep. Along the same lines. This one is even simpler, though, as it requires only a single integer CPU instruction (and the simplest of all instructions too).

If you want full precision, you need to do three Newton-Raphson iterations after the initial approximation. One iteration is:

    y = y * (2.0F - x * y);

Re: Reciprocal Approximation with 1 Subtraction

#4

Post by magicalhippo »

mbitsnbites wrote: post #3
magicalhippo wrote: post #2

Similar trick to that used in the fast inverse square root routine[1] popularized by Quake 3. [1]: https://en.wikipedia.org/wiki/Fast_inverse_square_root

Yep. Along the same lines. This one is even simpler, though, as it requires only a single integer CPU instruction (and the simplest of all instructions too). If you want full precision, you need to do three Newton-Raphson iterations after the initial approximation. One iteration is: y = y * (2.0F - x * y);

It's a neat trick, and could be very useful on microcontrollers which doesn't have hardware division but does have hardware multiplication.

Re: Reciprocal Approximation with 1 Subtraction

#5

Post by actionfromafar »

magicalhippo wrote: post #4
mbitsnbites wrote: post #3

Earlier quoted context omitted.

Yep. Along the same lines. This one is even simpler, though, as it requires only a single integer CPU instruction (and the simplest of all instructions too). If you want full precision, you need to do three Newton-Raphson iterations after the initial approximation. One iteration is: y = y * (2.0F - x * y);

It's a neat trick, and could be very useful on microcontrollers which doesn't have hardware division but does have hardware multiplication.

Hm, like 68000?

Re: Reciprocal Approximation with 1 Subtraction

#6

Post by fph »

magicalhippo wrote: post #2

Similar trick to that used in the fast inverse square root routine[1] popularized by Quake 3. [1]: https://en.wikipedia.org/wiki/Fast_inverse_square_root

For some more explanation: the main idea behind both tricks is that the IEEE floating point formats are designed so that the most significant bits represent its exponent, that is, floor(log2(x)). Hence reinterpret-casting a float x to an unsigned integer uint(x) approximates a multiple of log2(x). So these kinds of approximations work like logarithm arithmetic: float(C + a*uint(x)) approximates x^a, for a suitable constant C. Quake's invsqrt is a=-1/2, this post is a=-1.

More detail on https://en.wikipedia.org/wiki/Fast_inverse_square_root#Alias... .

IEEE754 floats are a very well-designed binary format, and the fact that these approximations are possible is part of this design; indeed, the first known instance of this trick is for a=1/2 by W. Kahan, the main designer of IEE754.

Re: Reciprocal Approximation with 1 Subtraction

#7

Post by torusle »

There are couple of tricks you can do if you fiddle with the bits of a floating point value using integer arithmetic and binary logic.

That was a thing back in the 90th..

I wonder how hard the performance hit from moving values between integer and float pipeline is nowadays.

Last time I looked into that was the Cortex-A8 (first I-Phone area). Doing that kind of trick costed around 26 cycles (back and forth) due to pipeline stalls back then.

Re: Reciprocal Approximation with 1 Subtraction

#8

Post by Y_Y »

Quick comparison with exact and one Newton-Raphson:

  Value | True | Fast | Fast+Newton
  ----------------------------------------
   0.1 | 10.000 | 11.200 | 9.8560
   0.5 | 2.0000 | 2.0000 | 2.0000
   1.0 | 1.0000 | 1.0000 | 1.0000
   2.0 | 0.5000 | 0.5000 | 0.5000
   5.0 | 0.2000 | 0.2187 | 0.1982
  10.0 | 0.1000 | 0.1094 | 0.0991
(where the extra correction was done with:

  y *= (2.0f - x*y);
)

Re: Reciprocal Approximation with 1 Subtraction

#10

Post by stephencanon »

torusle wrote: post #7

There are couple of tricks you can do if you fiddle with the bits of a floating point value using integer arithmetic and binary logic. That was a thing back in the 90th.. I wonder how hard the performance hit from moving values between integer and float pipeline is nowadays. Last time I looked into that was the Cortex-A8 (first I-Phone area). Doing that kind of trick costed around 26 cycles (back and forth) due to pi…

There are basic integer operations in the FP/SIMD units on most CPUs, so there’s no generally need to “move back and forth” unless you need to branch on the result of a comparison, use a value as an address, or do some more specialized arithmetic.
Post reply on HN