| View previous topic :: View next topic |
| Author |
Message |
truevenik
Joined: 03 Feb 2004
Posts: 5
|
| square roots to the nearest integer, without floating point |
 Posted: Tue Mar 23, 2004 11:57 pm |
 |
|
In case somebody else needs this, here's a routine that computes to the nearest integer the square-root of any unsigned 32-bit integer (eg. isqrt(10) = 3, isqrt(16) = 4 ). I needed this because I didn't have enough memory left to use floating point:
| Code: |
int32 isqrt(int32 x)
{
int32 result = 0;
int8 bit;
for(bit = 15; bit != 0xFF; bit--) //while bit hasn't underflowed
{
bit_set(result, bit); //set the current bit
if(result*result > x) //if this makes the result > sqrt(x)
bit_clear(result, bit); //undo the bit-set
}
return result;
}
|
Note 1: This can be used to compute square roots of fixed point fractions as well - lets say you represent 65.32 as 6532 in your system. You want to compute sqrt(65.32) which will be represented as 100*sqrt(65.32). To do this you compute sqrt(6532*100). The reason 100*sqrt(65.32) is equivalent to sqrt(6532*100) is: 100*sqrt(65.32)= sqrt(100*100)*sqrt(65.32) = sqrt(65.32*100*100)
Note 2: The loop finds result through guess and check (binary search) by guessing result and then checking whether (result^2 > input). If it is then the guess was too big.
Note 3: I think logarithms to the nearest integer can be computed in a similar way: log(in) = result, in = 10^result, 10^result - in = 0. find result via binary-search.
Last edited by truevenik on Sat Apr 03, 2004 10:34 pm; edited 2 times in total |
|
 |
jds-pic
Joined: 17 Sep 2003
Posts: 205
|
|
|
Guest
|
| neat |
| Posted: Wed Mar 24, 2004 1:14 pm |
|
|
Hi, can you explain the idea behind this algorithm (I don't remember learning this in grammar school  ? |
|
|
mvaraujo
Joined: 20 Feb 2004
Posts: 59
Location: Brazil
|
| SQRT of an 32bit integer, posting code. |
| Posted: Tue Nov 30, 2004 7:56 am |
|
|
Hi All,
This message chain is old but I decided to post this code because it is pretty simple and can help other people that need to square a 32bit integer. It's small and fast, the best I've found in my searches until now.
| Code: |
long uisqrt32(int32 r)
{
int32 t,b,c=0;
for (b=0x10000000;b!=0;b>>=2) {
t = c + b;
c >>= 1;
if (t <= r) {
r -= t;
c += b;
}
}
return(c);
}
|
It solved speed issues on my code. In comparison to sqrt() from math.h (float) it takes 1/5 of the run time. |
|
|
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
