Wie funktionieren trigonometrische Funktionen?

In der Mathematik der High School und wahrscheinlich am College lernen wir, wie man Triggerfunktionen verwendet, was sie tun und welche Arten von Problemen sie lösen. Aber sie wurden mir immer als Black Box präsentiert. Wenn Sie den Sinus oder Cosinus von etwas benötigen, drücken Sie die Sinus- oder Cosinus-Taste auf Ihrem Taschenrechner und schon sind Sie fertig. Welches ist in Ordnung.

Ich frage mich, wie trigonometrische Funktionen normalerweise implementiert werden.

Zuerst müssen Sie eine Art Bereichsreduzierung durchführen. Triggerfunktionen sind periodisch, daher müssen Sie Argumente auf ein Standardintervall reduzieren. Für den Anfang können Sie die Winkel auf 0 bis 360 Grad reduzieren. Aber wenn Sie ein paar Identitäten verwenden, erkennen Sie, dass Sie mit weniger auskommen können. Wenn Sie Sinus und Cosinus für Winkel zwischen 0 und 45 Grad berechnen, können Sie die Triggerfunktionen für alle Winkel berechnen.

Sobald Sie Ihr Argument reduziert haben, verwenden die meisten Chips einen CORDIC- Algorithmus, um die Sinus- und Cosinuswerte zu berechnen. Sie können Leute sagen hören, dass Computer Taylor-Serien verwenden. Das klingt vernünftig, ist aber nicht wahr. Die CORDIC-Algorithmen eignen sich viel besser für eine effiziente Hardware- Implementierung. ( Softwarebibliotheken verwenden möglicherweise Taylor-Serien, z. B. auf Hardware, die keine Triggerfunktionen unterstützt.) Möglicherweise wird eine zusätzliche Verarbeitung durchgeführt, bei der der CORDIC-Algorithmus verwendet wird, um ziemlich gute Antworten zu erhalten, und dann etwas anderes unternommen wird, um die Genauigkeit zu verbessern.

Es gibt einige Verfeinerungen zu den oben genannten. Zum Beispiel ist für sehr kleine Winkel Theta (im Bogenmaß) sin (Theta) = Theta mit der Genauigkeit, die Sie haben. Daher ist es effizienter, einfach Theta zurückzugeben, als einen anderen Algorithmus zu verwenden. In der Praxis gibt es also eine Menge Sonderfalllogik, um die gesamte mögliche Leistung und Genauigkeit herauszuholen. Chips mit kleineren Märkten erfordern möglicherweise weniger Optimierungsaufwand.

edit: Jack Ganssle hat eine anständige Diskussion in seinem Buch über eingebettete Systeme, "The Firmware Handbook" .

Zu Ihrer Information: Wenn Sie Genauigkeits- und Leistungsbeschränkungen haben, sollten Taylor-Reihen nicht verwendet werden, um Funktionen für numerische Zwecke zu approximieren. (Speichern Sie sie für Ihre Kalkülkurse.) Sie nutzen die Analytizität einer Funktion an einem einzelnen Punkt , z. B. die Tatsache, dass alle ihre Ableitungen an diesem Punkt existieren. Sie konvergieren nicht unbedingt im interessierenden Intervall. Oft sind sie schlecht darin, die Genauigkeit der Funktionsnäherung zu verteilen, um in der Nähe des Bewertungspunkts "perfekt" zu sein. Der Fehler zoomt im Allgemeinen nach oben, wenn Sie ihn verlassen. Und wenn Sie eine Funktion mit einer nicht kontinuierlichen Ableitung haben (z. B. Rechteckwellen, Dreieckswellen und deren Integrale), gibt Ihnen eine Taylor-Reihe die falsche Antwort.

Die beste "einfache" Lösung, wenn ein Polynom mit maximalem Grad N verwendet wird, um eine gegebene Funktion f (x) über ein Intervall x0 <x <x1 zu approximieren , ist die Chebyshev-Approximation ; Eine gute Diskussion finden Sie unter Numerische Rezepte. Beachten Sie, dass Tj (x) und Tk (x) in dem Wolfram-Artikel, mit dem ich verlinkt habe, cos und inversen Cosinus verwendet haben. Dies sind Polynome. In der Praxis verwenden Sie eine Wiederholungsformel, um die Koeffizienten zu erhalten. Siehe auch Numerische Rezepte.

