# The Babylonian square-root algorithm
The [Babylonian square root algorithm](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Heron's_method) (Also known as the Heron's method) of computing square root is one of the simplest algorithm of computing square root. Here we will show some rigorously some properties of this algorithm and discuss its' relataionship with Cauchy commpleteness.

## The Babylonian algorithm
The Babylonian algorithm takes in a real number $a \in \mathbb R$, $a\geq 1$ and construct the following sequence that approximate $\sqrt a$ better and better.

1. Set $x_0=1$
2. Compute $$x_{n+1} = \frac{x_n + a/x_n}{2}$$
3. Repeat step two until the desired accuracy is reached

As one can see, the algorithm only requires elementary arithmetic. The idea of the algorithm is also pretty clear - it takes the $n$-th guess of the squre root and create a better guess by averaging it with the quotient of $a/x_n$

## Proof of correctness
We now demonstrate that the algorithm converges

**Lemma 1**: $x_n\geq \sqrt a$ for all $n\geq 1$
**Proof:** By the AM-GM inequality, we have $x_n\geq\sqrt{x_{n-1} (a/x_{n-1})} = \sqrt a$, so the sequence is lower bounded by $\sqrt a$

**Lemma 2**: $x_{n+1} \leq x_{n}$ for all $n\geq 1$
**Proof:** Note that $$x_{n+1}=x_n + \frac{x_n(-1+a/x_n^2)}{2} \leq x_n $$
because $(-1+a/x_n^2)$ is negative by Lemma 1

**Lemma 3**: Let $x_n = \sqrt a + \epsilon_n$, then for all $n\geq 1$$$\epsilon_{n+1} \leq \frac{\epsilon_n}{2}$$
**Proof:** By direct computation, we see that
$$\epsilon_{n+1} = \epsilon_n -\frac{\epsilon_n^2 + 2\sqrt a \epsilon_n}{2(\sqrt a + \epsilon_n)}= \frac{\epsilon_n^2}{2 (\sqrt a + \epsilon_n)} \leq \frac{\epsilon_n}{2}$$
because $\epsilon_n\geq 0$ for all $n\geq 1$

**Proposition:** The algorithm above converges to $\sqrt a$
**Proof:** By Lemma 3, it is clear that $$0\leq\epsilon_{n+1}\leq \frac{\epsilon_1}{2^n}$$
Therefore $\lim_{n\to\infty} \epsilon_n = 0$. This implies $\lim_{n\to \infty} x_n = \sqrt a$

**Remark:** Actually in the proof of lemma 3, we see that when $\epsilon_n \leq \sqrt a$, $\epsilon_{n+1} \leq \epsilon_n^2/{2\sqrt a}$ and the convergence becomes quadratic.

## Relationship with Cauchy completeness
This algorithm, combined with the fact that $\sqrt 2$ is not rational, can be use to show that $\mathbb Q$ is not Cauchy. This is because $\{x_n\}_{n=1}^{\infty}$ defines a converging sequence that is not converging to a limit in $\mathbb Q$.