isqrt.legalize.c:

/* Integer square root by Halleck's method, with Legalize's speedup */
long isqrt (x) long x;{
  long   squaredbit, remainder, root;

   if (x<1) return 0;
  
   /* Load the binary constant 01 00 00 ... 00, where the number
    * of zero bits to the right of the single one bit
    * is even, and the one bit is as far left as is consistant
    * with that condition.)
    */
   squaredbit  = (long) ((((unsigned long) ~0L) >> 1) & 
                        ~(((unsigned long) ~0L) >> 2));
   /* This portable load replaces the loop that used to be 
    * here, and was donated by  legalize@xmission.com 
    */

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