edit: Wikipedia hat einen halbwegs anständigen Artikel zur Approximationstheorie . Eine der Quellen, die sie zitieren (Hart, "Computer Approximations"), ist vergriffen (und gebrauchte Kopien sind in der Regel teuer), geht jedoch auf viele Details zu solchen Dingen ein. (Jack Ganssle erwähnt dies in Ausgabe 39 seines Newsletters The Embedded Muse .)

edit 2: Hier sind einige konkrete Fehlermetriken (siehe unten) für Taylor vs. Chebyshev für sin (x). Einige wichtige Punkte zu beachten:

1. dass der maximale Fehler einer Taylorreihen-Näherung über einen gegebenen Bereich viel größer ist als der maximale Fehler einer Chebyshev-Näherung des gleichen Grades. (Bei ungefähr demselben Fehler können Sie mit Chebyshev mit einem Begriff weniger davonkommen, was eine schnellere Leistung bedeutet.)
2. Reichweitenreduzierung ist ein großer Gewinn. Dies liegt daran, dass der Beitrag von Polynomen höherer Ordnung abnimmt, wenn das Intervall der Approximation kleiner ist.
3. Wenn Sie mit der Entfernungsreduzierung nicht durchkommen können, müssen Ihre Koeffizienten genauer gespeichert werden.

Verstehen Sie mich nicht falsch: Die Taylor-Reihe funktioniert ordnungsgemäß für Sinus / Cosinus (mit angemessener Genauigkeit für den Bereich -pi / 2 bis + pi / 2; technisch gesehen können Sie mit genügend Begriffen jede gewünschte Genauigkeit für alle realen Eingaben erreichen. Versuchen Sie jedoch, cos (100) mithilfe der Taylor-Reihe zu berechnen, und Sie können dies nur tun, wenn Sie eine Arithmetik mit beliebiger Genauigkeit verwenden. Wenn ich mit einem unwissenschaftlichen Taschenrechner auf einer einsamen Insel festsitze und Sinus und Cosinus berechnen müsste, würde ich wahrscheinlich Taylor-Reihen verwenden, da die Koeffizienten leicht zu merken sind. Die realen Anwendungen, in denen Sie Ihre eigenen sin () - oder cos () -Funktionen schreiben müssen, sind jedoch selten genug, dass Sie am besten eine effiziente Implementierung verwenden, um die gewünschte Genauigkeit zu erreichen - was bei der Taylor-Serie nicht der Fall ist .

Bereich = -pi / 2 bis + pi / 2, Grad 5 (3 Terme)

• Taylor: max Fehler rund um 4.5E-3, f (x) = xx ³ /6 + x ⁵ /120
• Chebyshev: maximaler Fehler um 7e-5, f (x) = 0,9996949x-0,1656700x ³ + 0,0075134x ⁵

Bereich = -pi / 2 bis + pi / 2, Grad 7 (4 Terme)

• Taylor: max Fehler rund um 1,5E-4, f (x) = xx ³ /6 + x ⁵ /120 x ⁷ /5040
• Chebyshev: maximaler Fehler um 6e-7, f (x) = 0,99999660x-0,16664824x ³ + 0,00830629x ⁵ -0,00018363x ⁷

Bereich = -pi / 4 bis + pi / 4, Grad 3 (2 Terme)

• Taylor: max Fehler rund um 2.5E-3, f (x) = xx ³ /6
• Chebyshev: max Fehler rund um 1,5E-4, f (x) = 0.999x-0.1603x ³

Bereich = -pi / 4 bis + pi / 4, Grad 5 (3 Terme)

• Taylor: max Fehler rund um 3.5E-5, f (x) = xx ³ /6 + x ⁵
• Chebyshev: max Fehler rund 6E-7, F (x) = 0.999995x-0.1666016x ³ + 0.0081215x ⁵

Bereich = -pi / 4 bis + pi / 4, Grad 7 (4 Terme)

• Taylor: max Fehler rund 3e-7, f (x) = xx ³ /6 + x ⁵ /120 x ⁷ /5040
• Chebyshev: maximaler Fehler um 1,2e-9, f (x) = 0,999999986x-0,166666367x ³ + 0,008331584x ⁵ -0,000194621x ⁷

Ich glaube, sie werden mit Taylor Series oder CORDIC berechnet . Einige Anwendungen, die Triggerfunktionen (Spiele, Grafiken) stark nutzen, erstellen beim Start Trigger-Tabellen, damit sie nur nach Werten suchen können, anstatt sie immer wieder neu zu berechnen.

Lesen Sie den Wikipedia-Artikel über Triggerfunktionen. Ein guter Ort, um zu lernen, wie man sie tatsächlich in Code implementiert, sind numerische Rezepte .

Ich bin kein großer Mathematiker, aber ich verstehe, woher Sünde, Cos und Tan "kommen", dass sie gewissermaßen beobachtet werden, wenn Sie mit rechtwinkligen Dreiecken arbeiten. Wenn Sie die Seitenlängen einer Reihe verschiedener rechtwinkliger Dreiecke messen und die Punkte in einem Diagramm darstellen, können Sie daraus sin, cos und tan erhalten. Wie Harper Shelby betont, werden die Funktionen einfach als Eigenschaften von rechtwinkligen Dreiecken definiert.

Ein differenzierteres Verständnis wird erreicht, indem verstanden wird, wie sich diese Verhältnisse auf die Kreisgeometrie beziehen, was zu Bogenmaß und all dieser Güte führt. Es ist alles da im Wikipedia-Eintrag.

Am häufigsten wird für Computer die Darstellung von Potenzreihen verwendet, um Sinus und Cosinus zu berechnen, und diese werden für andere Triggerfunktionen verwendet. Wenn Sie diese Reihe auf ungefähr 8 Terme erweitern, werden die erforderlichen Werte mit einer Genauigkeit berechnet, die nahe am Maschinen-Epsilon liegt (kleinste Gleitkommazahl ungleich Null, die gehalten werden kann).

Die CORDIC-Methode ist schneller, da sie auf Hardware implementiert ist. Sie wird jedoch hauptsächlich für eingebettete Systeme und nicht für Standardcomputer verwendet.

Ich möchte die Antwort von @Jason S erweitern. Unter Verwendung einer Domain-Unterteilungsmethode, die der von @Jason S beschriebenen ähnelt, und unter Verwendung von Maclaurin-Reihen-Approximationen, einer durchschnittlichen (2-3) X-Beschleunigung über tan (), sin () Die im gcc-Compiler mit -O3-Optimierung integrierten Funktionen cos,), atan (), asin () und acos () wurden erreicht. Die unten beschriebenen besten Approximationsfunktionen der Maclaurin-Serie erreichten eine doppelte Genauigkeit.

