Archived

This topic is now archived and is closed to further replies.

integer square roots

This topic is 5666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

do you guys know a fast method to find integer square roots? i mean sqrt(10) = 3. P.S: editing for correcting gammar mistakes [edited by - akiinao on June 10, 2002 5:25:14 PM]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites