optimizing the square root

Turn on compiler intrinsics and make sure you're set to compile for a recent processor. Enabling SSE instructions will help as well. If that doesn't do the trick, you may wish to look at vectorizing with SSE yourself, and doing 4 square roots at a time.

It is unlikely you will be able to even come vaguely close in performance to an SSE square root using any other method anyway.

You can also find partial precision sqrt() approximations, but they may not give you the precision you need for a physical simulation.

http://www.google.com/search?q=sqrt+approximation

If you know that most vectors will be *close* to 100.0f, then a taylor expansion around 100 would be a good way to go. I've also stumbled on the following fake-sqrt which seems to be working nicely. I haven't been able to derive where it comes from, though.

float fy = fabsf(y);
float fx = fabsf(x);
float l = (fy > fx) ? (fy + .336356f*fx) : (fx + .336356f*fy);

Since you're normalizing vectors if you go the SSE route it looks like you're much better off computing reciprocal square roots and multiplying rather than square roots and dividing. I don't claim to be any great expert on x86 assembler - I know enough to get around but I'm nowhere near Jan Wassenberg's level - but the Intel manual list the packed square root and divide instructions as having latencies and throughputs of ~40 each, whereas packed reciprocal square roots are listed with a latency of ~6 and throughput of ~4 and packed multiplies a latency of ~7 and a throughput of ~2. Latency is the number of clock cycles required for the instruction to execute and throughput is the number of clock cycles required before that instruction can be issued again on the same port.

Σnigma

Carmack has a very fast inverse square root approximation that you can find if you dig through the Quake3 source (I think it's in c_math.h). It's an approximation but a very close one, we used this all over the place in our last project.

Here's a little article that shows the code for Carmack's sqrt and discusses it a bit.

Thanks, at in the article there were the following lines:


What do they mean.
and what is 0x5f375a86 in the decimal (mormal) system?
Thanks.

About that constant:

Quote:

Original post by daniel_i_l It turns out that the magic constant 0x5f3759df is a real mystery. In the article "Fast Inverse Square Root" [2] , mathematician Chris Lomont of Purdue University researches the meaning of this magic constant.

About x = *(float*)&i:

&i is the address of i, a pointer to an int.
(float*) casts that pointer to int to a pointer to float.
This pointer is then dereferenced by the * and stored in the variable x.

What this line of codes does is interpret the bits represented by i as a float. This is necessary because you cannot manipulate the bits in a float variable.

The algorithm will not make much sense to you unless you know how floating point values are internally stored.

Maybe this thread is of interest:
http://www.gamedev.net/community/forums/topic.asp?topic_id=278849

Quote:

Original post by daniel_i_l Thanks, at in the article there were the following lines: *** Source Snippet Removed *** What do they mean. and what is 0x5f375a86 in the decimal (mormal) system? Thanks.

The Windows calculator could tell you that, but that wouldn't bring you one iota closer to understanding why it is that exact number.
Do not try to understand the function, it is not for mere mortals. Simply give thanks to Carmack and use the code wisely.[cool]

Its actualy really easy to understand *why* that number was chosen.

Any other number will give results with a larger magnitude of error across the set of expected inputs.

The precise details are of course unimportant unless you are looking into deriving a similar algorithm for, say, 4th roots. The key idea however is that in the floating point format is an integer representing the exponent of the binary value as well as an integer representing the mantissa. The exponent offers a quick and dirty log2 approximation which is what drives the idea, and the mantissa is used to improve that approximation in yet another dirty move.

in that article it say that they tried to find that magic constant with mathematics, but they got a slightly different number, how did thay find it?

This paper describes the process used to calculate that number

On current computers, the cost of doing an exhaustive search (based on an estimation of error) is so low that there is no reason not to simply search all possible constants. There are only 4 billion of them.

Quote:

Original post by Rockoon1 On current computers, the cost of doing an exhaustive search (based on an estimation of error) is so low that there is no reason not to simply search all possible constants. There are only 4 billion of them.

True, although to test how good each one of those 4 billion are, you need to try each one with more than one input float value. Ideally you'd try each one out with all 4 billion input floats, but that's now outside the realms of feasability.

Quote:

Original post by iMalc Quote: Original post by Rockoon1 On current computers, the cost of doing an exhaustive search (based on an estimation of error) is so low that there is no reason not to simply search all possible constants. There are only 4 billion of them. True, although to test how good each one of those 4 billion are, you need to try each one with more than one input float value. Ideally you'd try each one out with all 4 billion input floats, but that's now outside the realms of feasability.

No that wouldnt be ideal.

Ideal would be to test against your expected input set, not against all possible inputs. This will give you a better approximation in practice.

Also, approximating the error with only a handfull of test terms is actualy quite accurate if they are distributed well. Values near each other will yield errors near each other.

Ah, true true. I must have been feeling pessimistic when I wrote that.

Everything you ever wanted to know about square roots, but were afraid to ask. (some assembly required). [smile]