No idea why you'd have to compute distances every frame, but in any case either don't use sqrt like others said, or there are ways of approximating sqrt, which I dare not go into.

You may also be advised to look at your design and to why your execution is O(N^N)

[I'm assuming you actually did mean exponential rather than something like O(N^2)]

You can achieve a lot by saving the results of distance computations (the old space vs execution time trade-off).

you could try an approximate distance/sqrt algorithm.

You could try changing your design so that more of the calculations take place on the client side, e.g distances to static or slow moving objects.

I heard somewhere that using double now is actually faster than using floats on modern computers.

Is this true?

Hey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share

I heard somewhere that using double now is actually faster than using floats on modern computers.

Is this true?


i beleive this is true only on 64 bit processors with 64 bit o/s's

Ok, so if you're having that big O n^n problem you should use an oct-tree or break up your space into sectors and give each of them an oct-tree.

Also, you can use a combination of dirty distance methods and accurate ones. So I'd say use something really dirty for most distances, but once you get close(like for a collision or something) re-calc for something more accurate.


Dirty method one: The octagon
// perfect on the axis, 18% average error
// 8+ times faster
// assuming all numbers are positive, or changed to be... x = abs(x);
d = 0.5*(x + y + ... + max(x, y, ..)); // generally
d = 0.5*(x + y + (x>y)?x:y); // c++ish 2d case


Dirty method two: Know your floating point, EDIT: this is for 32bit float
// perfect for powers of 2, 1.8% average error
// 6+ times faster
union{float f[2]; // store your x, y & z
unsigned int i[2];};// temp
i[0] <<= 1;
i[1] <<= 1;
i[0] -= 0x3F800000;
i[1] -= 0x3F800000;
f[0] += f[1];
i[0] += 0x3F800000;
i[0] >>= 1;
// f[0] is your final distance

EDIT: unless you're squaring complex numbers(normal float doesn't support) then you don't need to abs() your displacements (x1-x2)... we forgive him, the hour is late...


I see through the lies of the Jedi... to learn the true power of the code one must look at both sides and find their true power!

[Edited by - ismakefire on June 4, 2005 4:07:57 AM]