# *Numerical* Convergence of the Babylonian Method?

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.

• What is the difference between the two modes of convergence by your interpretation? Does "numerical" convergence refer to the number of correct digits? – Chris Jun 17 '18 at 18:06
• I'm worried about oscillation of the sequence, because the sequence is truncated in calculus – CWPC Jun 17 '18 at 18:11
• The "fixed point theorems" you allude to, if I'm interpreting you correctly, do provide guarantees on the number of correct digits, which must be monotonically increasing (in fact, quadratically). There can't be any "oscillation" in the sense I believe you find troublesome. – Chris Jun 17 '18 at 18:19
• Suppose an initial number $x_0 > \sqrt2$ , the sequence is monotonically decreasing and always larger than $\sqrt2$ algebraically. But the sequence is truncated numerically, there is a number n such that the term $x_n$ is less than $\sqrt2$. Then, the sequence increases! And in this point, the term is larger than $\sqrt2$. So, the sequence restart to decrease... Thus does the sequence oscillate in such a way? – CWPC Jun 17 '18 at 18:41
• The kind of “truncation” I recall from calculus does not mean throwing away the “extra” digits from a number. It means you stop adding the series after some term. – David K Jun 17 '18 at 18:42

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}. \,$
• So, I'm curious what if the number $2$ in $\sqrt2$ is replaced by other number or the base is replaced by other or fixed-point representation is replaced by floating-point representation... – CWPC Jun 17 '18 at 20:02