integer square roots

simply do this:

int iResult = (int)sqrt(value);

There is no faster way to get square roots. Thats why you should avoid using them when possible

PUTZ!! what a dumb!
I'm talkin' about algorithms... (that formula i know)

[edited by - akiinao on June 5, 2002 3:52:49 PM]

quote:

---

Original post by Kern
simply do this:

int iResult = (int)sqrt(value);

There is no faster way to get square roots. Thats why you should avoid using them when possible

---

dat was se pratty dumb thang to says!

Of coarse there are faster ways of getting integer square roots! And your crazy hungarian notation of iResult makes me want to vomit!

Try http://www.numbertheory.org/calc/krm_calc.html, I think they might have what your looking for!

Sheesh, welcome to the forums, Kern!

You didn''t say you were looking for an algorithm, akiinao.

http://www.azillionmonkeys.com/qed/sqroot.html

Thanks to everyone who provided constructive responses to akiinao''s post.

I admire Richard Feynman, the late physicist who, in his own words, was a "curious character." I''ve read some of his memoirs, and it seems that a few other rather famous scientists (including, I think, Fermi) would always ask Richard questions even when he was a lowly student and they were noble prize-winning famous big-time scientists. Why, you ask? Because Richard didn''t know he was supposed to bow down and worship they ground that they walked on. While their lesser professional peers would generally agree with their theories, Richard would always be honest, telling the big-guys when he thought they were full of shit. They appreciated his honesty! I do imagine that he was fairly courteous to them, though! I guess he probably never called them "dumbass!"

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

quote:

---

Original post by grhodes_at_work
I guess he probably never called them "dumbass!"

---

eehehheehe, I can hear it through the sands of time:
"Fermi, you're such a dumbass. I can't believe I hang around with ghey guys like you - like bombarding uranium with inert neurons will make anything special happen, I don't care how fast... OH MY GOD"


Magmai Kai Holmlor

"Oh, like you've never written buggy code" - Lee


[edited by - Magmai Kai Holmlor on June 5, 2002 7:22:30 PM]

I really liked the play about him, Q.E.D., did anyone else see that? Very good play!

Oh, and I diddn''t mean to sound stuck up about integral algorithms, I was saying it in a joking sense. You really think I''d make fun of hungarian notation? .bSen

thanx guys.
i''ll read that links
;-)

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