Wie wird intern cos/sin berechnet?

SoIntMan

Guten Morgen,

unabhängig der Programmiersprache verwendet man ja gelegentlich cos und sin Funktionen. Nach einiger Recherche
hab ich diesen tollen link gefunden [https://f1lt3r.io/roll-your-own-math-sine-cosine](Link Adresse)

Da wird das ganze mathematisch erklärt, und wie es aussieht berechnet sich der sin /cos je nach Genauigkeit mit einer entsprechend unendlichen Reihe...

Aber da bspw. in c# oder c++ die sin/cos rel. schnell ein Ergebnis liefert, aber wie das ? wird der Wert gehashed?

Bin gespannt:)

DirkB

@SoIntMan Auf Computern wird meist CORDIC verwendet.

https://de.wikipedia.org/wiki/CORDIC

und das in Hardware.

SoIntMan

@DirkB sagte in Wie wird intern cos/sin berechnet?:

@SoIntMan Auf Computern wird meist CORDIC verwendet.

https://de.wikipedia.org/wiki/CORDIC

und das in Hardware.

Ahaa.. sehr interessant, man lernt nie aus danke dir:)

wob

@SoIntMan sagte in Wie wird intern cos/sin berechnet?:

Aber da bspw. in c# oder c++ die sin/cos rel. schnell ein Ergebnis liefert, aber wie das ? wird der Wert gehashed?
Bin gespannt:)

Um eine vollständige Antwort zu erhalten, musst du den Hersteller deines Prozessors fragen. Wie der das intern exakt implementiert hat, ist vermutlich geheim - es muss ja nicht unbedingt CORDIC sein. Vielleicht irgendeine Abwandlung davon mit Geschwindigkeitsverbesserungen, zum Beispiel.

Jedenfalls muss der Compiler nur die fcos-Instruktion aufrufen (oder fsin für Sinus). Wenn du cos und sin gleichzeitig braucht, kann der Prozessor die sogar beide gleichzeitig mit fsincos berechnen - schneller als sin und cos separat. Aber Achtung: das ist natürlich Prozessor-/Architekturabhängig, das hier gilt jetzt für x87 (auf anderen Architekturen können die Befehle anders sein - vor Ewigkeiten (20y?) hatte ich mal mit einem Atmel Atmega rumgespielt, der kannte gar keine sin/cos-Befehle).

Mechanics

@SoIntMan sagte in Wie wird intern cos/sin berechnet?:

Aber da bspw. in c# oder c++ die sin/cos rel. schnell ein Ergebnis liefert, aber wie das ?

Zusätzlich zu dem was die anderen geschrieben haben, wie hast du jetzt bewertet, ob das schnell ist? Selbst die unendliche Reihe muss man nicht bis zur Unendlichkeit durchrechnen.

SoIntMan

@wob sagte in Wie wird intern cos/sin berechnet?:

Um eine vollständige Antwort zu erhalten, musst du den Hersteller deines Prozessors fragen. Wie der das intern exakt implementiert hat, ist vermutlich geheim - es muss ja nicht unbedingt CORDIC sein. Vielleicht irgendeine Abwandlung davon mit Geschwindigkeitsverbesserungen, zum Beispiel.
Jedenfalls muss der Compiler nur die fcos-Instruktion aufrufen (oder fsin für Sinus). Wenn du cos und sin gleichzeitig braucht, kann der Prozessor die sogar beide gleichzeitig mit fsincos berechnen - schneller als sin und cos separat. Aber Achtung: das ist natürlich Prozessor-/Architekturabhängig, das hier gilt jetzt für x87 (auf anderen Architekturen können die Befehle anders sein - vor Ewigkeiten (20y?) hatte ich mal mit einem Atmel Atmega rumgespielt, der kannte gar keine sin/cos-Befehle).

vielen dank, hab mir darüber nie Gedanken gemacht, dass diese explizit CPU befehle sind....:)

@Mechanics sagte in Wie wird intern cos/sin berechnet?:

Zusätzlich zu dem was die anderen geschrieben haben, wie hast du jetzt bewertet, ob das schnell ist? Selbst die unendliche Reihe muss man nicht bis zur Unendlichkeit durchrechnen.

