## OB Sqrt

I have discussed the problem of efficient square root calculation quite a few times. And yet, while reading Rudman’s The Babylonian Theorem, I found yet another square root algorithm. The Old Babylonian square root algorithm. Let’s have a look on how it works.

Rudman, in The Babylonian Theorem, presents the Old Babylonian method of extracting square roots. Let’s look at the code first, and we’ll discuss how it works just after:

template <typename T> T ob_sqrt(const T & x)
{
T a=x,b=1,l;
do
{
l=a;
a=(a+b)/T(2);
b=x/a;
}
while (a!=l);
return a;
}


The form may be reminiscent of Newton’s algorithm (that I discussed in some detail here), but its mindset is different. It is basically a quadrature algorithm that finds a (perfect) square that has the same area as some initial rectangle. The initial rectangle has an area of $n$, with sides $n$ and $1$. We must progressively transform this $n\times{1}$ rectangle into a $\sqrt{n}\times\sqrt{n}$ square.

Let the two sides of the current rectangle be $a$ and $b$ (initially $a=n$ and $b=1$). At each iteration we average the lengths of the sides to get one of the new side, $a'=\frac{1}{2}(a+b)$, and the other side becomes $b'=n/a'$. Successive averaging and completion eventually converge, and both $a$ and $b$ converge to $\sqrt{n}$!

*
* *

So it appears that the Old Babylonians arrived at Newton’s algorithm specialized for square root a couple of thousands years before Newton. Recall, Newton’s algorithm iterates with

$\displaystyle x_{t+1}=\frac{1}{2}\left(x_t+\frac{n}{x_t}\right)$,

while the Old Babylonian algorithm iterates with

$\displaystyle a_{t+1}=\frac{1}{2}\left(a_t+b_t\right)=\frac{1}{2}\left(a_t+\frac{n}{a_t}\right)$!

Reference

Peter S. Rudman —The Babylonian Theorem: The Mathematical Journey to Pythagoras and Euclid — Prometheus Books, 2010, 248 pp., ISBN 978-15910-2773-7

### 2 Responses to OB Sqrt

1. […] hard, even for simple problems like the square root, subject we’ve visited a number of times. One method we haven’t explored yet, is using the Taylor series. The Taylor series for […]

2. […] discussed algorithms for computing square roots a couple of times already, and then some. While sorting notes, I’ve came across something interesting: […]