¿La forma más rápida de calcular la distancia entre dos CGPoints?

Question

Distancia entre dos puntos:

sqrt((x1-x2)^2 + (y1-y2)^2) 

¿Hay una manera de hacerlo más rápido matemáticas en Objective-C?

EDIT: Creo que tengo que aclarar arriba. Escribí la fórmula anterior solo para aclarar qué fórmula estoy usando para calcular la distancia.^no pretende representar xor - Solo quería representar la fórmula matemática sin usar ninguna función como pow o nada, así que quise utilizar^para "aumentar el apagado". Me preguntaba si alguien sabe si usar operadores bit a bit, o escribir código en el ensamblado daría una versión optimizada. Estoy usando la fórmula en una aplicación de iPhone/iPad.

Answer 1

No, si necesita la distancia exacta, no puede vencer esa fórmula.

Aunque para ser claros^no es un operador para cuadrar un valor, sino un operador de bit que hace xor.

tendrá algo así como

double dx = (x2-x1); 
double dy = (y2-y1); 
double dist = sqrt(dx*dx + dy*dy); 

Si se puede vivir con sólo la plaza (que es útil cuando lo que desea es hacer algo como ordenar por distancia, puede utilizar el mucho más eficiente

double dx = (x2-x1); 
double dy = (y2-y1); 
double dist = dx*dx + dy*dy; 

Estos serán al menos tan bueno como un prisionero de guerra solución. en el peor, pow() se usa la pila y ser menos eficiente, pero tal vez su compilador convierte en x * x para este caso.

Answer 2

double dist = sqrt (pow((x1-x2), 2) + pow((y1-y2), 2)); 

considerando x1, x2, y1, y2 son float o double o entero.

Answer 3

en un Mac Intel Clang compilará:

double distance = ({double d1 = x1 - x2, d2 = y1 - y2; sqrt(d1 * d1 + d2 * d2); }); 

en un total de 6 Instrucciones para el de matemáticas: sub, mul, sub, mul, añadir, sqrt; bastante difícil de superar eso. (sqrt es una instrucción única, aunque lleva varios ciclos).

Answer 4

Lo único que se puede mejorar aquí es la función de cálculo de raíz cuadrada.

He probado estas dos funciones (que se encuentra en un Wikipedia article on square root computation) para calcular los valores aproximados de raíz cuadrada:

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; 
} 

Pero en mi Core 2 Duo CPU Pentium no parecen ser más rápido que el x87 Instrucción FPU FSQRT. Vea si funcionan más rápido que el estándar sqrtf()/sqrt() en su plataforma y si la precisión es suficiente.

Answer 5

Simplemente ofreciendo esto como una solución simple y agradable. Lo más probable es que no sea más rápido que el anterior, solo más corto. Yo personalmente estoy usando hypot.

double dist = hypot((x1-x2), (y1-y2)); 

por la docs, esto le volverá "La raíz cuadrada de (x^2 + y^2)."