Ich habe nicht wirklich bewertet, ich dachte nur "hmm ok, unendliche reihe, könnte lang gehen, aber wenn ich das in ner Loop aufrufe ist es echt flott" also es war ne PI mal Daumen Bewertung.. bitte nicht gleich auf die Goldwaage legen;)

DirkB

@SoIntMan sagte in Wie wird intern cos/sin berechnet?:

vielen dank, hab mir darüber nie Gedanken gemacht, dass diese explizit CPU befehle sind....:)

Das ist dann die FPU (Floating Point Unit)
Früher (damals, im letzten Jahrtausend) war das auch ein externer Baustein. Mittlerweile sind die (wenn es eine gibt) mit der CPU auf einem Chip.

Quiche Lorraine

@SoIntMan sagte in Wie wird intern cos/sin berechnet?:

Ich habe nicht wirklich bewertet, ich dachte nur "hmm ok, unendliche reihe, könnte lang gehen, aber wenn ich das in ner Loop aufrufe ist es echt flott" also es war ne PI mal Daumen Bewertung.. bitte nicht gleich auf die Goldwaage legen;)

Sorry, ich setze hier trotzdem nochmals an.

Warum? Weil ich eine sehr schöne Näherungsformel für das Berechnen einer Wurzel kenne, welche sehr schnell gegen das richtige Ergebnis konvergiert.

Die Näherungsformel für das Berechnen einer Wurzel lautet x(n+1) = 0.5 * (x(n) + a/x(n)), wobei x die Schätzwerte darstellen und a den Wert, von welchem wir die Wurzel berechnen wollen.

Nehmen wir mal an, wir wollen die Wurzel von 11 berechnen. Das Ergebnis lautet

Wurzel(11) = 3.3166247903554

Nun suchen wir einen ersten Schätzwert. Da das Ergebnis zwischen 3 und 4 liegt, wählen wir 3.5. Schauen wir uns nun die ersten 10 Iterationen an:

----- Startwert 3.5 -----

x(0) = 3.5
x(1) = 0.5*(x(0)+a/x(0)) = 0.5*(3.5+7/3.5) = 3.321428571428571
x(2) = 3.3166282642089095
x(3) = 3.316624790357219
x(4) = 3.3166247903554
x(5) = 3.3166247903554
x(6) = 3.3166247903554
x(7) = 3.3166247903554
x(8) = 3.3166247903554
x(9) = 3.3166247903554

Nach 4 Schritten sind wir schon am richtigen Ergebnis!

Aber was passiert, wenn der Schätzwert schlecht ist, z.B. 11 in unserem Fall?

----- Startwert 11 -----

x(0) = 11
x(1) = 6.0
x(2) = 3.9166666666666665
x(3) = 3.3625886524822697
x(4) = 3.316938934730457
x(5) = 3.3166248052315686
x(6) = 3.3166247903554
x(7) = 3.3166247903554
x(8) = 3.3166247903554
x(9) = 3.3166247903554

Hier dauert es nur 6 Schritte, bis wir zu dem richtigen Ergebnis kommen.

Und weil es so schön ist, nehmen wir als Startwert 30:

----- Startwert 30 -----

x(0) = 30
x(1) = 15.183333333333334
x(2) = 7.953905964141969
x(3) = 4.66843714404062
x(4) = 3.5123430342979893
x(5) = 3.3220777929006973
x(6) = 3.3166292657528187
x(7) = 3.3166247903584196
x(8) = 3.3166247903554
x(9) = 3.3166247903554

Und siehe da, es dauert nur 8 Schritte, bis wir zu dem richtigen Ergebnis kommen.

Es gibt also Näherungsformeln, welche sehr flott gegen das richtige Ergebnis konvergieren.

PS:
Der Python Code hierzu:

import math

def Root(x : float, a : float) -> None:
    for i in range(10):
        print(f"x({i}) = {x}")
        x = x = 0.5 * (x + a / x)

# Main

print("\nWurzel(11) = " + str(math.sqrt(11)))

