Division-less computation of $1/(x+d)$ starting from $1/x$

52 Views Asked by At

I need to compute $\frac{1}{x+\Delta x}$ avoiding divisions, is this possible through an iterative method starting from $\frac{1}{x}$? I thought of two possibilities that could be different from the classical computation of the reciprocal using the Newton-Raphson algorithm:

1) find $\frac{x}{x+\Delta x}$ such that $\frac{1}{x}\cdot\frac{x}{x+\Delta x}=\frac{1}{x+\Delta x}$

2) find $\frac{\Delta x}{x(x+\Delta x)}$ such that $\frac{1}{x}-\frac{1}{x}+\frac{1}{x+\Delta x}=\frac{1}{x}-\frac{\Delta x}{x(x+\Delta x)}=\frac{1}{x+\Delta x}$

Is one of these viable or am I stuck with the classical way of finding the reciprocal? Can you help me find if there are any equations whose roots are the values I'm looking for?

1

There are 1 best solutions below

0
On

One slick method (assuming $|\Delta x| < x$) is to use the geometric series. We have $$ \frac 1{x + \Delta x} = \frac 1x \cdot \frac{1}{1 + \frac{\Delta x}{x}} = \frac 1x \sum_{n=0}^\infty (-1)^n\left(\frac{\Delta x}{x}\right)^n $$ for an approximation, simply take the sum out to $N$ steps rather than infinitely many.

This approach gives you a linear convergence rate, which is very much outdone by Newton-Raphson.