Wie berechnen Computer Sündenwerte? [geschlossen]

28

Wie berechnet ein Computer einen Sündenwert? Wenn ich darüber nachdenke, ist der einzig offensichtliche Weg, viele Sin-Werte in den Speicher zu schreiben, und wenn ein Sin-Wert "berechnet" werden muss, werden einfach Daten aus einer bestimmten Speicheradresse gezogen (z. B. sin (x)) Daten aus der Speicheradresse ziehen, die den Wert von sin (x) enthält. Dies scheint der einzig mögliche Weg zu sein. Oder gibt es eine Funktion, mit der die Sünde eines Wertes berechnet werden kann? Ich versuche wirklich zu fragen, wie ein Computer die Sünde auf einer Basisebene berechnet. Gibt es eine Möglichkeit, Sin-Werte mit einer anderen Funktion zu approximieren, die aus "grundlegenderen" Operationen besteht, und die ALU wäre in der Lage, mehrere "grundlegende" Operationen durchzuführen, um den Sin-Wert zu approximieren, oder werden nur Werte aus dem Speicher abgerufen?

zack1544
quelle
10
Google "CORDIC". Google "Taylor-Serie". Und deine Gedanken über das Gedächtnis sind nicht klar.
Eugene Sh.
8
Die "Speicher" -Methode ist eine häufig verwendete Optimierungstechnik (der Name lautet "Nachschlagetabelle"). Aber nein, der Computer hat es anfangs nicht. Aber wenn Sie jemals darüber nachdenken, wie der Computer rechnet <placeholder>, googeln Sie nach " <placeholder>Berechnungsalgorithmus". Es funktioniert in den meisten Fällen besser, als nach SE zu fragen.
Eugene Sh.
5
Achten Sie neben CORDIC und Taylors auch auf Chebyshev in Verbindung mit nichtlinearen Minimax-Techniken. Taylor begrenzt den durchschnittlichen Fehler, während Chebyshev den maximalen Fehler begrenzt und sich ebenfalls schneller nähert. Minimax wird benötigt, da Konstanten nicht unendlich genau sind und auch keine Operationen. Und Sie müssen Symmetrien ausnutzen, wie verrückt!
Jonk
3
Ist dir bewusst, dass es eine Reihe gibt, mit der die Sünde berechnet werden kann, genau wie für Lattich, Protokolle, Exponenten, Pi, Quadratwurzeln usw.
Andy aka
2
Natürlich können Sie Inhalte "an erster Stelle" im Computerspeicher haben - wie denken Sie, booten Computer? Anfangswerte können in eine Schaltung verdrahtet, in Nur-Lese-Speicherzellen oder die Metallisierungsschichten eines ICs eingebaut, in Sicherungen gebrannt, als eingeschlossene Ladung gespeichert sowie von Disketten, Lochbändern oder Kippschaltern gelesen werden - jede für Software verwendbare Methode ist prinzipiell auch für vorberechnete Tabellen nützlich, und tatsächlich benötigen viele Algorithmen verschiedene Konstanten. Was am besten ist, muss wirklich auf der Grundlage der Anforderungen, der Technologie und der Ressourcen entschieden werden, die nach den anderen Anforderungen übrig bleiben.
Chris Stratton

Antworten:

30

Typischerweise werden sin (x) -Funktionen mit hoher Auflösung mit einem CORDIC-Algorithmus (CORDIATE ROTATION DIGITAL COMPUTER) implementiert, der mit einer kleinen Anzahl von Iterationen ausgeführt werden kann, wobei nur Verschiebungen und Additionen / Subtraktionen sowie eine kleine Nachschlagetabelle verwendet werden. Das Originalpapier The CORDIC Computing Technique von Jack Volder stammt aus dem Jahr 1959. Es funktioniert auch gut, wenn es mit Hardware in einem FPGA implementiert wird (und ein ähnlicher Algorithmus würde in einer Hardware-FPU für diejenigen Mikros implementiert werden, die eine FPU haben).

Für eine niedrigere Auflösung, um beispielsweise eine synthetisierte Sinuswelle für einen Frequenzumrichter oder einen Motor-VFD (Frequenzumrichter) zu erstellen, eignet sich eine Nachschlagetabelle (LUT) mit oder ohne Interpolation. Aufgrund der Symmetrie müssen die Werte nur für einen Quadranten der Sinuswelle gespeichert werden.

Wie @Temlib hervorhebt, verwenden die in modernen FPUs verwendeten Algorithmen eine Bereichsreduzierung, gefolgt von einer Auswertung mit dem Remez-Algorithmus , um den maximalen absoluten Fehler zu begrenzen. Weitere Informationen finden Sie in diesem Artikel von Intel. Formale Überprüfung der trigonometrischen Gleitkommafunktionen .

Spehro Pefhany
quelle
2
CORDIC ist eher für eine reine Hardware-Konvertierung fester Funktionen (seine erste historische Anwendung). Für einen Computer mit einer FPU sind Polynomapproximationen schneller und geeigneter, da vorhandene Arithmetikoperatoren anstelle eines speziellen CORDIC-Shift-and-Add-Geräts wiederverwendet werden.
TEMLIB
1
@TEMLIB Ja, das ist ein gültiger Punkt, das werde ich zur Antwort hinzufügen. CORDIC wurde auch in den ersten wissenschaftlichen Taschenrechnern wie dem HP-35 verwendet.
Spehro Pefhany
Meines Wissens hatte CORDIC seine erste Hardware-Implementierung im HP 9100A Tischrechner. Auf der Karte befand sich eine mit Dioden bedeckte gedruckte Schaltungskarte, die als ROM diente und die von den CORDIC-Algorithmen verwendeten Parameter speicherte.
Hot Licks
@HotLicks - Wenn Sie sich irren, wurde CORDIC fast zehn Jahre vor dem HP 9100A für einen Bordnavigationscomputer entwickelt und in diesem verwendet.
Chris Stratton
@ ChrisStratton - ich stehe korrigiert.
Hot Licks
14

Die meisten Computer-Trigger-Bibliotheken basieren auf Polynom-Approximationen , die das beste Gleichgewicht zwischen Geschwindigkeit und Genauigkeit bieten. Zum Beispiel sind ein Dutzend Multiplikations- und Additions- / Subtraktionsoperationen ausreichend, um eine vollständige Genauigkeit mit einfacher Genauigkeit für Sinus und Cosinus zu erzielen.

Dave Tweed
quelle