Highly optimized code for distance

Nope, that's as fast as you'll get it. Unless you can get it in SSE or something, but I question the value of doing that.

Instead of optimizing the distance formula, the usual trick is to work in "squares-of-distances". If you're only interested in relative distances, then instead of:

if( distance < 2 )
{
    // do something
}

try:

if( distance2 < 4 )
{
    // do something
}

See? The logic is the same, but it's a multiply instead of square root.

Edit: Not even a multiply if you're using a constant on the right

If I had my way, I'd have all of you shot!

---

codeka.com - Just click it.

[edited by - Dean Harding on January 15, 2003 6:36:42 AM]

Actually, it''s :

d^2 = (Ax - Bx)^2 + (Ay - By)^2 + (Az - Bz)^2

(note the - sign instead of +)

ASM won''t help you here. It would be even faster to use a C++ inline function since it may be easier for the compiler to interleave the generated opcodes with opcodes that are outside the function, which is more pipeline and super scalar friendly.

Just forget about ASM and use an inline function.

The only optimizations I can think of are these ones (remember the square root is the bottleneck here) :

- Use a custom sqrt() function. Some aproximations can be computed faster (Quake 2 code contains such a function, if memory deserves).

- Do not compute the square root. If you don''t need the actual distance and you just want to compare distances, you can use the squared distances (since A^2 > B^2 and A > 0 and B > 0 => A > B).

PS : since my english sucks and I''ve noticed you''re french, I can explain it in french if you want.

quote:

---

Original post by Prosper/LOADED
d^2 = (Ax - Bx)^2 + (Ay - By)^2 + (Az - Bz)^2

(note the - sign instead of +)

ASM won't help you here. It would be even faster to use a C++ inline function since it may be easier for the compiler to interleave the generated opcodes with opcodes that are outside the function, which is more pipeline and super scalar friendly.

Just forget about ASM and use an inline function.

The only optimizations I can think of are these ones (remember the square root is the bottleneck here) :

- Use a custom sqrt() function. Some aproximations can be computed faster (Quake 2 code contains such a function, if memory deserves).

- Do not compute the square root. If you don't need the actual distance and you just want to compare distances, you can use the squared distances (since A^2 > B^2 and A > 0 and B > 0 => A > B).

PS : since my english sucks and I've noticed you're french, I can explain it in french if you want.

---

he could use left shift for the ^2 to make it go faster

[edited by - xaxa on January 15, 2003 7:16:19 AM]

Left shift won''t help here. A left shift one step is multiplication by two. Although you can use the shift operator and addition multiple times to achieve a square, it will be WAY slower than a single multiplication. Also, if the datatypes in use are floatingpoint types, shifts won''t work at all.

quote:

---

Original post by xaxa
he could use left shift for the ^2 to make it go faster

---

Please explain how. Left shift is commonly used to multiply a number by a power of two but I fail to see how you can compute X^2 (ie. X*X) with it.

quote:

---

Original post by Prosper/LOADED
Please explain how. Left shift is commonly used to multiply a number by a power of two but I fail to see how you can compute X^2 (ie. X*X) with it.

---

Yes sorry, I was wrong. It only works for integer numbers power of two.

(256)^2 = (100000000)<<8 = 10000000000000000

So i guess it's useless in this case.

EDIT: I mean power (not multiple)

[edited by - xaxa on January 15, 2003 8:16:06 AM]

quote:

---

Original post by xaxa

(256)^2 = (100000000)<<8 = 10000000000000000

---

256^2 = 1<<16 = 65536

quote:

---

Original post by sardak
256^2 = 1<<16 = 65536

---

I meant that if you shift so many times as zeros the number has you get the ^2...

256^2 = (1 0000 0000)<<8 = 1 0000 0000 0000 0000 = 65536

Does this need to be exact?
You can get an upper bound on the distance by summing the absolute difference between components (manhattan or taxicab distance).

> Unless you can get it in SSE or something, but I question the value of doing that.
> Just forget about ASM and use an inline function.
hehe...

VC7:



slapped together 3DNow! code:



a bit more than 2x as fast on my Athlon XP. Similar gains are possible with SSE, though it''s a bit more clumsy for lack of an accumulate instruction.


If you can''t avoid the sqrt, calculate it as x * rsqrt(x):
- on Athlons: pfrsqrt + pfmul (7 clock latency)
- otherwise, use a clever bit of code credited to Carmack:


What this does in a nutshell is approximate via one iteration of Newton''s method (the line with the magic number computes an initial guess, important for convergence).

HTH
Jan

500x2