The Ultimate Fast Integer Square Root
Author
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
Quote:Original post by SpoonbenderThat's part of a do...while loop.Quote:Highly optimized code.... [grin]
while (c++ < 25);
return nv;
}
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.
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;}
I have tested your sqrt function with the following code:
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
#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
Author
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
Quote:Original post by Spoonbender
you 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
