From b98f7895180818a0737d59d60d8e81d729f4ea46 Mon Sep 17 00:00:00 2001 From: FlyFrog Date: Wed, 4 Sep 2013 12:45:44 +0700 Subject: int_sqrt: Improve 3x faster integer sqrt. Result on 10,000,000 call. Old: sqrt(12345689) = 3513 real 0m0.768s user 0m0.760s sys 0m0.004s New: sqrt(12345689) = 3513 real 0m0.222s user 0m0.224s sys 0m0.000s Signed-off-by: engstk --- lib/int_sqrt.c | 28 +++++++++++++--------------- 1 file changed, 13 insertions(+), 15 deletions(-) (limited to 'lib') diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index 0814f0762..5c3916d09 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -14,34 +14,32 @@ * * A very rough approximation to the sqrt() function. */ -unsigned long int_sqrt(unsigned long x) +inline unsigned long int_sqrt(unsigned long x) { - unsigned long tmp; - unsigned long place; - unsigned long root; - unsigned long remainder; + register unsigned long tmp; + register unsigned long place; + register unsigned long root = 0; if (x <= 1) return x; - root = 0; - remainder = x; place = 1UL << (BITS_PER_LONG - 2); - - while (place > remainder) + + do{ place >>= 2; + }while(place > x); - while (place != 0) { + do { tmp = root + place; + root >>= 1; - if (remainder >= tmp) + if (x >= tmp) { - remainder -= tmp; - root += (place << 1); + x -= tmp; + root += place; } - root >>= 1; place >>= 2; - } + }while (place != 0); return root; } -- cgit v1.2.3