Ich entwickle ein Spiel, das so viele mathematische Funktionen für Physik und Rendering aufruft. "Fast inverse sqrt" in Quake3 verwendet bekannt ist schneller als sqrt() und sein Hintergrund ist schön.Schneller mathematischer Algorithmus opfert Genauigkeit
Kennen Sie einen anderen Algorithmus, der schneller ist als der andere mit akzeptablem Genauigkeitsverlust?
Diese Algorithmen werden in der Literatur als Approximationsalgorithmen bezeichnet. Das Standardbuch mit vielen Beispielen ist Approximation Algorithms by Vijay V. Vazirani.
Der Fall von sin x ~~ x ist ein Sonderfall von etwas etwas allgemeiner: Betrachten Sie die Taylor series (oder Fourier-Reihe bei periodischen Funktionen) Ihrer Funktion und berechnen Sie nur die ersten paar Begriffe.
Eine andere (etwas brutale) Technik besteht darin, einige Punkte Ihrer Funktion nach dem Zufallsprinzip zusammenzustellen und dann eine lineare Regression dagegen durchzuführen. Auf diese Weise können Sie ein gutes Polynom erhalten, das auch Ihre Funktion beschreibt :).
Eine lineare Regression führt zu einer "geraden Linie" - wahrscheinlich nicht das, was Sie wollen. Aber Sie könnten ein Polynom 2. oder 3. Grades im kleinsten Quadranten anpassen, was zu akzeptabler Genauigkeit führen kann. – Paul
Sie können die Koeffizienten des Polynoms mit einer linearen Regression finden. – nes1983
Danke, das Buch ist was ich suche. – grayger
für kleine x: sin (x) ~ = x ist eine, die oft in der Physik verwendet wird
Bitte ändern Sie '==' in '~'. – jason
guten Ruf - geändert –
Anything probabilistischen ist in der Regel wie folgt aus. Wenn Sie eine Simulation 10-mal ausführen, ist dies zwar schneller, aber Sie erzielen weniger genaue Ergebnisse als wenn Sie eine Simulation 1000-mal ausführen.
Niko hat einige gute Vorschläge, zu denen ich die alte Mode-Look-Up-Tabelle hinzufügen würde.
Ich habe eine Nachschlagetabelle für zirkuläre Funktionen (sin/cos/tan) erfolgreich viele Male in Hochleistungs-Echtzeit-System verwendet. Das sqrt() ist auf diese Weise schwieriger, aber wenn Ihr Eingabebereich eingeschränkt ist (um Bildschirmpixel zu sagen), ist es schwer, Geschwindigkeit zu erreichen, und Sie können den Raum-/Genauigkeits-Trade genau einstellen. Sie können auch die Suche nach einem gemeinsamen Bereich verwenden und dann einen Fallout für eine Framework-Funktion sqrt() für den seltenen Fall haben.
Paul
Jede kontinuierliche Funktion (die häufigste mathematische Operationen umfasst) kann auch über einen beschränkten Intervall durch ein Polynom approximiert werden. Dies, zusammen mit relativ einfachen Identitäten, die gewöhnliche mathematische Funktionen normalerweise erfüllen (wie Additionsgesetze) und Tabellensuchen, liefert die Basis der Standardtechniken zum Konstruieren schneller Approximationsalgorithmen (und auch die Basis von hochgenauen Methoden, wie sie in der Systemmathematik verwendet werden Bibliothek).
Taylor-Reihen sind normalerweise eine schlechte Wahl, jedoch; Chebyshev- oder Minimax-Polynome haben für die meisten Computeranwendungen viel bessere Fehlereigenschaften. Die Standardtechnik für die Anpassung von Minimax-Polynomen ist die Verwendung des Remes-Algorithmus, der in einer Vielzahl kommerzieller Mathe-Software implementiert ist, oder Sie können Ihre eigene Implementierung mit einem Arbeitstag umsetzen, wenn Sie wissen, was Sie tun.
Für die Aufzeichnung der „schnelle inverse Quadratwurzel“ sollte bei modernen Prozessoren vermieden werden, da er wesentlich schneller ist, eine Fließkommainstruktion reziproken Quadratwurzelschätzwertes (rsqrtss/rsqrtps auf SSE, vrsqrte auf NEON zu verwenden, vrsqrtefp auf AltiVec). Selbst die (nicht näherungsweise) Hardware-Quadratwurzel ist auf aktuellen Intel-Prozessoren recht schnell.
Von dem Doom-Quellcode, um ungefähren Abstand zwischen zwei 2D-Punkten ohne sqrt() oder trigonometrische Funktionen zu verwenden:
fixed_t P_AproxDistance(fixed_t dx, fixed_t dy)
{
dx = abs(dx);
dy = abs(dy);
if (dx < dy)
return dx+dy-(dx>>1);
else
return dx+dy-(dy>>1);
}
Beachten Sie, dass x >> 1 das gleiche ist wie x/2 aber etwas schneller - gute, moderne Compiler mach das heute automatisch, aber damals waren sie nicht so toll.
Okay, das dauerte ewig, aber 'fixed_t' ist ein Typdef von' int'. Also, was nähern Sie sich der Entfernung von? – knight666
Vielleicht erhalten Sie auch Antworten für die auf http://mathoverflow.net – Lucero
Was ist damit ein Wiki zu machen? – ATorras
Ich bin mir nicht sicher, ob die schnelle umgekehrte Wurzel, die in Quake verwendet wird, heutzutage schneller ist als eine RSQRTPS, und sie tut vier parallel. Heutzutage können die Kosten für das Verschieben von Daten von der FPU in den RAM zum Registrieren, Manipulieren, Speichern und Neuladen in die FPU mehr als nur ein FSQRT sein. – Skizz