http://medialab.freaknet.org/martin/src/sqrt/sqrt.c
I compared it to the normal sqrt() function included in the IDE, and to one other routine I found online, and it was about 10x faster than both in average.
It works perfectly good for 32bit integers, returning another integer. Not useful if you need floating point, but if you don’t need more precision than integers (like calculating coordinates in a display, there is no need for decimals), and you calculate a lot of square roots, it may provide some speed improvement to your code.
To compare the speed of each routine I calculated all the square root from 1.000.000 to 1. I could have gone higher, to 4.000.000.000, but it would take a lot of time to calculate it all.
When I have a working mini again, I will test with a few ranges, to see if the speed improvements compared to the standard sqrt function are mostly on certain bit lengths, as the speed depends on the size of the number.
This is the code, but is in that webpage too:
uint16_t asqrt(uint32_t x) {
/* From http://medialab.freaknet.org/martin/src/sqrt/sqrt.c
* Logically, these are unsigned. We need the sign bit to test
* whether (op - res - one) underflowed.
*/
int32_t op, res, one;
op = x;
res = 0;
/* "one" starts at the highest power of four <= than the argument. */
one = 1 << 30; /* second-to-top bit set */
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 (uint16_t) (res);
}
Your algorithm and others are well explained here:
http://www.codecodex.com/wiki/Calculate … quare_root
Please consider that the algorithm was conceived avoiding multiplication. Today even the AVR has a HW MULT. So there are other algorithms that may win. If your code frame is ready for testing you might test this one:
unsigned int sqrt32(unsigned long n)
{
unsigned int c = 0x8000;
unsigned int g = 0x8000;
for(;;) {
if(g*g > n)
{
g ^= c;
}
c >>= 1;
if(c == 0)
{
return g;
}
g |= c;
}
}
unsigned int sqrt32(unsigned long n)
{
unsigned int c = 0x8000;
unsigned int g = 0x8000;
for(;;) {
if(g*g > n) {
g ^= c;
}
c >>= 1;
if(c == 0) {
return g;
}
g |= c;
}
}
Glad it helped. I took it from the link above and I did not test it with real code to be true.
Your remark about int or long is interesting. I will have to check it. What means “…worked better..” exactly?
@Roger: Next time I will use proper formatting
This is where I caution users of such algorithms to build test cases for their data and to carefully and extensively test to ensure the data set is resolved accurately within the operational boundaries of their project. I cannot stress enough that bad results are quickly received when an algorithm go astray.
Ray
Bunch of routines there that implement fixed point math for you. I’ve compiled that on the msp430 which has very slow floating point routines and got pretty nice results.
-rick
I don’t like at all the (new?) licence. So, Ray, you’re right!