Für die Funktionen tan (), sin () und cos () und der Einfachheit halber wurde eine überlappende Domäne von 0 bis 2 pi + pi / 80 in 81 gleiche Intervalle mit "Ankerpunkten" bei pi / 80, 3 pi / 80, unterteilt. ..., 161pi / 80. Dann wurden tan (), sin () und cos () dieser 81 Ankerpunkte ausgewertet und gespeichert. Mit Hilfe von Triggeridentitäten wurde für jede Triggerfunktion eine einzelne Maclaurin-Serienfunktion entwickelt. Jeder Winkel zwischen ± unendlich kann an die Trigger-Approximationsfunktionen übergeben werden, da die Funktionen zuerst den Eingabewinkel in die Domäne von 0 bis 2 pi übersetzen. Dieser Übersetzungsaufwand ist im Approximationsaufwand enthalten.

Ähnliche Methoden wurden für die Funktionen atan (), asin () und acos () entwickelt, bei denen eine überlappende Domäne von -1,0 bis 1,1 in 21 gleiche Intervalle mit Ankerpunkten bei -19/20, -17/20, .. unterteilt wurde. ., 19/20, 21/20. Dann wurde nur atan () dieser 21 Ankerpunkte gespeichert. Wiederum wurde mit Hilfe inverser Triggeridentitäten eine einzelne Maclaurin-Reihenfunktion für die atan () -Funktion entwickelt. Die Ergebnisse der atan () -Funktion wurden dann verwendet, um asin () und acos () zu approximieren.

Da alle inversen Trigger-Approximationsfunktionen auf der atan () -Näherungsfunktion basieren, ist jeder Argument-Eingabewert mit doppelter Genauigkeit zulässig. Das Argument, das in die Näherungsfunktionen asin () und acos () eingegeben wird, wird jedoch auf die Domäne ± 1 abgeschnitten, da jeder Wert außerhalb davon bedeutungslos ist.

