[Math] Finding reciprocal via Newton Raphson: How to determine initial guess

newton raphson

I'm learning Newton-Raphson to get the reciprocal of any arbitrary value. I need this in order to accurately emulate how the PlayStation 1 does the divide. They used a modified version of the algorithm.

Trying to understand the basic algorithm I came across this video.

Which is all fine and dandy, makes sense. But then as I started writing the code to get the reciprocal, I wasn't sure how to assign the initial guess value. In his example, he set it to 0.1f to find the reciprocal for 7. I found that if I set it to anything else, I would get totally different results. e.g. If I set it to 0.5f, I would get -217.839 in 3 iterations.

Code:

float GetRecip(float Number, float InitialGuess, int Iterations)
{
    float Result;

    Result = InitialGuess;
    for (int i = 0; i < Iterations; i++)
    {
        Result = Result * (2 - Number*Result);
    }

    return (Result);
}

// Example:
float Recip1 = GetRecip(7, 0.1f, 3); // 0.142847776
float Recip2 = GetRecip(7, 0.5f, 3); // -217.839844

Changing the number of iterations doesn't help, it would yield more drastic different results.

How do I go about finding that initial guess of 0.1f?

Best Answer

The algorithm is obfuscated a bit (among other things) because the GTE works exclusively with fixed point numbers. Barring these details, the algorithm to approximate $d^{-1}$ is as follows.

  1. Determine an integer $m\in[0, 255]$ and an integer $k$ such that $(256 + m) {\cdot} 2^k$ is closest to $d$. That is, round $d$ to nine significant bits.
  2. Use a lookup table $\mathrm t[]$ of integers in the range $[0, 255]$ to approximate $$ (256 + m)^{-1} \approx (257 + \mathrm t[m]) {\cdot} 2^{-17}$$ to nine significant bits.
  3. Perform one Newton-Raphson iteration on the approximation $ r = (257 + \mathrm t[m]) {\cdot} 2^{-(17 + k)} \approx d^{-1}$.

For the example $d=7$ this proceeds as follows.

  1. $7 = (256 + 192) {\cdot} 2^{-6}$, so $m=192$ and $k=-6$.
  2. $\mathrm t[192] = 36$ so $(256 + 192)^{-1} \approx (257 + 36) {\cdot} 2^{-17}$.
  3. With $r=(257 + 36) {\cdot} 2^{-11} = 0.143066{\cdots}$ compute the Newton-Raphson iteration $2r - 7 r^2 = 0.142857{\cdots}$. The absolute error is about $3 {\cdot} 10^{-7}$.
Related Question