Wie kann man die Sin-Funktion schneller und genauer berechnen?

Ich möchte berechnen y(n)=32677Sin(45/1024•n), wo yeine Ganzzahl ist und nzwischen 0 und 2048 liegt. Wie kann ich diesen Prozess schneller und genauer machen? Jetzt möchte ich Ihnen eine Referenzantwort zeigen: Seit Sin(a+b)=Sin(a)Cos(b)+Cos(a)Sin(b) Und Cos(a+b)=Cos(a)Cos(b)-Sin(a)Cos(b). So kann ich speichern Sin(45/1024•1)und nur. Cos(45/1024•1)Dann verwenden Sie diese Formel:

Sin(45/1024•2)=Sin(45/1024•1+45/1024•1), Cos(45/1024•2)=Cos(45/1024•1+45/1024•1), Sin(45/1024•n)=Sin(45/1024•(n-1)+45/1024•1), Cos(45/1024•n)=Cos(45/1024•(n-1)+45/1024•1), Auf diese Weise vielleicht schneller ohne großen Array zu speichern.

c++ algorithms LaiJong
quelle

Diese Frage ist für Programmierer geeignet, vorausgesetzt, die Absicht besteht darin, die geeigneten Algorithmen und / oder Datenstrukturen aus Sicht der Softwareentwicklung kennenzulernen.

Thomas Owens

Diese 45 ist ein bisschen verdächtig; es lässt mich denken, dass Sie wollen, sin(x)wo xin Grad ist. Wenn dies der Fall ist, müssen Sie sich bewusst sein, dass das Argument für die Triggerfunktionen normalerweise im Bogenmaß lautet. Das Argument ist in C ++ im Bogenmaß angegeben. So wird diese Frage markiert.

David Hammen

Warum muss diese Frage beantwortet werden? Was ist die Anwendung?

GlenPeterson

Wie genau muss das Ergebnis sein?

Dan04

@ dan04 Da y eine ganze Zahl ist, muss sie als ganze Zahl genau sein.

LaiJong

Antworten:

Wenn der nBereich zwischen 0 und 2048 liegt, können Sie die Werte vorberechnen und dann in einem Array speichern. y(n)würde werden values[n].

vartec
quelle

+1 und Sie können für beliebige Werte dazwischen interpolieren (wenn dies möglich ist).

Daniel B

Dies ist eine praktikable Option, obwohl ich sie immer noch profilieren würde, um sicherzustellen, dass sie effizienter ist als die Berechnung (z. B. können die FPUs fsinverwendet werden und sind cachefreundlicher als einige Arrays).

Benjamin Bannier

Wie wäre es, wenn Sie den Wert [n] nicht speichern?

LaiJong

Trigonometrische Funktionen lassen sich im laufenden Betrieb nur sehr langsam berechnen. Ich bin mir ziemlich sicher, dass jede schnelle Implementierung vorberechnete Werte verwendet. Da sin () und cos () periodisch sind, müssen Sie nur die ersten 90 Grad speichern. Sie können je nach Quadrant -sin () oder sin (90 - der Winkel) oder -sin (90 - der Winkel) zurückgeben. Sie können cos () auch als sin () definieren. Wenn Sie den möglichen Bereich von Eingabewerten kennen, können Sie die Werte, die Sie für Ihr Programm benötigen, vorberechnen und nur speichern. Wenn nicht, ist die Interpolation zwischen einer begrenzten Anzahl von Werten möglicherweise die schnellste Option.

GlenPeterson

@Glen: Sin-Werte liegen zwischen -1 und 1, sodass sie tatsächlich in vorzeichenlose 16-Bit-Werte passen.

Vartec

Berechnen Sie die Tabelle zur Kompilierungszeit anstelle der Laufzeit.

Sie erstellen eine Tabelle mit 2048 Elementen mit skalierten 16-Bit-Ganzzahlwerten.

Schreiben Sie ein billiges Matlab-Skript mit einem Ausdruck, der eine Datenzeile enthält, die für Ihre endgültige Programmiersprache geeignet ist. Schneiden Sie das Ergebnis als konstante Datentabelle aus und fügen Sie es in Ihren Quellcode ein. Führen Sie zur Laufzeit eine Tabellensuche durch. Dadurch wird die anfängliche Rechenzeit anstelle der Programmstartzeit in den Erstellungszyklus verschoben.

John R. Strohm
quelle

Wie viel Laufzeit spart dies im Vergleich zu den zusätzlichen Programmiererkosten?

JBRWilkinson

Schnell und dreckig. Nett.

Quant

In Anbetracht der Form der Funktion ist die natürliche Antwort der CORDIC-Algorithmus . Es ist ein viel saubererer Ansatz als die Aufschlüsselung der Frage. Andererseits ist der benötigte Tisch viel, viel kleiner als der Tisch, den andere vorgeschlagen haben.

MSalters
quelle