I have discussed the problem of efficient squarerootcalculation 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 , with sides and . We must progressively transform this rectangle into a square.

Let the two sides of the current rectangle be and (initially and ). At each iteration we average the lengths of the sides to get one of the new side, , and the other side becomes . Successive averaging and completion eventually converge, and both and converge to !

* * *

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

This entry was posted on Tuesday, December 22nd, 2015 at 20:42 pm and is filed under algorithms, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

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

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

RT @JohnJJohnston: A lovely evening, discussing lunar representations with @petriefriends’ members. This bronze lunar Osiris, a Roman writi… 4 hours ago

RT @nixcraft: More code means more bugs. More bugs means more time spend fixing it. So keep it simple. Follow unix philosophy https://t.co/…13 hours ago

RT @SSEAToronto: We hope to see you at our next talk on Friday, March 23 at Sidney Smith Hall! Join us to hear from @UofT professor Mary-An… 13 hours ago

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

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