Finding of Nth root can be done with following methods. Nth root is similar to find the
cube root of any Number, we can apply same methods with modification to find Nth root.
cube root of any Number, we can apply same methods with modification to find Nth root.
Calculate Cube Root Of any number
For Calculating Cube root of N, We have straight forward method for checking all range like 0 to N with points with the difference of Accuracy we want. ISuppose we want to find Out Cube root of 3 with accuracy up to 5 decimal points, Then we have to check 0 to 3 with each time addition of 0.00001 (because we want 5 decimal accuracy) until we click right answer.
CubeRoot (3) = 1.44225
For click right answer loop must be run (1.44225 – 0)/0.00001 times which is 144225 times. For analysis purpose, let's assume loop go up to 3 So loop run 3/0.00001 times which is 300000 times.
Implementation this algorithm in C/C++.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
General Method For Cubic Root | |
Time Complexity : O (n) | |
where N is range of Possible Cubic roots | |
Space Complexity : O (1) | |
*/ | |
float CubicRoot(float Number , int accuracy) | |
{ | |
float i=0; | |
float d =1.0; // d is difference in range numbers according to accuracy | |
float cube; | |
while(accuracy >0) | |
{ d=d/10.0; | |
accuracy--; | |
} | |
for(i=0.0;i<=Number;i+=d) | |
{ | |
cube = i*i*i; | |
if(cube == Number || (cube<(Number + d) && cube >(Number-d))) | |
return i; | |
} | |
return 0; | |
} |
Efficient Method Of Calculating Cube root of any number
If we apply binary search ( If you don’t know about Binary Search, Click here ) to the whole range of possible cubic root, then we can decrease significant loop count.
Analysis Of Algorithm with Binary Search
CubeRoot(3) = 1.44225
For Analysis of this algorithm, let's take boundary case, which is whole range 0 to 3 with 0.00001 which means loop count range is 0 to 300000 times. BUT binary search has Time Complexity of log2 (N) here N=300000.
So
Loop Count of CubeRootUsingBinarySearch(3) = log2 (300000)
= 18.19
~ 19 (Because we want Upper limit)
Now if we compare with former algorithm’s loop count which is 300000 and with binary search we make it 19.Implementation Of Cubic Root with Binary Search in C/C++. These function which is given here can be modified to find Nth root of any number.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Cubic Root with Binary Search | |
Time Complexity : O ( log2 (n) ) | |
where n is range of Possible Cubic roots | |
Space Complexity : O (1) | |
*/ | |
float CubeRootWithBS(float Number , float accuracy) | |
{ | |
float d=1.0 ; // d is difference in range numbers according to accuracy | |
while(accuracy >=0) | |
{ d=d/10; | |
accuracy--; | |
} | |
float l=0.0,u=Number; | |
float mid=(l+u)/2; | |
float cube=mid*mid*mid; | |
while(cube!=Number && (cube>(Number + d) || cube <(Number-d))) | |
{ | |
if(cube<Number) | |
l=mid+d; | |
else | |
u=mid-d; | |
mid=(l+u)/2; | |
cube=mid*mid*mid; | |
} | |
return mid; | |
} |
Comments
Post a Comment