A floating point number is given. the task is to evaluate the value of its square root. We will discuss how to find the square root of a real number in this post, and also present a C Language code which does this job. The value of the root will be evaluated with the Hero’s method.

Finding Square Root : The Hero’s method

Let there be a real number C having square root \pm x . then it is represented by: x=\sqrt {C} .
So we have x=\sqrt {C}

We can find the roots of this function with the Newton-Raphson derived qth root method as described in this post : Finding qth real root of a real number
Putting q=2 in the qth root iterative formula we get the iterative formula to evaluate square root of a real number C. This iterative formula with q=2 is known as the Hero’s method as is shown below:

Finding square root of a real number with Hero’s Method:
x_{n+1}=\frac{1}{2}(x_{n}+\frac{C}{x_{n}})

With the last expression we can find square roots of a real number ‘C’. This method is known as the Hero’s method. If we find the root x of the equation at the nth iteration then the roots of the equation would be: \pm x_{n}

In this case we have a 2nd order equation which will have two roots with same value but different sign. So if we find one root then we automatically find the other root. Now the initial guess. We can take an initial guess any arbitrary value other than 0, for this case, and that need not to be close to the root. The function is parabolic, and for real roots the apex of the parabola is below the X axis and on the Y axis and thus there is no chance of a cycle.

For the case of C is negative no real root exists and this method will fail to provide any result. To calculate imaginary root of C, we can take the positive value of C and find its root say \pm r , and thus the imaginary root is written as \pm ir , where i=\sqrt{-1}

Sourcecode

Now we will present a code which will calculate the square root of a real number using the Hero’s method described above.

/* This code is a part of https://phoxis.org/2010/04/27/evaluating-square-root-hero/ 
 * Source code to evaluate the square root of a real number with Hero's Method
 */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define ERROR 0

double sqroot (double c);

int
main (void)
{
  double c, x;

  printf ("c: ");
  scanf (" %lf", &c);

  x = sqroot (c);
  
  printf ("\nsqroot(%lg) = %lg", c, x);
  printf ("\nsqrt  (%lg) = %lg", c, sqrt (c));
  printf ("\n");

  return 0;
}

double
sqroot (double c)
{
  double x, x_new;

  if (c == 0)
    return 0;
  else if (c < 0)
    return -NAN;
  else if (c == INFINITY)
    return INFINITY;
  
  /* Initial guess is 1 */
  x_new = 1;

  /* Calculate the root of c with Hero's method 
   */
  do
    {
      x = x_new;
      x_new = 0.5 * (x + c / x);
    }
  while (fabs (x_new - x) > ERROR);

  return x_new;
}

to compile this code use the -lm switch to link the math library as it uses the sqrt() function to compare the results:

gcc sqroot.c -lm -o sqroot

The function sqroot () receives a double calculates its root and returns a double. First it checks if the number passed is 0, if yes it returns 0. If a negative number is passed then -NAN is returned. NAN is described as in math.h . If c is INF this is a very large number which is not possible to represent with double, then it returns INF. Thus the special cases are handled first.

Then we set the first guess as 1. Any other arbitrary number could be taken and does not matter in this case. After the initial guess is set, the do-while loop finds the root of the number c with Hero’s method. x is the current guess of the root which corresponds with x_{n} in the equation. The x_new is the next guess of the root which is found from the previous value of x and corresponds to x_{n+1} in the equation. The statement x_new = 0.5 * (x + c / x) calculates the next guess from the previous guess, and the statement in the next iteration x = x_new sets the new guess, found in the previous iteration, as the current x.
The iteration will stop when the new and old guesses differ within a desired accuracy. The ERROR is defined as zero, that is we want the root to be represented as far as possible accurate which is representable by a double data type. When the difference between two guesses will be smaller than representable in computer then the loop will terminate. As this method converges very fast and the termination condition is met every time.

The results of the function sqroot() constructed with Hero’s method and the math.h library function sqrt are compared.

Advertisements

2 thoughts on “Hero’s Method : Evaluating square root of a real number

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