Distance between two points:
sqrt((x1-x2)^2 + (y1-y2)^2)
Is there a way to do this math faster in objective-C ?
EDIT: I think I need to clarify above. I wrote the formula above just to clarify what formula I am using to calculate the distance. ^ is not meant to represent xor - I just wanted to represent the mathematical formula without using any functions like pow or anything, so I meant to use ^ to "raise to the power off". I was wondering if anyone knows if using bitwise operators, or otherwise writing code in assembly would give an optimized version. I am using the formula in an iPhone / iPad application.
No, if you need the exact distance you cannot beat that formula.
Although to be clear ^ is not an operator for squaring a value, but a bit operator that does xor.
you will need something like
double dx = (x2-x1);
double dy = (y2-y1);
double dist = sqrt(dx*dx + dy*dy);
If you can live with just the square (which is useful when you just want to do something like sort by distance, you can use the much more efficient
double dx = (x2-x1);
double dy = (y2-y1);
double dist = dx*dx + dy*dy;
These will be at least as good as a solution pow. At worst, pow() will use the stack and be less efficient, but maybe your compiler turns it into x*x for this case.
Just offering this as a simple, nice looking solution. It is most likely not any faster than any previously given, just shorter. I personally am using hypot.
double dist = hypot((x1-x2), (y1-y2));
Per the docs, this will return you "The square root of (x^2+y^2)."
On an Intel Mac Clang will compile:
double distance = ({double d1 = x1 - x2, d2 = y1 - y2; sqrt(d1 * d1 + d2 * d2); });
into a grand total of 6 instructions for the maths: sub, mul, sub, mul, add, sqrt; pretty hard to beat that. (sqrt is a single instruction, though it takes multiple cycles).
double dist = sqrt ( pow((x1-x2), 2) + pow((y1-y2), 2) );
considering x1, x2, y1, y2 are float or double or integer.
About the only thing that can be improved here is the square root calculation function.
I've tried these two functions (found in a Wikipedia article on square root computation) to calculate approximate square root values:
float fsqrt(float x)
{
float xhalf = 0.5f * x;
union
{
float x;
int i;
} u;
u.x = x;
u.i = 0x5f3759df - (u.i >> 1);
x *= u.x * (1.5f - xhalf * u.x * u.x);
return x;
}
float fsqrt2(float z)
{
union
{
int tmp;
float f;
} u;
u.f = z;
/*
* To justify the following code, prove that
*
* ((((val_int / 2^m) - b) / 2) + b) * 2^m = ((val_int - 2^m) / 2) + ((b + 1) / 2) * 2^m)
*
* where
*
* val_int = u.tmp
* b = exponent bias
* m = number of mantissa bits
*
* .
*/
u.tmp -= 1 << 23; /* Subtract 2^m. */
u.tmp >>= 1; /* Divide by 2. */
u.tmp += 1 << 29; /* Add ((b + 1) / 2) * 2^m. */
return u.f;
}
But on my Core 2 Duo Pentium CPU they don't seem to be faster than the x87 FPU FSQRT instruction. See if they work faster than the standard sqrtf()/sqrt() on your platform and if the accuracy is sufficient.
