lonesock

05-22-2008, 12:56 AM

Hi, All.

I came up with a quick & simple integer sqrt function targeting the propeller (just got my 1st protoboard!!). It does not require multiplication, using only bit-shifts (for those not familiar with C notation, a<<1 = a*2, and a>>2 = a/4) and addition and minimal branching. I can't write assembly yet, so I'll just post the C version I used for testing on my desktop. This may already be a standard way of computing integer square roots, but I did not find anything related when doing a quick Google search. Enjoy!

/*

Jonathan "lonesock" Dummer

Successive Approximation Integer Square Root

2008-05-21-10.24

Features:

* simple

* scalable input range

* no multiply, just bitshift, add, sub, and minimal branching

* developed for the Parallax Propeller chip

*/

const int sqrt_input_bits = 16;

int ls_sqrt( int n )

{

/* my eventual answer */

int x = 0;

/* start with the highest (output) bit and work down */

for( int b = (sqrt_input_bits>>1)-1; b >= 0; --b )

{

/*

the difference between x^2 now, and if I add (1<<b) to x is:

(x + (1<<b))^2 - x^2

x^2 + 2*x*(1<<b) + (1<<b)^2 - x^2

((x+x)<<b) + (1<<(b+b))

(x+x+(1<<b))<<b

*/

int dx2 = ((1<<b)+x+x)<<b;

/* is n large enough to handle the delta in x^2? */

if( n >= dx2 )

{

/* if so, remove it from n */

n -= dx2;

/* and add this bit into x */

x += 1 << b;

}

}

/* and the winner is... */

return x;

}

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

lonesock

Piranha are people too.

I came up with a quick & simple integer sqrt function targeting the propeller (just got my 1st protoboard!!). It does not require multiplication, using only bit-shifts (for those not familiar with C notation, a<<1 = a*2, and a>>2 = a/4) and addition and minimal branching. I can't write assembly yet, so I'll just post the C version I used for testing on my desktop. This may already be a standard way of computing integer square roots, but I did not find anything related when doing a quick Google search. Enjoy!

/*

Jonathan "lonesock" Dummer

Successive Approximation Integer Square Root

2008-05-21-10.24

Features:

* simple

* scalable input range

* no multiply, just bitshift, add, sub, and minimal branching

* developed for the Parallax Propeller chip

*/

const int sqrt_input_bits = 16;

int ls_sqrt( int n )

{

/* my eventual answer */

int x = 0;

/* start with the highest (output) bit and work down */

for( int b = (sqrt_input_bits>>1)-1; b >= 0; --b )

{

/*

the difference between x^2 now, and if I add (1<<b) to x is:

(x + (1<<b))^2 - x^2

x^2 + 2*x*(1<<b) + (1<<b)^2 - x^2

((x+x)<<b) + (1<<(b+b))

(x+x+(1<<b))<<b

*/

int dx2 = ((1<<b)+x+x)<<b;

/* is n large enough to handle the delta in x^2? */

if( n >= dx2 )

{

/* if so, remove it from n */

n -= dx2;

/* and add this bit into x */

x += 1 << b;

}

}

/* and the winner is... */

return x;

}

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

lonesock

Piranha are people too.