In response to the orginal question...I don't know of any integer square root algorithms, HOWEVER I have found sqrt() to be extremely fast...much faster than any integer approximation function that I tried to write (I was optimizing a prime number generator in a friendly competition with a friend...). In fact I don't really think you CAN get any faster than sqrt() because the math co-processor has a built in sqrt machine instruction and I suspect that any intelligent compiler will replace a call to sqrt() with this single machine instruction...well okay there would be one or two other instructions to push the argument onto the co-processor stack, but any function you write will have stack overhead too so in my opinion I don't think you can do better at a software level. So I agree with Senses777 (btw is that a Unix permissions joke?...) that is probably the fastest you can do in C for integer square roots.

[edited by - bob_the_third on June 6, 2002 10:28:55 PM]

If speed is important, and you have all the memory you need, construct a table of squares, and then bsearch it for the lesser square. I don''t know if it''s neccessarily faster than the included squareroot functions supplied with the standard C library, but it''s adjusting the work into code you probably do know how write and optimize.

-> Will Bubel
-> Machine wash cold, tumble dry.

I read Richard Feynman''s auto-biography, and it was one of the best read''s I''ve had. He was such an interesting guy, a bit of a "wide boy" I liked how he was just generally really intelligent ( like how he got into breaking locks and stuff like that - completely unrelated to theoretical physics ).

Death of one is a tragedy, death of a million is just a statistic.

I think what Kern was trying to say that with the current memory/CPU bandwidth ratio, the memory lookup and possible pipeline stalls associated with constructing an algorithm to calculate a square root, fsqrt is usually faster, when not using SIMD instructions. As memory access frequency increases, this may no longer be the case.

simple method of calculating squares:
int square = num*num;

i think you are search for square roots, not squares.

thanx...
i got a routine named fred_sqrt in [http://www.azillionmonkeys.com/qed/sqroot.html.
i dunno if thatz faster than (int) sqrt(n), but itz pretty fast!

use a look up table maybe?
Yratelev