Schnellste Hypotenuse in Javascript?

Question

Ich habe eine Reihe von Fragen über Simulationen und Animationen in JavaScript, um zu sehen, die oft die Hypotenuse beinhalten Berechnung: zu

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

Da kartesisch die Waffe der Wahl in den meisten dieser Motoren sind, werden diese Berechnungen benötigt Finde den Abstand zwischen Paaren von Punkten, usw. Jede Beschleunigung bei der Berechnung der Hypotenuse könnte eine große Hilfe für viele Projekte sein.

Können Sie zu diesem Zweck eine schnellere Methode als die einfache Implementierung oben sehen? Ich fand eine Approximation, die in Chrome marginal schneller war, aber in Firefox, basierend auf this approximation function in SuperCollider, viel langsamer war.

Edit 2015-08-15: Ich habe die akzeptierte Antwort auf die Math.Hypot eins; Ich vermute, dass der pragmatische Ansatz zur Zeit wäre, Math.hypot oder eine synthetisierte Hypot-Funktion zu verwenden, wenn sie nicht verfügbar ist, und mit dem Quadrat zu vergleichen (pro Schs Antwort), wenn das ausreicht und Math.hypot nicht verfügbar ist.

Answer 1

In ECMAScript ES6 Sie Math.hypot verwenden:

// 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))

bearbeiten: Sie können diesen Test ausführen und auf eine leere Registerkarte sind 2 Millionen Operationen sowohl mit Methoden, die Ergebnisse sind sehr gut, es ist 24% schneller.

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"); 

Hinweis: In diesem Test ist es ES6 die verwendet Math.hypot.

Answer 2

Oft müssen Sie die Quadratwurzel nicht berechnen und hypot^2 = x*x + y*y ist genug. Dies ist zum Beispiel der Fall, wenn Sie die Entfernungen vergleichen möchten und nicht die tatsächlichen Werte benötigen.

Answer 3

Sie können auf Gleichheit x und y schauen. Wenn sie gleich sind, können Sie die Hypotenuse als (x + y)/sqrt(2) berechnen, wobei sqrt(2) eine Konstante ist.

So kann diese Methode für den Fall verwendet werden, wo x = y. In anderen Fällen kann es mit einer maximalen Ungenauigkeit von ~ 41% verwendet werden. Das ist ein großer Fehler. Wenn Sie jedoch zulässige Fehlergrenzen angeben, können Sie diese Methode verwenden. Wenn Sie beispielsweise den zulässigen Fehler auf 5% setzen, können Sie feststellen, dass b zwischen 0.515*a und 1.942*a liegen muss.

Wenn Sie also keine perfekte Ungenauigkeit Ihrer Berechnungen benötigen, können Sie die Leistung von Berechnungen mit einem Wertebereich verbessern.

Analog können Sie auf Gleichheit x oder y zu zero schauen. Und mit einiger Genauigkeit berechnen Sie die Hypotenuse für diese Fälle schneller.

P.S. Ich habe darüber in der One russian article gelesen.

Answer 4

Ein wichtiger Punkt, dass viele nicht wissen:

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

Die in der Theorie funktioniert, aber in der Praxis kann es fehlschlagen. Wenn x so groß ist dass x * x überläuft, wird der Code ein unendliches Ergebnis erzeugen.

So berechnen Sie sqrt (x x + y y), ohne einen Überlauf zu riskieren.

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

Referenz und vollständiger Text: John D.Koch - http://www.johndcook.com/blog/2010/06/02/whats-so-hard-about-finding-a-hypotenuse/