Re: exact fixed-point inverse square root

Nils wrote:
Hi usenet.

I'm looking for an algorithm to calculate the inverse square root of a fixed point integer.

I know about the Newton-Raphson iteration, but this one does not work if you're looking for an exact result because each step requires a multiplication which in fixed point math always goes along with a loss of precision.

Integer square roots can be calculated exact using a two bits per iteration algorithm.

For my application the Newton-Raphson iteration does not work. Even when I add more iterations than nessesary I always got biten by the precision loss. The bitwise calculation of the square-root (adopted to fixed point) followed by a division works well but is computational expensive.


I have never seen a inverse square root iteration that is not based on the Newton-Raphson iteration and I wonder why.
Even if it's not practical for real world applications because it's is to slow it would be nice to know how it works in principle.

I tried to come up with one of my own but failed. Any ideas?

Isn't this sort of trivial?

A fixed-point implementation is effectively identical to an integer-only, if you prescale the input, right?

So, by exact do you mean closest possible result, i.e. perfectly rounded, or do you mean largest possible value such that

res * res * input_value <= 1.0

i.e. truncated rounding?

Calculate an approximate result using table lookup + NR, then square it and multiply by the original number. The result should be very close to 1.0.

Depending upon the first step you can then adjust the first guess up or down by one ulp, then check which guess results in the best answer.

You can also do one extra iteration of the NR, using double-wide precision, then use the final error term to determine the correctly rounded result.

Terje

--
- <Terje.Mathisen@xxxxxxxxxxxxx>
"almost all programming can be viewed as an exercise in caching"
.

Relevant Pages

  • Re: newton convergence
    ... the Householder expressions for the Nth root of any number P. ... A SIMPLE EXAMPLE ON THE SQUARE ROOT OF ANY NUMBER P. ... Higher-order rational process based on the Rational Mean. ... multiply by THREE the number of exact digits in each iteration. ...
    (sci.math.num-analysis)
  • Re: computation of square root & reciprocal calculation
    ... The most important idea is to realize that inverse square root have a much faster NR iteration than both regular square root and reciprocal division: ... Using this you can use a small lookup table to get an approximate inverse square root, then iterate 2-4 times to get it as accurate as you want. ... By modifying the last iteration slightly, you can of course use the same idea to calculate either of the functions you desired. ... For further speedups, I suggest calculating multiple inverse square roots in parallel, since that will allow you to schedule most/all of the multi-cycle operations in parallel. ...
    (comp.arch.arithmetic)
  • Re: cube root of a given number
    ... GENERAL HURTWITZ's ROOT-SOLVING METHOD? ... Higher-order rational process based on the Rational Mean: ... approximations -by defect and excess-- to the square root of P. ... multiply by THREE the number of exact digits in each iteration. ...
    (sci.math)
  • Re: rapidly converging rational sqrt
    ... Note that after iteration 6 we have ... > more than 100 significant digits. ... I don't wish to denigrate your algorithm unduly, but square root algorithms ...
    (sci.math.research)
  • Higher-order root solving. Newton. Halley, Householder, Bernoulli
    ... A Higher-order algorithm for the square root of any number P. ... By agency of such a simple arithmetical operation you can produce all the Householder expressions for the Nth root of any number P. ... Two expressions whose product is trivial and equal to P, both of them multiply by FOUR the number of exact digits in each iteration. ...
    (sci.math.num-analysis)