Najszybszy sposób obliczenia odległości między dwoma punktami CG?

Question

Odległość między dwoma punktami:

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

Czy istnieje sposób, aby zrobić to szybciej matematyki w Objective-C?

EDYCJA: Myślę, że muszę wyjaśnić powyżej. Napisałem powyższą formułę tylko po to, aby wyjaśnić, jaką formułę używam do obliczenia odległości.^nie ma reprezentować xora - chciałem tylko przedstawić matematyczną formułę bez użycia jakichkolwiek funkcji, takich jak pow lub cokolwiek, więc zamierzałem użyć ^, aby "podnieść do potęgi". Zastanawiam się, czy ktoś wie, czy używanie operatorów bitowych, czy w inny sposób pisanie kodu w zestawie dałoby zoptymalizowaną wersję. Używam formuły w aplikacji na iPhone'a/iPada.

Answer 1

Nie, jeśli potrzebujesz dokładnej odległości, nie możesz pokonać tej formuły.

Chociaż dla jasności^nie jest operatorem do kwadratury wartości, ale operatorem bitowym, który wykonuje xor.

trzeba będzie coś podobnego

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

Jeśli można żyć tylko z placu (co jest przydatne, gdy po prostu chcesz zrobić coś takiego sortuj według odległości, można użyć dużo bardziej wydajny

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

te będą co najmniej tak dobry jak pow rozwiązania. w najgorszym wypadku, pow() użyje stos i być mniej skuteczne, ale może twój kompilator zamienia ją x * x dla tej sprawy.

Answer 2

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

rozważa x1, x2, y1, y2 są float lub double lub całkowitą.

Answer 3

Na Intel Mac Clang skompiluje:

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

do ogólnej sumy 6 Instrukcje dla matematyki: sub, mul, sub, mul, dodawać sqrt; bardzo trudno to pokonać. (sqrt to pojedyncza instrukcja, ale wymaga wielu cykli).

Answer 4

Jedyna rzecz, którą można poprawić tutaj, to funkcja obliczania pierwiastka kwadratowego.

Próbowałem te dwie funkcje (znaleziono w Wikipedia article on square root computation) w celu obliczenia wartości przybliżone kwadratowych root:

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

Ale na moim Core 2 Duo CPU Pentium nie wydają się być szybsze niż x87 Instrukcja FPU FSQRT. Sprawdź, czy działają one szybciej niż standard sqrtf()/sqrt() na twojej platformie i czy dokładność jest wystarczająca.

Answer 5

Po prostu oferuję to jako proste, ładne rozwiązanie. Najprawdopodobniej nie jest szybszy od wcześniej podanych, a jedynie krótszy. Osobiście używam hypot.

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

za tym docs to nastąpi powrót "pierwiastek kwadratowy (x + y^2^2)".