Um die Approximationsfunktionen zu testen, mussten eine Milliarde zufällige Funktionsbewertungen ausgewertet werden (das heißt, der -O3-Optimierungscompiler durfte die Auswertung nicht umgehen, da ein berechnetes Ergebnis nicht verwendet wurde.) Um die Verzerrung bei der Auswertung einer Milliarde zu beseitigen Zufallszahlen und Verarbeitung der Ergebnisse, die Kosten eines Laufs ohne Auswertung einer Trigger- oder inversen Triggerfunktion wurden zuerst durchgeführt. Diese Vorspannung wurde dann von jedem Test abgezogen, um eine repräsentativere Annäherung an die tatsächliche Funktionsbewertungszeit zu erhalten.

Tabelle 2. Zeitaufwand in Sekunden für die Ausführung der angegebenen Funktion oder Funktionen eine Milliarde Mal. Die Schätzungen werden erhalten, indem die Zeitkosten für die Auswertung einer Milliarde Zufallszahlen, die in der ersten Zeile von Tabelle 1 gezeigt sind, von den verbleibenden Zeilen in Tabelle 1 subtrahiert werden.

Zeit in tan () verbracht: 18.0515 18.2545

In TAN3 () verbrachte Zeit: 5.93853 6.02349

In TAN4 () verbrachte Zeit: 6.72216 6.99134

Zeit in sin () und cos (): 19.4052 19.4311

In SINCOS3 () verbrachte Zeit: 7.85564 7.92844

In SINCOS4 () verbrachte Zeit: 9.36672 9.57946

Zeit in atan () verbracht: 15.7160 15.6599

In ATAN1 () verbrachte Zeit: 6.47800 6.55230

In ATAN2 () verbrachte Zeit: 7.26730 7.24885

In ATAN3 () verbrachte Zeit: 8.15299 8.21284

Zeitaufwand in asin () und acos (): 36.8833 36.9496

In ASINCOS1 () verbrachte Zeit: 10.1655 9.78479

In ASINCOS2 () verbrachte Zeit: 10.6236 10.6000

In ASINCOS3 () verbrachte Zeit: 12.8430 12.0707

(Um Platz zu sparen, ist Tabelle 1 nicht dargestellt.) Tabelle 2 zeigt die Ergebnisse von zwei getrennten Läufen von einer Milliarde Bewertungen jeder Näherungsfunktion. Die erste Spalte ist der erste Lauf und die zweite Spalte ist der zweite Lauf. Die Zahlen '1', '2', '3' oder '4' in den Funktionsnamen geben die Anzahl der Begriffe an, die in der Maclaurin-Reihenfunktion verwendet werden, um den bestimmten Trigger oder die inverse Trigger-Approximation zu bewerten. SINCOS # () bedeutet, dass sowohl sin als auch cos gleichzeitig ausgewertet wurden. Ebenso bedeutet ASINCOS # (), dass sowohl Asin als auch Acos gleichzeitig bewertet wurden. Die gleichzeitige Bewertung beider Mengen ist mit wenig zusätzlichem Aufwand verbunden.

Die Ergebnisse zeigen, dass eine Erhöhung der Anzahl der Begriffe die Ausführungszeit erwartungsgemäß geringfügig verlängert. Selbst die kleinste Anzahl von Termen ergab überall eine Genauigkeit von 12 bis 14 Stellen, mit Ausnahme der tan () - Näherung nahe der Stelle, an der sich ihr Wert ± unendlich nähert. Man würde erwarten, dass sogar die tan () - Funktion dort Probleme hat.

Ähnliche Ergebnisse wurden auf einem High-End-MacBook Pro-Laptop unter Unix und auf einem High-End-Desktop-Computer unter Linux erzielt.

Wenn Sie nach einer physikalischeren Erklärung von Sünde, cos und tan fragen, überlegen Sie, wie sie sich auf rechtwinklige Dreiecke beziehen. Der tatsächliche numerische Wert von cos (Lambda) kann ermittelt werden, indem ein rechtwinkliges Dreieck gebildet wird, wobei einer der Winkel Lambda ist, und die Länge der Dreieckseite neben Lambda durch die Länge der Hypotenuse dividiert wird. Verwenden Sie für die Sünde die gegenüberliegende Seite geteilt durch die Hypotenuse. Verwenden Sie für Tangenten die gegenüberliegende Seite geteilt durch die benachbarte Seite. Das klassische Memonic, an das man sich erinnert, ist SOHCAHTOA (ausgesprochen socatoa).