OK, under normal circumstances this is something I would use search for I''ve been happily using sqrt in my programs since I began programming in C++, but I''ve recently read stuff claiming its terribly slow. Unfortunately, none of these sources could agree on one good alternative. Is sqrt really that bad? And if so, what is commonly used instead? PS. Yes, I googled, but all I found was assembly, gulp (I should put that on a t-shirt )

---

pan narrans
Study + Hard Work + Loud Profanity = Good Code

Use a lookup table, if you want speed. There is no way to do a square root fast "the real way".

EDIT: What sort of values are you working with? floats, 0 << x << 1, integers?

[edited by - CWizard on September 24, 2002 12:38:28 PM]

The big problem with a lookup table is that it can cause a lot of processor data cache misses. For very expensive operations like sqrt this can still be a better choice, but sometimes making a LUT for something just because it''s possible can actually be a slowdown.

---

Helpful links:
How To Ask Questions The Smart Way | Google can help with your question | Search MSDN for help with standard C or Windows functions

quote:

---

Original post by siaspete
The big problem with a lookup table is that it can cause a lot of processor data cache misses. For very expensive operations like sqrt this can still be a better choice, but sometimes making a LUT for something just because it''s possible can actually be a slowdown.

---

Well, you can always configure it to not cache the lookup table.

I use it for float a couple of times in my collision detection library, specifically calculating vector magnitude, and ray/sphere intersections.

Since it probably gets called five - ten times per mesh face when checking for collisions each frame I wondered whether I would get much of a speed boost using another method.

I also have a pedantic need to always try to use the best possible algorithms

[EDIT] - better estimate

---

pan narrans
Study + Hard Work + Loud Profanity = Good Code

[edited by - pan narrans on September 24, 2002 12:58:18 PM]

Hmm, I think the idea is to have it cached so that its fast. And I would like to know just how it is possible to configure memory that is -not to be cached-

How accurate must the result be? Do you know between which values you''re sqrt()ing on?

_Stinger, I don''t remember how, but I read that the newest processors support you to disable the cache for some address range, or perhaps it just was to disable the cache all together. Check Intel''s site about Pentium 4.

Given that its for collision I want it to be as accurate as possible, and I don''t know the values before hand so a LUT is probably not going to be much use.

Sqrt is workin fine, and seeing as I want the precision its probably worth it. Just wondered if their was some much faster way of doing it that everyone was keepin under their hats

---

pan narrans
Study + Hard Work + Loud Profanity = Good Code

You''ve probably looked into it already, but are you sure you need all those sqrts? When I did a ray-sphere intersection thingy, at least one of the sqrts was redundant - the value was squared again before using it, or something. It''s been a while since I''ve thought about it though .

Miles

As said, it depends a lot on how accurate you want the sqrt to be. ID software had a nice hack in the q2-code, check it out.
Also, I think you''re doing quite a lot of detection, when you need all those sqrts per face. You better reconsider the design of your collision detection code!