Friday, September 2, 2011

Method to find Square Root


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 so take x=n/2) .
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


Implementation:

/*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/2; //n/2 can be closest one.
  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.


For a perfect square number this e would be equal to 0.

1 comment:

  1. Another solution for Perfect Square is :

    Square numbers are sum of consecutive odd numbers like
    1+3+5+7=16 so add numbers till you get the required number --- O(sqrt(n)).

    1 + 3 + 5 + 7 +9 =25 Count of odd numbers = num = 5. Complexity O(sqrt (n)) .

    (or)

    Si=sum of i terms of AP i =1...n/2 as n/2>sqrt(n)

    Si can be obtained in O(1) i.e. sum of AP

    Do a binary search on those n/2 S items.
    complexity=log(n/2)+O(sqrt(n)).

    ReplyDelete