wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> How to compute the square root of an integer?
        
(Message started by: cuckoo on Jul 14th, 2007, 2:08am)
Title: How to compute the square root of an integer?
Post by cuckoo on Jul 14th, 2007, 2:08am
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! ;D

/**
* 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;
}
Title: Re: How to compute the square root of an integer?
Post by coder@heart on Jul 14th, 2007, 10:01am
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));
}
}
Title: Re: How to compute the square root of an integer?
Post by KWillets on Jul 16th, 2007, 11:52am
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.
Title: Re: How to compute the square root of an integer?
Post by Aryabhatta on Jul 16th, 2007, 12:03pm

on 07/14/07 at 10:01:39, 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).
Title: Re: How to compute the square root of an integer?
Post by Barukh on Jul 19th, 2007, 11:33pm
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 (http://www.embedded.com/98/9802fe2.htm).

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


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board