Home Problems Volumes Ranking Forum Help News Mess
Contents

Square Root Approximation

For any given value v the square root of it is some value r such that it yields v if multiplied by itself (i.e. "squared"). So using function sqrt to describe square root we can write:

r = sqrt(v)
v = r * r = r ^ 2

There is no straighforward way to calculate square root, so if any program needs it, programmer should use some iterative approximation algorithm (which is often already implemented in his programming language library or even inside the (co)processor itself).

Here we describe the popular method which was probably in use in ancient Greece, Babylon etc - and which is good to be learned.

Heron's (or Babylonian) Method

  1. To find square root r of a value v, first choose any reasonable approximation - (for example, let r = 1);
  2. Calculate d as the result of division v by r, i.e. d = v / r - obviously the better approximation r gives, the closer d will be to it;
  3. Check the difference between r and d, if it is small enough for your purpose, then stop and return r;
  4. Calculate average between r and d and use it as the next step approximation, i.e. r{new} = (r + d) / 2);
  5. Proceed with the new approximation from the step 2.

Let us see an example - we'll try to compute sqrt(10):

r = 1

d = 10 / 1 = 10
abs(r - d) = abs(1 - 10) = 9   - difference is bit too much still
(r + d) / 2 = (1 + 10) / 2 = 5.5
let r = 5.5

d = 10 / 5.5 = 1.8182
abs(r - d) = abs(5.5 - 1.8182) = 3.6818   - again too much, let us proceed
(r + d) / 2 = (5.5 + 1.8182) / 2 = 3.6591
let r = 3.6591

d = 10 / 3.6591 = 2.7329
abs(r - d) = abs(3.6591 - 2.7329) = 0.9262   - it become less than 1, let us do the one step more
(r + d) / 2 = (3.6591 + 2.7329) / 2 = 3.196
let r = 3.196

So in just 3 steps we get reasonably well result (exact value is sqrt(10) = 3.1623...), even despite we started from extremely poor initial approximation of r = 1.

To practice this algorithm see the Square Root task. You can also read wikipedia on more methods for square root computing methods.