print("\n----- Startwert 3.5 -----\n")
Root(3.5, 11)

print("\n----- Startwert 11 -----\n")
Root(11, 11)

print("\n----- Startwert 30 -----\n")
Root(30, 11)

zeropage

@Quiche-Lorraine sagte in Wie wird intern cos/sin berechnet?:

Nehmen wir mal an, wir wollen die Wurzel von 11 berechnen. Das Ergebnis lautet

Wurzel(11) = 3.3166247903554

Nun suchen wir einen ersten Schätzwert. Da das Ergebnis zwischen 3 und 4 liegt, wählen wir 3.5.

Das ist jetzt eine ernstgemeinte Frage: Woher weiß man das vorher? Klar, als Mensch kann man das abschätzen. Aber wenn man nun gar keine Ahnung hat oder eine Maschine ist, woher hat man den Schätzwert, ohne ihn auszurechnen? Nimmt man dann eine zufällige Zahl, aber in welcher Größenordnung?

Leon0402

@zeropage sagte in Wie wird intern cos/sin berechnet?:

@Quiche-Lorraine sagte in Wie wird intern cos/sin berechnet?:

Nehmen wir mal an, wir wollen die Wurzel von 11 berechnen. Das Ergebnis lautet

Wurzel(11) = 3.3166247903554

Nun suchen wir einen ersten Schätzwert. Da das Ergebnis zwischen 3 und 4 liegt, wählen wir 3.5.

Das ist jetzt eine ernstgemeinte Frage: Woher weiß man das vorher? Klar, als Mensch kann man das abschätzen. Aber wenn man nun gar keine Ahnung hat oder eine Maschine ist, woher hat man den Schätzwert, ohne ihn auszurechnen? Nimmt man dann eine zufällige Zahl, aber in welcher Größenordnung?

Ich hätte jetzt mal behauptet, dass man die Größenordnung relativ leicht angeben kann. z.B. wird das Ergbnis nicht größer als 11 sein. Das ist doch schon mal ne recht große Einschränkung.
Mann kann es auch so einschränken 3^2 = 9 < 12 & 4^2 = 16 > 12 ... Der gesuchte Wert liegt also zwischen 3 und 4. (Also sprich: Schon rechnen, aber halt nicht die Wurzel natürlich, sondern Dinge, die der Mensch / Maschine besser kann. Überschlagen quasi).

Ob das so jetzt auch wirklich gemacht wird, keine Ahnung. Wäre aber wohl sicher eine Möglichkeit

zeropage

Ja danke. Ich hatte natürlich nach meiner Frage auch weiter überlegt, wollte aber nicht ständig editieren. Das die Wurzel einer Zahl nicht größer sein kann als die Zahl selbst ist einleuchtend

hustbaer

@zeropage
Die einfachste Variante ist wohl die Ausgangszahl zu nehmen. Bei kleinen Zahlen sollte das ausreichend sein. Man braucht halt einfach ein paar Iterationen mehr. Und man muss ja nicht mit einer fixen Anzahl an Iterationen arbeiten - man kann ja prüfen wie stark sich das Ergebnis zwischen zwei Schritten ändert, und abbrechen wenn die Änderung eine bestimmte Schwelle unterschritten hat.

Wenn man das Optimum rausholen will, kann man aber auch ausnutzen dass Gleitkommazahlen intern in der Form X * 2^Y vorliegen, wobei X zwischen 1 und 2 liegt (ausgenommen Denormals). Für eine Abschätzung der Wurzel kann man also z.B. einfach 1.5 * 2^(Y/2) oder X * 2^(Y/2) nehmen. Etwas fancier wäre (1+(X-1)*K) * 2^(Y/2). Den optimalen Wert für die Konstante K müsste man ermitteln, aber er wird wohl irgendwo in der Grössenordnung 0.3 liegen. Wobei die Frage ist ob sich die zusätzlichen Rechenschritte für den (1+(X-1)*K) Teil auszahlen. Müsste man ebenfalls ausprobieren.

zeropage

@hustbaer
Joh, auch Dir danke. Ist immer schön, wie sich Fragen auflösen, wenn man gute Antworten bekommt