**Next message:**Andrew Morton: "Re: [PATCH 00/20] generic show_mem() v5"**Previous message:**Dave Jones: "Re: [PATCH] powerpc/ep8248e: Fix compile problem if !CONFIG_FS_ENET"**In reply to:**Soumyadip Das Mahapatra: "Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c"**Next in thread:**Lennart Sorensen: "Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

On Wed, Jul 16, 2008 at 02:35:56PM -0700, Soumyadip Das Mahapatra 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)

ub = m - 1;

else

lb = m + 1;

} while(ub >= lb);

return lb - 1;

}

int main() {

unsigned long i;

unsigned long old;

unsigned long new;

for(i=0;i<10000000;i++) {

old=old_int_sqrt(i);

new=new_int_sqrt(i);

if(new!=old) {

printf("sqrt(%lu)= %lu(new)->%llu %lu(old)->%llu",i,new,(unsigned long long)new*(unsigned long long)new,old,(unsigned long long)old*(unsigned long long)old);

if(llabs((unsigned long long)new*(unsigned long long)new - (unsigned long long)i) < llabs((unsigned long long)old*(unsigned long long)old - (unsigned long long)i)) {

printf(" (new is best)\n");

} else {

printf(" (old is best)\n");

}

}

}

return 0;

}

Example output:

sqrt(9380468)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380469)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380470)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380471)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380472)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380473)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380474)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380475)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380476)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380477)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

sqrt(9380478)= 146574(new)->21483937476 3062(old)->9375844 (old is best)

--

Len Sorensen

--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

the body of a message to majordomo@xxxxxxxxxxxxxxx

More majordomo info at http://vger.kernel.org/majordomo-info.html

Please read the FAQ at http://www.tux.org/lkml/

**Next message:**Andrew Morton: "Re: [PATCH 00/20] generic show_mem() v5"**Previous message:**Dave Jones: "Re: [PATCH] powerpc/ep8248e: Fix compile problem if !CONFIG_FS_ENET"**In reply to:**Soumyadip Das Mahapatra: "Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c"**Next in thread:**Lennart Sorensen: "Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]