#### Archived

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

# Why square root is expensive?

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

## 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 on other sites
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 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 on other sites
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 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 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 on other sites
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 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 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 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;
}

1. 1
Rutin
37
2. 2
3. 3
4. 4
5. 5

• 12
• 10
• 13
• 104
• 11
• ### Forum Statistics

• Total Topics
632982
• Total Posts
3009690
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!