isqrt.halleck.c:

/* 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 ...

• Factoring Page
• John Halleck's Home Page

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 January 12th, 2009
And the underlying file was last modified on December 12th, 2005