Author |
Topic: How to compute the square root of an integer? (Read 790 times) |
|
cuckoo
Junior Member
Gender: 
Posts: 57
|
 |
How to compute the square root of an integer?
« on: Jul 14th, 2007, 2:08am » |
 Quote  Modify
|
The following code computes the integer square root of an integer, which comes from linux source. But I can not figure out how it works. Can somebody explain it to me please? Thank you! 
/**
* int_sqrt - rough approximation to sqrt
* @x: integer of which to calculate the sqrt
*
* A very rough approximation to the sqrt() function.
*/
#defineBITS_PER_LONG(sizeof(unsigned long)<<3)
unsigned long int_sqrt(unsigned long x)
{
unsigned long op, res, one;
op = x;
res = 0;
one = 1UL << (BITS_PER_LONG - 2);
while (one > op)
one >>= 2;
while (one != 0) {
if (op >= res + one) {
op -= (res + one);
res += (one<<1);
}
res >>= 1;
one >>= 2;
}
return res;
}
|
|
 IP Logged |
|
|
|
coder@heart
Newbie
Gender:
Posts: 14
|
|
Re: How to compute the square root of an integer?
« Reply #1 on: Jul 14th, 2007, 10:01am » |
Quote Modify
|
How about solving sqrt as a search algorithm. Have a look at this Java program that computes square root correct to 14th decimal place by 'guess-work'!
Code:
public class Sqrt {
public double sqrt(double x) {
double guess = x/2;
while(Math.abs(x-guess*guess) > 1e-14) {
//if guess is deviant then x/guess will correct it and vice versa
guess = (guess + x/guess)/2;
}
return guess;
}
public static void main(String args[]) {
System.out.println(new Sqrt().sqrt(9));
}
} |
|
|
|
IP Logged |
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: How to compute the square root of an integer?
« Reply #2 on: Jul 16th, 2007, 11:52am » |
Quote Modify
|
A common technique for int square root is to find the most significant bit first and then add 1 bits from left to right (msb to lsb) if they don't cause the square of the root estimate to exceed x. The root estimate in this process is monotone increasing, and since each iteration adds one bit, it's a binary search.
If you maintain the root estimate r, and the current "bit of interest" b as an int with a single 1 digit, then (r+b)^2 = r^2 + 2rb + b^2. These terms are usually kept as running totals, and bitshifts are used to iterate through 2rb and b^2 with no multiplications. So on each iteration, b >>= 1, and b^2 >>= 2, etc.
In this case they seem to be doing a fancy register-saving equivalent where r is left-shifted at the beginning to look like the square of the msb in the result. I believe on each iteration res is 2rb (which is just r shifted left by some amount), and "one" is b^2 as above. The difference between x and the square of the estimate is maintained in op.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: How to compute the square root of an integer?
« Reply #3 on: Jul 16th, 2007, 12:03pm » |
Quote Modify
|
on Jul 14th, 2007, 10:01am, coder@heart wrote:How about solving sqrt as a search algorithm. Have a look at this Java program that computes square root correct to 14th decimal place by 'guess-work'!
Code:
public class Sqrt {
public double sqrt(double x) {
double guess = x/2;
while(Math.abs(x-guess*guess) > 1e-14) {
//if guess is deviant then x/guess will correct it and vice versa
guess = (guess + x/guess)/2;
}
return guess;
}
public static void main(String args[]) {
System.out.println(new Sqrt().sqrt(9));
}
} |
|
|
|
It is not exactly guess-work!
There is theory behind it.
The sequence xn+1 = (xn + M/xn)/2
converges to sqrt(M).
|
| « Last Edit: Jul 16th, 2007, 12:03pm by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: How to compute the square root of an integer?
« Reply #4 on: Jul 19th, 2007, 11:33pm » |
Quote Modify
|
The tecnique outlined by Kwillets is a basis for an iterative algorithm for square root calculation that dates back to Euclid times. Some of us, probably, learned it in high school. For more detail, you may refer to the “High-School Algorithm” section in J. Crenshaw’s overview.
The following example demonstrates how the linux elegant code implements this ancient algorithm.
On the left, the calculation of square root of 121 = 11110012 is performed. On the right, the values of the variables in the code at the beginning of each main loop iteration are given. The result (given at the end in res variable, or read vertically from the 'b' column) is 10112 = 11.
4r b x iter op one res
1 11 10 01 1 01 11 10 01 01 00 00 00 00 00 00 00
1 1 00 00 00
----------
11 10 01 2 00 11 10 01 00 01 00 00 01 00 00 00
100 0 00 00 00
----------
11 10 01 3 00 11 10 01 00 00 01 00 00 10 00 00
1000 1 10 01 00
----------
1 01 01 4 00 01 01 01 00 00 00 01 00 01 01 00
10100 1 1 01 01
----------
0 00 00 00 00 00 00 00 00 00 00 10 11
|
| « Last Edit: Jul 19th, 2007, 11:38pm by Barukh » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print