lkml.org 
[lkml]   [2008]   [Jul]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c
From
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


\
 
 \ /
  Last update: 2008-07-17 20:03    [from the cache]
©2003-2011 Jasper Spaans