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

##### Share on other sites
Quote:
 Original post by blueonei 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.