I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming. I end up with this working code in C++
#include <iostream>
using namespace std;
double SqrtNumber(double num)
{
double lower_bound=0;
double upper_bound=num;
double temp=0; /* ek edited this line */
int nCount = 50;
while(nCount != 0)
{
temp=(lower_bound+upper_bound)/2;
if(temp*temp==num)
{
return temp;
}
else if(temp*temp > num)
{
upper_bound = temp;
}
else
{
lower_bound = temp;
}
nCount--;
}
return temp;
}
int main()
{
double num;
cout<<"Enter the number\n";
cin>>num;
if(num < 0)
{
cout<<"Error: Negative number!";
return 0;
}
cout<<"Square roots are: +"<<sqrtnum(num) and <<" and -"<<sqrtnum(num);
return 0;
}
Now the problem is initializing the number of iterations nCount in the declaratione ( here it is 50). For example to find out square root of 36 it takes 22 iterations, so no problem whereas finding the square root of 15625 takes more than 50 iterations, So it would return the value of temp after 50 iterations. Please give a solution for this.
Why not try to use the Babylonian method for finding a square root.
Here is my code for it:
double sqrt(double number)
{
double error = 0.00001; //define the precision of your result
double s = number;
while ((s - number / s) > error) //loop until precision satisfied
{
s = (s + number / s) / 2;
}
return s;
}
Good luck!
//long division method.
#include<iostream>
using namespace std;
int main() {
int n, i = 1, divisor, dividend, j = 1, digit;
cin >> n;
while (i * i < n) {
i = i + 1;
}
i = i - 1;
cout << i << '.';
divisor = 2 * i;
dividend = n - (i * i );
while( j <= 5) {
dividend = dividend * 100;
digit = 0;
while ((divisor * 10 + digit) * digit < dividend) {
digit = digit + 1;
}
digit = digit - 1;
cout << digit;
dividend = dividend - ((divisor * 10 + digit) * digit);
divisor = divisor * 10 + 2*digit;
j = j + 1;
}
cout << endl;
return 0;
}
As I found this question is old and have many answers but I have an answer which is simple and working great..
#define EPSILON 0.0000001 // least minimum value for comparison
double SquareRoot(double _val) {
double low = 0;
double high = _val;
double mid = 0;
while (high - low > EPSILON) {
mid = low + (high - low) / 2; // finding mid value
if (mid*mid > _val) {
high = mid;
} else {
low = mid;
}
}
return mid;
}
I hope it will be helpful for future users.
Here is a very simple but unsafe approach to find the square-root of a number. Unsafe because it only works by natural numbers, where you know that the base respectively the exponent are natural numbers. I had to use it for a task where i was neither allowed to use the #include<cmath> -library, nor i was allowed to use pointers.
potency = base ^ exponent
// FUNCTION: square-root
int sqrt(int x)
{
int quotient = 0;
int i = 0;
bool resultfound = false;
while (resultfound == false) {
if (i*i == x) {
quotient = i;
resultfound = true;
}
i++;
}
return quotient;
}
This a very simple recursive approach.
double mySqrt(double v, double test) {
if (abs(test * test - v) < 0.0001) {
return test;
}
double highOrLow = v / test;
return mySqrt(v, (test + highOrLow) / 2.0);
}
double mySqrt(double v) {
return mySqrt(v, v/2.0);
}
After looking at the previous responses, I hope this will help resolve any ambiguities. In case the similarities in the previous solutions and my solution are illusive, or this method of solving for roots is unclear, I've also made a graph which can be found here.
(default is square root for the sake of this question)
#include <cmath>
// for "pow" function
double sqrt(double A, double root = 2) {
const double e = 2.71828182846;
return pow(e,(pow(10.0,9.0)/root)*(1.0-(pow(A,-pow(10.0,-9.0)))));
}
Explanation:
This works via Taylor series, logarithmic properties, and a bit of algebra.
Take, for example:
log A = N
x
*Note: for square-root, N = 2; for any other root you only need to change the one variable, N.
1) Change the base, convert the base 'x' log function to natural log,
log A => ln(A)/ln(x) = N
x
2) Rearrange to isolate ln(x), and eventually just 'x',
ln(A)/N = ln(x)
3) Set both sides as exponents of 'e',
e^(ln(A)/N) = e^(ln(x)) >~{ e^ln(x) == x }~> e^(ln(A)/N) = x
4) Taylor series represents "ln" as an infinite series,
ln(x) = (k=1)Sigma: (1/k)(-1^(k+1))(k-1)^n
<~~~ expanded ~~~>
[(x-1)] - [(1/2)(x-1)^2] + [(1/3)(x-1)^3] - [(1/4)(x-1)^4] + . . .
*Note: Continue the series for increased accuracy. For brevity, 10^9 is used in my function which expresses the series convergence for the natural log with about 7 digits, or the 10-millionths place, for precision,
ln(x) = 10^9(1-x^(-10^(-9)))
5) Now, just plug in this equation for natural log into the simplified equation obtained in step 3.
e^[((10^9)/N)(1-A^(-10^-9)] = nth-root of (A)
6) This implementation might seem like overkill; however, its purpose is to demonstrate how you can solve for roots without having to guess and check. Also, it would enable you to replace the pow function from the cmath library with your own pow function:
double power(double base, double exponent) {
if (exponent == 0) return 1;
int wholeInt = (int)exponent;
double decimal = exponent - (double)wholeInt;
if (decimal) {
int powerInv = 1/decimal;
if (!wholeInt) return root(base,powerInv);
else return power(root(base,powerInv),wholeInt,true);
}
return power(base, exponent, true);
}
double power(double base, int exponent, bool flag) {
if (exponent < 0) return 1/power(base,-exponent,true);
if (exponent > 0) return base * power(base,exponent-1,true);
else return 1;
}
int root(int A, int root) {
return power(E,(1000000000000/root)*(1-(power(A,-0.000000000001))));
}
Here is a very awesome code to find sqrt and even faster than original sqrt function.
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f375a86 - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
x = x*(1.5f - xhalf*x*x);
x = x*(1.5f - xhalf*x*x);
x=1/x;
return x;
}
if you need to find square root without using sqrt()
,use root=pow(x,0.5)
.
Where x is value whose square root you need to find.
Remove your nCount
altogether (as there are some roots that this algorithm will take many iterations for).
double SqrtNumber(double num)
{
double lower_bound=0;
double upper_bound=num;
double temp=0;
while(fabs(num - (temp * temp)) > SOME_SMALL_VALUE)
{
temp = (lower_bound+upper_bound)/2;
if (temp*temp >= num)
{
upper_bound = temp;
}
else
{
lower_bound = temp;
}
}
return temp;
}
Source: Stackoverflow.com