3 ms·
Not only similar, it's identical to Newton Raphson in ideal arithmetic! The nth order product approximation for the reciprocal of d = 1 - x is y_n = product_{i
by bsteinbach 3y ago
Not only similar, it's identical to Newton Raphson in ideal arithmetic!
The nth order product approximation for the reciprocal of d = 1 - x is
y_n = product_{i=1}{n} (1 + x^{2^(i-1)}) = sum_{i=0}^{2^n - 1} x^i = (1 - x^(2 n)) / (1 - x).
The Newton-Raphson iteration for the reciprocal of d is
z_{n+1} = z_n * (2 - (1-x) * z_n).
Induction with the base case z_0 = 1 = y_0 shows the sequences are equal by inserting y_n for z_n in the Newton Raphson iteration:
z_{n+1} = (1 - x^(2 n)) * (2 - (1 - x^(2 n))) / (1 - x) = ( 1 - x^(4 n) ) / ( 1 - x) = y_{n+1}.
So I guess you could call it an explicit product formula for the Newton Raphson reciprocal.
- perihelions 3y agoThis 100% checks out! I didn't recognize this at all. - "...in ideal arithmetic!" Comparing the two, Newton-Raphson seems rather better conditioned. I guess it's the (1.0 + x^(2^i)) part that holds back the explicit-product version (adding a large float with a small one).