: A better approach to compute int_sqrt in lib/int_sqrt.c
Quoted 74 lines
From: Peter Zijlstra <[email protected]>
To: Soumyadip Das Mahapatra <[email protected]>
Cc: [email protected]
Sent: Thursday, July 17, 2008 2:21:09 AM
Subject: Re: [PATCH] : A better approach to computeint_sqrtinlib/int_sqrt.cQuoted 5 lines · Soumyadip Das Mahapatra
Hello everybody !!
The patch below is what i think is a better approach to
computeint_sqrt().What about it ?
Indeed, what about it?
How is it better;
- is it cheaper
- how so
- on what platform- it is more accurate
- who needs itPlease provide a little more information about why you suggest this change.
Quoted 11 lines
Thanks !!
---
lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +0
-1@@ -1,4 +1,3 @@ - #include #includelib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 line 9
Quoted 4 lines
lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +1
-0@@ -7,26 +6,21 @@ * @x: integer of which to calculate the sqrt * * A very rough approximation to the sqrt() function. + * Improved version from the previous one.With the previuos one being gone, this comment adds little but confusion..
Quoted 28 lines
lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +7
-18*/ unsigned long 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 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;
Quoted 8 lines
lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 line 26
Quoted 8 lines
lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +5
-0+ else + lb = m + 1; + } while(ub >= lb); + + return lb - 1; } EXPORT_SYMBOL(int_sqrt);
Thanks Peter for noticing :-)
Sorry, I should have it explained before. Really sorry for that. Here are they...
0 It is better because
o it uses only one loop instead of two
o contains no division operator (older version has two) which are surely comparatively slow task in computer
0 Currently find . -name '*.[ch]' | xargs grep int_sqrt gives me this
....
./fs/nfs/write.c: nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10);
./drivers/video/fbmon.c: h_period = int_sqrt(h_period);
./mm/page_alloc.c: min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
./mm/oom_kill.c: s = int_sqrt(cpu_time);
./mm/oom_kill.c: s = int_sqrt(int_sqrt(run_time));
....So this function works in critical computing sections like frame-buffer, paging. Which means betterment of this function should not be ignored. Besides, if there is a better way to do things then why should not we do that ?
Anyways thanks :-)
Quoted 17 lines · Soumyadip Das Mahapatra
Thanks Peter for noticing :-)
Sorry, I should have it explained before. Really sorry for that. Here are they...0 It is better because
o it uses only one loop instead of two
o contains no division operator (older version has two) which are surely comparatively slow task in computer0 Currently find . -name '*.[ch]' | xargs grep
int_sqrtgives me this.... ./fs/nfs/write.c: nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10); ./drivers/video/fbmon.c: h_period = int_sqrt(h_period); ./mm/page_alloc.c: min_free_kbytes = int_sqrt(lowmem_kbytes * 16); ./mm/oom_kill.c: s = int_sqrt(cpu_time); ./mm/oom_kill.c: s = int_sqrt(int_sqrt(run_time)); ....
Quoted 5 lines
So this function works in critical computing sections like frame-buffer, paging. Which means betterment of this function should not be ignored. Besides, if there is a better way to do things then why should not we do that ?
Anyways thanks :-)
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)
Signature · 1 line
Len Sorensen
Quoted 39 lines · Lennart Sorensen
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_LONG32unsigned 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; }
Quoted 7 lines
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.
Quoted 8 lines
ub = m - 1; else lb = m + 1; } while(ub >= lb); return lb - 1; }
Signature · 1 line
Len Sorensen
Quoted 31 lines · Soumyadip Das Mahapatra
Quoted 31 lines
Quoted 31 lines
*/
unsigned longint_sqrt(unsigned long x)
{(quoted diff) +10
-18- 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 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);
Quoted 8 lines
Quoted 4 lines
Review
Quoted 4 lines
(quoted diff) +2
-0+ + return lb - 1; } EXPORT_SYMBOL(int_sqrt);0 It is better because
o contains no division operator (older version has two) which are surely comparatively slow task in computer
Actually, the old version has zero division operators; those are simply right-shifts.
-- Vadim Lobanov
Quoted 17 lines · Soumyadip Das Mahapatra
Thanks Peter for noticing :-)
Sorry, I should have it explained before. Really sorry for that. Here are they...0 It is better because
o it uses only one loop instead of two
o contains no division operator (older version has two) which are surely comparatively slow task in computer0 Currently find . -name '*.[ch]' | xargs grep
int_sqrtgives me this.... ./fs/nfs/write.c: nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10); ./drivers/video/fbmon.c: h_period = int_sqrt(h_period); ./mm/page_alloc.c: min_free_kbytes = int_sqrt(lowmem_kbytes * 16); ./mm/oom_kill.c: s = int_sqrt(cpu_time); ./mm/oom_kill.c: s = int_sqrt(int_sqrt(run_time)); ....
Quoted 5 lines
So this function works in critical computing sections like frame-buffer, paging. Which means betterment of this function should not be ignored. Besides, if there is a better way to do things then why should not we do that ?
Anyways thanks :-)
So so far the line:
if((m * m) > x)
overflows easily in which case the result is wrong.
Also at least on my Athlon 2500, this new algorithm takes 3.5 times longer than the old one to get result when doing all square roots from 0 to 200000000, which is no improvement.
Signature · 1 line
Len Sorensen
Quoted 4 lines · Soumyadip Das Mahapatra
0 It is better because
o it uses only one loop instead of two
o contains no division operator (older version has two) which are surely comparatively slow task in computer
As Lennart has said, gcc is smart enough to transform a division by a power-of-two into shifts.
Quoted 8 lines
0 Currently find . -name '*.[ch]' | xargs grep
int_sqrtgives me this.... ./fs/nfs/write.c: nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10); ./drivers/video/fbmon.c: h_period = int_sqrt(h_period); ./mm/page_alloc.c: min_free_kbytes = int_sqrt(lowmem_kbytes * 16); ./mm/oom_kill.c: s = int_sqrt(cpu_time); ./mm/oom_kill.c: s = int_sqrt(int_sqrt(run_time)); ....
fs/nfs/write.c is init codemm/page_alloc.c is also init codemm/oom_kill.c isn't a hot path
which leaves the fbmon case, which after a quick peek is setup code, so not a hot path either.
So while that doesn't preclude us from changing it if you can indeed show its a better implementation, its not on anybodies hit-list.