Data Structure and Algorithm

/**************************************************************************************

DISCRIPTION

The algorithm is very simple and uses the same concept of binary search; it works by minimizing the possible range of the square root.

Suppose NUM = 25,
We know that NUM is between 0 and 25, therefore its square root’s lower bound is LB = 0 and upper bound is UB = 25.
The next step is calculating the average of the bounds t = (LB + UB)/2.
If t² = NUM we return t, if t² < NUM all of the numbers between LB and t are not the square root, hence LB = t. Similarly, if  t² > NUM then our upper bound, UB = t.

We can repeat this step as many times as we want. Each iteration doubles the precision.
If we didn’t find the specific square root when we finish, we should return (LB + UB) / 2, as it is the closest we can get to the actual square root.

**************************************************************************************/

#include <iostream.h>
#include <conio.h>

double sqrt(double num)
{
double lb,ub;
int iteration = 35; //The greater the number of iteration, The accurate is the result
lb = 0; //Set Lower Bound to zero
ub = num; //Set Upper Bound to num

while(iteration > 0)
{
  double t = (lb + ub) / 2;
  if(t * t == num) //If square of a t is equal to the num itself then
   return t; //Return Root

  else if(t * t > num) //If square of t is greater than the num
   ub = t; //Update Upper Bound

  else
   lb = t; //Update Lower Bound

  iteration--; //Decrease iteration
}

return (lb + ub) / 2; //Return closest value if root is not found in 35 iterations
}

int main()
{
double num,result;
cout << "Square Root of : ";
cin >> num;
if (num < 0)
  {
   cout << "Cannot Square Root a Negative Number";
   getch();
   return 0; //Halt the program
  }

result = sqrt(num);
cout << "is " << result; //Print Result
getch();
return 0;
}

OUTPUT

Download Original File

SquareRoot.cpp