Algorithm C Programming Coding Mathematical Algorithms

C Programming-Babylonian method for square root

C Programming - Babylonian method for square root - Mathematical Algorithms - If we are sure that n is a perfect square, then we can use following method.

1.Algorithm:

This method can be derived from (but predates) Newton – Raphson method.
1 Start with an arbitrary positive start value x (the closer to the
root, the better).
2 Initialize y = 1.
3. Do following until desired approximation is achieved.
a) Get the next approximation for root using average of x and y
b) Set y = n/x
2.Implementation:

C
/*Returns the square root of n. Note that the function */
float squareRoot(float n)
{
  /*We are using n itself as initial approximation
   This can definitely be improved */
  float x = n;
  float y = 1;
  float e = 0.000001; /* e decides the accuracy level*/
  while(x - y > e)
  {
    x = (x + y)/2;
    y = n/x;
  }
  return x;
}
 
/* Driver program to test above function*/
int main()
{
  int n = 50;
  printf ("Square root of %d is %f", n, squareRoot(n));
  getchar();
}

Example:

n = 4 /*n itself is used for initial approximation*/
Initialize x = 4, y = 1
Next Approximation x = (x + y)/2 (= 2.500000), 
y = n/x  (=1.600000)
Next Approximation x = 2.050000,
y = 1.951220
Next Approximation x = 2.000610,
y = 1.999390
Next Approximation x = 2.000000, 
y = 2.000000
Terminate as (x - y) > e now.

If we are sure that n is a perfect square, then we can use following method. The method can go in infinite loop for non-perfect-square numbers. For example, for 3 the below while loop will never terminate.

C program
/*Returns the square root of n. Note that the function
  will not work for numbers which are not perfect squares*/
unsigned int squareRoot(int n)
{
  int x = n;
  int y = 1;
  while(x > y)
  {
    x = (x + y)/2;
    y = n/x;
  }
  return x;
}
 
/* Driver program to test above function*/
int main()
{
  int n = 49;
  printf (" root of %d is %d", n, squareRoot(n));
  getchar();
}
READ  How to Add Calculator in Quick Settings on Android Nougat

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment

X