1

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?

KBowser
  • 11
  • When you say the classical method, do you mean the iteration $y_{k+1}=2y_k-xy_k^2$ (where you want $\frac{1}{x}$)? Because it seems like this would work very nicely in your context. If you take $y_0=\frac{1}{x}$, then if $\Delta x$ has opposite sign from $x$ then you need $|\Delta x|<|x|/2$, and if they have the same sign then you need $|\Delta x|<|x|$. Both are fairly mild requirements. – Ian Dec 18 '15 at 18:08
  • @Ian yes, but that method needs a good seed value to converge in few iterations, I was wondering if it's possible to use some workarounds as I have already 1/x as a starting point – KBowser Dec 18 '15 at 18:12
  • How few iterations do you need? This method gives essentially $2^n$ binary digits in $n$ steps with any initial condition that converges at all. That gives double precision in 6 steps (maybe 7 if I miscounted slightly). I'm not sure how much better you're going to get than that without some lookup... – Ian Dec 18 '15 at 18:13
  • Also, in floating point arithmetic, at least if you have the internal representation, it is easy to satisfy the requirement that $0<y_0<2/x$, because you can just take $y_0$ to be $2^{-n}$ where $n$ is the exponent in the floating point representation of $x$. – Ian Dec 18 '15 at 18:19
  • Can you give an example of the kind of $x$ and $\Delta x$ that you need to deal with in your application? I suspect that the "classical" method will require even less than six iterations to converge, with $y_0=1/x$ and $|\Delta x| \ll |x|$. – Ian Dec 18 '15 at 18:52

1 Answers1

2

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.

Ben Grossmann
  • 225,327