/**************************************************************************************
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 t2 = NUM we return t, if t2 < NUM all of the numbers between LB and t are not the square root, hence LB = t. Similarly, if t2 > 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