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.

wood

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

One Response 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: