Structures, water, computers, languages and people (not necessarily in this order)

Fast square roots

I have always been puzzled about the way square roots calculations are taught in the elementary school. I remember a very cumbersome method in which each decimal was extracted with hard work.

In college, especially in my studies in computer science, I have not always been permitted to use a calculator during the examination time, so I learnt to calculate square roots with pencil and paper in a sufficiently approximate but fast way. In my case, I use to apply the Newton-Raphson algorithm to the equation f(x) = x-root(K) = 0

Suppose we need to calculate the root of a real number K. To calculate the root of K, first assume an educated guess x[0].

For small numbers my usual estimate is x[0] = K/2
Up to 1000, to start with x[0] = 8+(K/40) usually works well. In other cases, bearing in mind some perfect squares helps.

Once the first estimate is made, it is refined with the formula
x[i+1] = (1/2) * (x[i] + (K / x[i]))

For example, if you are on-site and you do not have a calculator near you and a worker asks you about the side of a slab of 500 sq meters you know that the side L = root(500) = 10*root(5) = 10*x
then
x[0] = 5/2 = 2.5 (error 12%)
x[1] = 9/4 = 2.25 (error 1%)
x[2] = 161/72 = 2.2361 ... (error 0.002%)

therefore the side is L = 22,361 m

The difference for root(780) between the classic algorithm and the Newton-Raphson one is clear in the appended images below.






Elementary school algorithm
















Iterative algorithm

5 comments:

  1. This is super useful and something that I was not ever taught in a math or engineering course at school... good to keep in the pocket though.

    ReplyDelete
  2. I thought that this method is called Babylonian method, used by Heron of Alexandria cca 1600yrs ago, which also seems to have been known by Babylonians 2000 yrs before Heron.
    Am I wrong in my assertion?

    ReplyDelete
    Replies
    1. Dear Eugen: you're absolutely right. Newton-Raphson for the square root is equivalent to the Babylonian rule. The good thing about Newton-Raphson is that you can get also cube roots, fourth roots, etc...

      Also, the presented algorithm is equivalent to the following recursive function:

      float sqroot (float num, float guess) {
      if (num < 0.0) return -1.0;
      if ((guess * guess) == num) return guess;
      return sqroot (num, (guess + (guess / num)) / 2);}

      Delete
  3. super cool stuff. No one teaches these tricks at schools and colleges. Awesome work bro. Thank you for sharing :)

    ReplyDelete