Originally Posted by
anon
You could also write your own sqrt (approximation - int precision is enough) which is guaranteed to suit the algorithm.
Or perform a binary search on the range.
Yep, I've found that method to be effective as well. Another thing you can do is optimize the search range, such that it is already quite close to the actual square root. This implementation calculates the largest power of two needed to contain the root, eg: if N = 1234 then H (high) = 128... since the actual root is 111, H is obviously a pretty close initial guess. It might be improved upon by working out the minimum lower-bound as well, although I'm not sure that it's really worth the effort! It seems to run faster than the Newton-Raphson, AFAICT.
Code:
size_t isqrt( size_t val )
{
size_t const
one = 1;
size_t
div,
res,
low = one,
hig = one,
tmp = val;
if( !val )
return val;
while( tmp >>= one )
++hig;
hig = one << ( ( hig + ( hig & one ) ) >> one );
for( ;; )
{
res = low + ( ( hig - low ) >> one );
div = val / res;
if( div < res )
{
if( hig == res )
break;
hig = res;
}
else if( div > res )
{
if( low == res )
break;
low = res;
}
else
break;
}
return res;
}