Sign in to follow this  
blueone

The Ultimate Fast Integer Square Root

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by blueone
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

But in the title you claim
Quote:

The Ultimate Fast Integer Square Root

and in the post you say
Quote:

Are you looking for fast square root for integer only?

Emphasis mine, of course. If you are aware of your limitations, don't make so strong statements next time.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this