Why square root is expensive?

Performing a square root is expensive because it''s a complex operation. Compare working a square root in long hand to doing addition. Obviously doing a square root takes more work than doing addition.

From what I understand, the way most calcluators and computer CPU''s calculate the square root by using Newton''s method, which is based on simple differential calculus. To go through this process, you must "guess" a starting point, then do a couple addition, mulitplications, and derivatives. This process can be very time consuming if you want a very high(double) precision, as the method is recursive(in nature, not necessarily best implemented recursively). Basically you are trying to solve for the root of the sqrt() using a linear function that you can solve by picking a point, applying newton''s method, ending up an a point on the other side of the root, and constantly applying newton''s method until you reach the desired precision. Hope this helps...

Every once in a while I see a post here or elsewhere about a faster square root function that uses a magic number on a float cast as an int (it''s actually an inverse sqrt function). It is pretty interesting, might be worthwhile to search for.

Square roots are one of those things you learn in school but they never tell you how to actually manually calculate it. We just plug & chug it into our calculators. I remember an old math teacher telling us when he was in school, if there was a square root in a problem it was a non-trivial thing because they only could use a pencil and paper and write out Newton''s Method.

I believe SSE instructions give you the choice of a full accurate square root, or a 1/sqrt approximation. The full sqrt takes a huge amount of time (like 50 cycles or something), while the appoximation takes just a few cycles. Often you''ll want 1/sqrt, but even if you have to invert it back to a sqrt, it''s still MUCH faster to use the approximation than the full sqrt. More math libraries should give you the option of "close enough" if it can shave off precious cycles.

quote:

---

Original post by Anonymous Poster
He was so old they didn''t have slide rules? Hmmm? Very fast and easily accurate to 3 sig figs if you had a medium-big one. I guess you could get even more accuracy on a bigger one. Ah, the lost art of using a slide rule. They made you understand logarithms too.

---

Weirdly enough, I used one in primary school. We also used tables of logarithms and other functions (to four significant figures, so they were called "four-figure tables") in primary and secondary school.

quote:

---

Originally posted by the Other Anonymous Poster
Be careful: square root is "expensive" in that it takes many more cycles than a typical 1-cycle instruction. But we''re still talking "insanely fast" on just about any computer made in the last ten years.

---

Which makes no difference if you call it several times per frame, now does it?

"Expensive" is always a relative term. While it may be "insanely fast" in absolute terms (whatever you choose those to be), integer addition will remain "insanely faster". Et cetera.

Take a course (or get a book) on gate level computer architecture and find out why an adder takes less CPU cycles than something like square root. Once you see the circuit diagrams that is how to REALLY understand why square root takes more time.

here is an overloaded square root function, one with a static number of iterations, the other with a specified number of iterations.

i have not figured out how to make a good guess number to make these efficient.

it uses the divide and average method. this should give you an idea of why its expensive.

double SqRt ( double dNum )
{
double dAns = 2.0;
double dHold = 0.0;

for( int i = 0; i < 100; i++ )
{
dHold = dNum / dAns;
dAns = (dHold + dAns) / 2;
}

return dAns;
}

double SqRt ( double dNum, int iPrecision )
{
double dAns = 2.0;
double dHold = 0.0;

for( int i = 0; i < iPrecision; i++ )
{
dHold = dNum / dAns;
dAns = (dHold + dAns) / 2;
}

return dAns;
}

quote:

---

Original post by phongor
double SqRt ( double dNum, int iPrecision )
{
double dAns = 2.0;
double dHold = 0.0;

for( int i = 0; i < iPrecision; i++ )
{
dHold = dNum / dAns;
dAns = (dHold + dAns) / 2;
}

return dAns;
}

---

How accurate is that? In my games, I need to use sqrt a lot, when I really only need the answer as an int. Therefore, spending a while calculating the square root of 10 when it could return 3 instead of a number similar to pi.

---

Look, one of the few who hasn''t asked Salsa for an Avatar.
Nor do I follow the trend of putting "I don''t follow trends" in your sig.
Wait...

I''m surprised that no one mentioned Carmack''s fast inverse square root...

http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf

botman

quote:

---

Original post by Anonymous Poster

quote:

---

Original post by botman
I''m surprised that no one mentioned Carmack''s fast inverse square root...

<a href="http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf">http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf</a>

botman

---

Actually it has been mentioned, but it''s not really called "Carmack''s fast inverse square root" (although many people tend to call it that).

---

And didn''t some guy at Nvidia figure it out before him?

speaking of square roots, how do they figure out the exact figures for trigonometric functions? Plug in random values for opposite and adjacent? Draw a gazillion triangles with all possible angles and measure? Or do they just interpolate linearly for angle values that are not integers?

There are no such things for exact values for many of the inputs trigonmetric functions. It''s even mathematically provable that it''s impossible to determine exact values for some of the angles. It is possible to create accurate approximations to arbitrary precision through things like Taylor or Maclaurin expansions.

quote:

---

Original post by Cipher3D
speaking of square roots, how do they figure out the exact figures for trigonometric functions? Plug in random values for opposite and adjacent? Draw a gazillion triangles with all possible angles and measure? Or do they just interpolate linearly for angle values that are not integers?

---

Taylor and Maclaurin series.