Integer Based Square Root.

[Daid]

I need to do some integer based squareroots in the game I'm making. I currently use this code:

int INTsqrt(int a)
{
  int square = 1;
  int delta = 3;
  while(square <= a)
  {
	square += delta;
	delta += 2;
  }
  return (delta/2 - 1);
}

But my input is usualy around 0x100 to 0x10000 (never negative, no input checking needed), at that point this code might get a bit slow. There has to be some smart math way to do it alot faster, but I cannot find it. Any clues?
(Cannot use a lookup table, sometimes it goes all the way up to 0x10000000)

 

[Squidge]

Have a look here:

http://citeseer.ist.psu.edu/soderquist95areaperformance.html

and here:

http://www.ma.man.ac.uk/~higham/

 

[rabidcow]

http://www.google.com/search?q=integer+square+root+arm

Right now the top link is http://www.finesse.demon.co.uk/steven/sqrt.html, which has some cool ARM ASM and C code.

 

[Daid]

Thx. I needed an easy upgrade, ofcourse it could be done in pure ASM, but that would be a bit overkill in my case (it's not a huge bottleneck, and gives windows compile problems if I did ASM)

This code:

#define iter1(N) \
	Try = root + (1 << (N)); \
	if (n >= Try << (N))   \
	{   n -= Try << (N);   \
		root |= 2 << (N); \
	}

int INTsqrt(int n)
{
	int root = 0, Try;
	iter1 (15);	iter1 (14);	iter1 (13);	iter1 (12);
	iter1 (11);	iter1 (10);	iter1 ( 9);	iter1 ( 8);
	iter1 ( 7);	iter1 ( 6);	iter1 ( 5);	iter1 ( 4);
	iter1 ( 3);	iter1 ( 2);	iter1 ( 1);	iter1 ( 0);
	return root >> 1;
}

(That I found on one of the links) works great. And said to be optimize to 4 cycles per bit that's probly a whole lot faster then my old methode.

 

[dmitrygr]

here is a 55 cycle total routine

#define ITER0()						\
									\
	CMP	R0,R2;					\
	SUBHS  R0,R0,R2;				\
	ADC	R2,R1,R2, LSL #1;


#define ITER(i)						\
									\
	CMP	R0,R2,ROR #(2 * i);		\
	SUBHS  R0,R0,R2, ROR #(2 * i);	\
	ADC	R2,R1,R2, LSL #1;

asm UInt32 sqrt(UInt32 v){			//fast sqrt of integer (55 instructions + bx lr)
	
	CMP   R0,#0					//this routine does not like zero as input, so we check for that
	BXEQ  LR
	
	MOV   R1,#3 << 30
	MOV   R2,#1 << 30
	
	ITER0()
	ITER(1)
	ITER(2)
	ITER(3)
	ITER(4)
	ITER(5)
	ITER(6)
	ITER(7)
	ITER(8)
	ITER(9)
	ITER(10)
	ITER(11)
	ITER(12)
	ITER(13)
	ITER(14)
	ITER(15)
	
	BIC	R2,R2, #3 << 30
	CMP	R0,R2
	ADC	R0,R2,#0
	BX	 LR
}

#undef ITER
#undef ITER0

 

[Blah]

^^ Thats ASM, dude.

What I'd do is something like this:

#ifdef WIN32
//or "ifndef GP2X", or etc.

Uint32 isqrt(Uint32 v) {
//use generic square root command
//return value
}

#endif

#ifdef GP2X
//or "ifndef WIN32", or etc.

Uint3D isqrt(Uint32 v) {
//use asm square root command
//return value
}
#endif