Most of time I came across the process where I need to find the integer square root of a number. So I thought about writing a blog on finding integer square root.
Integer square root is a root of number whose square is less than or equal to the given number. If given number of perfect square then square of integer square root is equal to the number. In all ither cases it will smaler than the given number.
By naive method we will require O(n) time for finding integer square root
Using newton raphson's method, it can be done in very efficient manner.
First we will do a initial guess for the square root and then try to make it more accurate progressively.
int intSqrt(int n) {
int start = n/2;
int root = start;
do {
root = start;
start = (start+(n/start)) / 2;
cout << root << " " << start << endl;
}while(start < root);
return root;
}
Integer square root is a root of number whose square is less than or equal to the given number. If given number of perfect square then square of integer square root is equal to the number. In all ither cases it will smaler than the given number.
By naive method we will require O(n) time for finding integer square root
Using newton raphson's method, it can be done in very efficient manner.
First we will do a initial guess for the square root and then try to make it more accurate progressively.
int intSqrt(int n) {
int start = n/2;
int root = start;
do {
root = start;
start = (start+(n/start)) / 2;
cout << root << " " << start << endl;
}while(start < root);
return root;
}
