# The Ultimate Fast Integer Square Root

This topic is 4423 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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) . 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

##### Share on other sites
How does this compare to other sqrt() functions?

##### Share on other sites
Quote:
 while (c++ < 25);return nv;}

Highly optimized code.... [grin]

##### Share on other sites
Quote:
Original post by Spoonbender
Quote:
 while (c++ < 25);return nv;}
Highly optimized code.... [grin]
That's part of a do...while loop.

##### Share on other sites
doh, just woke up. I'm allowed to misread code... [lol]

##### Share on other sites
Again not good, at least there's a reason to try and improve integer sqrt(), unlike your abs() attempt.

For improving sqrt(), see here.

In particular, this implementation (assumes a modern 32-bit CPU with a deep pipeline and fast FPU, ie. a standard desktop PC). I modified it slight to be more C++-ish.

int32_t sqrt(int32_t r)
{
float x;
float rr = r;
float y = rr*0.5;
*(unsigned int*)&x = (0xbe6f0000 - *(uint32_t*)&rr) >> 1;

x = (1.5f*x) - (x*x)*(x*y);
if(r>101123) x = (1.5f*x) - (x*x)*(x*y);

int32_t is = (int32_t)(x*rr + 0.5f);
return is + (r - is*is)>>31;
}

##### Share on other sites
I have tested your sqrt function with the following code:
#include <stdio.h>
#include <math.h>
#include <windows.h>

#pragma comment(lib,"winmm.lib")

unsigned int sqrti(unsigned int input)
{
return((unsigned int)sqrt((double)input));
}
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;
}
void main()
{
DWORD t1,t2;
t1=timeGetTime();
for(unsigned int i=0;i<=1000000;i++) newt_sqrt(i);
t2=timeGetTime();

printf("dt = %d ms\n",t2-t1);

t1=timeGetTime();
for(unsigned int i=0;i<=1000000;i++) sqrti(i);
t2=timeGetTime();

printf("dt = %d ms\n",t2-t1);

}

Here the results:
dt = 375 ms
dt = 46 ms

newt_sqrt is much slower than sqri.

I have compiled the code with the following options using MSVC2005:
/Od /Ob1 /Ot /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Fo"Release\\" /Fd"Release\vc80.pdb" /W3 /nologo /c /Wp64 /Zi /TP /errorReport:prompt

##### Share on other sites
you didn't try with joanusdmentia's version too?

##### Share on other sites
hehe, i just want to share an implementation of my simple integer square root function W/O using any other functions except abs which i have myself. i know its slow just want to show to people that i can do simple things like this w/o functions T_T. but im not shy to accept my code's slowness because im only 16 years old hehehe

##### Share on other sites
Quote:
 Original post by Spoonbenderyou didn't try with joanusdmentia's version too?

I wouldn't really call it mine. Hell, I probably broke it in some subtle way while C++-ifying it [rolleyes]. If I did, check the link for the original.

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002141
×