• Advertisement

Archived

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

Why square root is expensive?

This topic is 5101 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

While studying many game books i have found that sqrt is expensive in terms of CPU but no one has explained it. Can u? Thanks

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Guest 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. Also note that a floating point square root can tick away in the background while integer and branch instructions are executing, so some of it''s wee expense is often further diluted.

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Scint
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.


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.

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites

  • Advertisement