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    [W:0.021 / U:2.704 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site