You can find reverse number $R$ using $x_{n+1} = x_n(2 - x_n \cdot R) \ \ $ where $ n = 0,1,..$
Prove it using Newton method for finding $0's$ of some function $f$
Anyone have idea what that function $f$ might be?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The Newton iteration is $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$ and to find the inverse you should root-find $f(x) = 1/x - R$ which has a root at $1/R$. Note that $f'(x) = -1/x^2$ so $f(x_n)/f'(x_n)$ will give you exactly the iteration you are looking for.
$\begingroup$
$\endgroup$
The function $f(x) = R - \frac{1}{x}. \;$ You find the simple derivation of your recursion formula here
answered Nov 5, 2013 at 14:42