*Numerical* Convergence of the Babylonian Method?

Question

I understand the sequence $x_{n+1} = \frac12\left(x_n + \frac2 {x_n}\right) $ converges to $ \sqrt2 $ algebraically.

That is proved by means of fixed-point method or monotone convergence theorem and so on.

But, I do want to know whether the sequence converges numerically (and if so, the proof of it).

So, here is my question.

Does the following algorithm always terminate?

1. Choose an initial number $ x_0 > 0 $.
2. Calculate $x_{n+1}=\frac12\left(x_n + \frac2 {x_n}\right)$ to one more places of decimals you need.
3. Truncate the number $x_{n+1}$ to places of decimals you need.
4. When $x_{n+1}=x_n$ occurs, this algorithm terminates.

In step 3, you need to truncate the number, and I'm worried about the effect of truncation on the convergence.

Answer 1

Actually, this issue does come up in square root algorithms if you are not careful. To take a simple example, suppose we work in base $12$ and we truncate using the floor function. Start with a bigger approximation to $\,\sqrt{2}\,$ which is $\, 17/12. \,$ Using the Babylonian algorithm, the next approximation is $\, (17/12 + 24/17)/2 = 577/408 = 16.9705.../12 \,$ and if you truncate this to $\, 16/12, \,$ then the next approximation is $\, (16/12 + 24/16)/2 = 17/12 \,$ and we have a loop, unless we terminate the algorithm at this step since we are getting a bigger approximation. The exact behavior of the sequence of approximations to $\, \sqrt{x} \,$ depends on the exact details of how the arithmetic is done, but except for the first iteration, you should always terminate if this sequence stops decreasing.

This issue is a very general one. Suppose you have $\,\{x_n\},\,$ a sequence of real numbers given by a recurrence $\, x_{n+1} = f(x_n) \,$ that converges to a finite limit. Now replace the real numbers by $\,F,\,$ a finite set of numbers such as used in a computer system, fixed point or floating point. Then the computing function $\, f_F : F \to F \,$ corresponding to $\,f,\,$ no matter what the initial value or even if the original $\,f\,$ converges or not, must eventually loop, and in best cases the loop is a fixed point.

Just as a curiousity, this kind of loop happens in other bases, namely, $\, \{2, 12, 70, 408, 2378, \dots\} \,$ which is OEIS sequence A001542 which relates them to continued fraction convergents to $\, \sqrt{2}. \,$