Why does this weird iteration converge to the square root ??

Question

Let $1 < x < 4$ , $a_1 = x$ and $b_1 = 0$.

Now consider the (conditional) iterations

if $a_n > b_n$ then

$a_{n+1} = 4(a_n - b_n - 1)$

$b_{n+1} = 2(b_n + 2)$

else ( $a_n = b_n$ or $a_n < b_n$ )

$a_{n+1} = 4 a_n$

$b_{n+1} = 2 b_n$

Now consider

$c_n = \frac{b_n}{2^n}$

Now define

$f(x) = \lim_{n \to \infty} c_n $

Now apparently $ f(x) = \sqrt x$

Despite being a simple limit of a conditional iteration, I do not get it.

I am even surprised limits of conditional iterations can be analytic functions with respect to the starting value.

I have never seen these type of iterations during my education nor in a book. Not even in books about numerical methods.

Sure the algorithm converges slowly but it has benefits too and it does not use complicated functions.

Im clearly missing the big picture here.

Conditional iterations (or recursions) is a topic I know nothing about it seems.

How and why does this algorithm give the square root ?

What is the bigger picture ? How to generalize this ?

I could be wrong, but is this related to the mediant when $x$ is rational ?

Answer 1

Claim: This process calculates the square root in binary, by calculating the next digit.

The described process is how one would calculate square roots in binary using the long division method. I'm guessing that you can find articles about the process.

Fill you get stuck, add in details of what you've been working on and why you're stuck.

---

Observations:

• $c_n = \frac{b_n}{2^n}$ suggests we want to look at $b_n$ in binary.
• $b_{n+1} = 2(b_n + 2) $ or $ 2b_n \Rightarrow c_{n+1} = c_n + \frac{1}{2^n} $ or $ c_n$. In fact, ignore $b_n$ and just work with $c_n$.
• The idea is that if you know $ c_n ^2 \leq x \leq (c_n + \frac{1}{2^{n-1}})^2$, then to figure out the next digit you look at $ x - ( c_n^2 + \frac{1}{2^n} )^2$ and see if it's positive or negative.