Messages in this thread | | | Date | Thu, 17 Jul 2008 14:00:09 -0400 | Subject | Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c | From | (Lennart Sorensen) |
| |
On Wed, Jul 16, 2008 at 06:05:56PM -0400, Lennart Sorensen wrote: > It is also very inaccurate: > > int_sqrt(9380489) returns 3062 with the old code and 146574 with the new > code. I wonder which one is closer to right. It seems as soon as the > input is 2^22 or higher, the new code goes all to hell and starts > returning 2^16-1 or similarly silly values rather than 2^11-1 or > similar. > > Here is how I tested: > > (compiled with gcc -Wall -O2 -std=c99) > > #include <stdio.h> > #include <unistd.h> > #include <stdlib.h> > > #define BITS_PER_LONG 32 > > unsigned long old_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 = op - (res + one); > res = res + 2 * one; > } > res /= 2; > one /= 4; > } > return res; > } > > unsigned long new_int_sqrt(unsigned long x) { > unsigned long ub, lb, m; > lb = 1; /* lower bound */ > ub = (x >> 5) + 8; /* upper bound */ > do { > m = (ub + lb) >> 1; /* middle value */ > if((m * m) > x) This line overflows while the result is good if changed to: if(((unsigned long long)m * (unsigned long long)m) > (unsigned long long)x)
Perhaps there is a better way to do this.
> ub = m - 1; > else > lb = m + 1; > } while(ub >= lb); > > return lb - 1; > } >
-- Len Sorensen
| |