Cách nhanh nhất để tính khoảng cách giữa hai CGPoints?

Question

Khoảng cách giữa hai điểm:

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

Có cách nào để làm toán này nhanh hơn trong mục tiêu-C?

EDIT: Tôi nghĩ rằng tôi cần làm rõ ở trên. Tôi đã viết công thức trên chỉ để làm rõ công thức tôi đang sử dụng để tính khoảng cách.^không có nghĩa là đại diện cho xor - Tôi chỉ muốn đại diện cho công thức toán học mà không sử dụng bất kỳ chức năng như pow hay bất cứ điều gì, vì vậy tôi có nghĩa là sử dụng^để "nâng cao sức mạnh tắt". Tôi đã tự hỏi nếu có ai biết nếu sử dụng các nhà khai thác bitwise, hoặc nếu không viết mã trong lắp ráp sẽ cung cấp cho một phiên bản tối ưu hóa. Tôi đang sử dụng công thức trong ứng dụng iPhone/iPad.

Answer 1

Không, nếu bạn cần khoảng cách chính xác, bạn không thể đánh bại công thức đó.

Mặc dù rõ ràng^không phải là toán tử cho bình phương một giá trị, nhưng một toán tử bit thực hiện xor.

bạn sẽ cần một cái gì đó giống như

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

Nếu bạn có thể sống chỉ với quảng trường (đó là hữu ích khi bạn chỉ muốn làm điều gì đó giống như sắp xếp theo khoảng cách, bạn có thể sử dụng nhiều hiệu quả hơn

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

đây sẽ là ít nhất cũng tốt như một pow giải pháp. tại tồi tệ nhất, pow() sẽ sử dụng ngăn xếp và ít hiệu quả, nhưng có lẽ trình biên dịch của bạn biến nó thành x * x cho trường hợp này.

Answer 2

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

xem xét x1, x2, y1, y2 là float hoặc double hoặc số nguyên.

Answer 3

Trên Intel Mac Clang sẽ biên dịch:

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

vào tổng số 6 chỉ dẫn cho toán: sub, mul, sub, mul, add, sqrt; khá khó để đánh bại điều đó. (sqrt là một lệnh duy nhất, mặc dù phải mất nhiều chu kỳ).

Answer 4

Điều duy nhất có thể cải thiện ở đây là hàm tính toán căn bậc hai.

Tôi đã thử hai chức năng (tìm thấy trong một Wikipedia article on square root computation) để tính toán gần đúng giá trị căn bậc hai:

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

Nhưng trên Core 2 Duo CPU Pentium của tôi họ không có vẻ là nhanh hơn so với x87 FPU FSQRT hướng dẫn. Xem liệu chúng có hoạt động nhanh hơn tiêu chuẩn sqrtf()/sqrt() trên nền tảng của bạn và nếu tính chính xác là đủ.

Answer 5

Chỉ cung cấp giải pháp này đơn giản, đẹp mắt. Nó rất có thể không nhanh hơn bất kỳ điều gì được đưa ra trước đó, chỉ ngắn hơn. Cá nhân tôi đang sử dụng hypot.

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

mỗi sự docs, điều này sẽ đưa bạn trở "Các căn bậc hai của (x^2 + y^2)."