4 replies to this topic

[blueone]

Are you looking for fast square root for integer only? Well, dont look further. This code is 99% no other function calls (except abs but i have a faster absolute function in this forum also for better performance) :sneaky: .

unsigned int newt_sqrt(unsigned int input)
{
int nv, v = input>>1, c = 0;
if (!v)
return input;
do
{
nv = (v + input/v)>>1;
if (abs(v - nv) <= 1) // I have an available fast absolute value in this forum. If you have it. use the next one.
//if (absi(v - nv) <= 1)
return nv;
v = nv;
}
while (c++ < 25);
return nv;
}

Hope you like it :worthy: :sneaky:

[.oisyn]

Please post code within [code] tags

[martinsm]

I think binary search would be faster (it doesn't involves division) than Newton iteration.
Or some kind of modification of binary search: http://home.utah.edu...ng/isqrt.c.html

[Nils Pipenbrinck]

:)

A integer square root is - from the complexity point of view - on par with divisions. Infact there are lots of similarities between those two. Your code might run faster on a modern machine, where divisions are fast, but you usually don't need a hand-written integer square root on this machines.

I personally go for the good old fixed iteration step method (see link)

http://astronomy.swi...rke/other/sqrt/

Nevertheless, it's fun to toy around with such problems. I'd personally would like to try out a method that uses interpolation search to find the result. In theory this would get the exact result in 4 iterations for a 32 bit integer (log log N search).

[jjd]

As pointed out on gamedev, your algorithm is slow.