hypotenuse nhanh nhất trong javascript?

Question

Tôi đã nhìn thấy một số câu hỏi về mô phỏng và hình ảnh động trong javascript, mà thường liên quan đến tính cạnh huyền:

hypot = Math.sqrt(x*x + y*y); 

Kể từ tọa độ Descartes là vũ khí của sự lựa chọn trong hầu hết các động cơ, những tính toán này là cần thiết để tìm khoảng cách giữa các cặp điểm, vv Vì vậy, bất kỳ sự tăng tốc nào trong việc tính toán cạnh huyền có thể là một trợ giúp lớn cho nhiều dự án.

Để kết thúc, bạn có thể thấy phương pháp nhanh hơn so với triển khai đơn giản ở trên không? Tôi đã tìm thấy một phép tính xấp xỉ nhanh hơn trong Chrome, nhưng hóa ra lại chậm hơn nhiều trong Firefox, dựa trên this approximation function in SuperCollider.

Chỉnh sửa 2015-08-15: Tôi đã chuyển câu trả lời được chấp nhận thành Math.hypot; Tôi nghi ngờ cách tiếp cận thực dụng hiện nay sẽ là sử dụng Math.hypot hoặc một hàm hypot tổng hợp nếu không có sẵn, và để so sánh với hình vuông (mỗi câu trả lời của sch) nếu điều đó là đủ và Math.hypot không có sẵn.

Answer 1

Trong ECMAScript ES6 bạn có thể sử dụng Math.hypot:

// ES5 support 
 

 
Math.hypot = Math.hypot || function(x, y){ return Math.sqrt(x*x + y*y) } 
 

 
var x = 3, y = 4; 
 

 
document.write(Math.hypot(x, y))

Sửa: Bạn có thể chạy thử nghiệm này trên một tab trống, là 2 triệu hoạt động với cả hai phương pháp, kết quả rất tốt, nhanh hơn 24%.

var i, tmp, x = 55, y = 66, end, ini = performance.now(); 

// Math.sqrt operation 
i = 0; 
ini = performance.now(); 
tmp = 0; 
while(i++ < 2000000){ 
    tmp += Math.sqrt(x*x + y*y) 
} 
end = performance.now(); 
console.log(tmp, "Math.sqrt operation: " + (end - ini) + " ms"); 

// Math.hypot 

i = 0; 
ini = performance.now(); 
tmp = 0; 
while(i++ < 2000000){ 
    tmp += Math.hypot(x, y) 
} 
end = performance.now(); 

console.log(tmp, "Math.hypot: " + (end - ini) + " ms"); 

Note: Trong thử nghiệm này, nó được sử dụng ES6 của Math.hypot.

Answer 2

Thông thường, bạn không cần tính căn bậc hai và hypot^2 = x*x + y*y là đủ. Đây là trường hợp ví dụ nếu bạn muốn so sánh khoảng cách và không cần các giá trị thực tế.

Answer 3

Bạn có thể xem xét mức độ bình đẳng của x và y. Nếu bằng với bạn có thể tính toán hypotenuse là (x + y)/sqrt(2) trong đó sqrt(2) là hằng số.

Vì vậy, phương pháp này có thể được sử dụng cho trường hợp x = y. Đối với các trường hợp khác, nó có thể được sử dụng với số lần hiển thị tối đa là ~ 41%. Đây là một lỗi lớn. Nhưng khi bạn chỉ định giới hạn lỗi cho phép, bạn có thể sử dụng phương pháp này. Ví dụ: nếu xác định lỗi cho phép đến 5%, bạn có thể nhận được rằng b phải nằm trong khoảng từ 0.515*a đến 1.942*a.

Vì vậy, nếu bạn không cần sự thiếu chính xác về tính toán của mình, bạn có thể cải thiện hiệu suất tính toán với phạm vi giá trị.

Bằng cách tương tự, bạn có thể xem xét mức độ bình đẳng của x hoặc y đến zero. Và với một số tính toán chính xác hypotenuse nhanh hơn cho các trường hợp này.

P.S. Tôi đã đọc về điều này trong một số russian article.

Answer 4

Một điểm quan trọng mà nhiều người không biết:

hypot = Math.sqrt(x*x + y*y);

đó làm việc trên lý thuyết, nhưng trong thực tế nó có thể thất bại. Nếu x là quá lớn rằng x * x tràn, mã sẽ tạo ra một kết quả vô hạn.

Dưới đây là cách tính toán sqrt (x x + y y) mà không có rủi ro tràn.

max = maximum(|x|, |y|) 
min = minimum(|x|, |y|) 
r = min/max 
return max*sqrt(1 + r*r) 

Tham chiếu và đầy đủ văn bản: John D.Cook - http://www.johndcook.com/blog/2010/06/02/whats-so-hard-about-finding-a-hypotenuse/