/* Integer square root by Halleck's method */
long isqrt (x) long x;{
long squaredbit, remainder, root;
if (x<1) return 0;
/* We really want to load the binary constant 01 00 00 ... 00,
* (There must be an even number of zeros to the right
* of the single one bit, and the one bit as far to the
* left as can be done within that constraint)
* but we don't portably know the word size. But it must
* be at least as long as the argument we were handed.
* So we will compute that size. If you know your word size,
* Then replace this loop with a load of squaredbit with
* the constant.
*/
remainder = x>>2; squaredbit = 1;
while (remainder > 0) {
remainder >>= 2;
squaredbit <<= 2;
}
/* Form bits of the answer. */
remainder = x; root = 0;
while (squaredbit > 0) {
if (remainder >= (squaredbit | root)) {
remainder -= (squaredbit | root);
root >>= 1; root |= squaredbit;
} else {
root >>= 1;
}
squaredbit >>= 2;
}
return root;
}

# Go to ...

This page is http://www.cc.utah.edu/~nahaj/factoring/isqrt.halleck.c.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on December 24th, 2013