Division using Newton-Raphson.
We want to compute 1/y for some number y. This amounts to solving the equation:
<br />
\frac{1}{x} - y = 0<br />
for x. If we do that using Newton-Raphson, we get:
<br />
x_{n+1} = 2x_{n} - x_{n}^{2}y<br />
This is indeed a true division algorithm as it doesn't contain any divisions. Also, due to quadratic convergence, you double the number of significant digits at each step. Long division will only yield one significant digit per step.
The above algorithm can also be used to compute the Taylor series of a function 1/f(x) if the Taylor series of f(x) is known. You just take P_{0}(x) to be the first term of the expansion, e.g. if f(0) is nonzero then P_{0}=1/f(0) and you iterate using the algorithm:
<br />
P_{n+1}(x) = 2P_{n}(x) - P_{n}(x)^{2}f(x)<br />
At each step the number of correct terms will double, so P_{n}(x) will contain the first 2^{n} terms of the series expansion of 1/f(x). Note that this means that the term P_{n}(x)^{2}f(x) has to be computed to order \mathcal{O}\left(x^{2^{n+1}-1}\right).
So, computing the first billion terms of 1/f(x) only requires 30 iterations
But we can do much more than computing reciprocals. Computing the series expansion of \log(f(x)) is almost as easy as computing the reciprocal of f(x) as all you have to do is integrate f'(x)/f(x) term by term. And using this algorithm for \log(f(x)) you can also compute \exp\left(f(x)\right) using Newton-Raphson to solve for that function that yields f(x) after taking the logarithm using Newton-Raphson and the algorithm for computing the logarithm of a series expansion.
Since a large class of functions can be expressed in terms of logarithms and exponentials, the series expansion of pretty much any awkward function can be computed this way.
