Diskussion:Schnelle 32Bit-Integer Sinusberechnung

Fragen und Probleme mit dem Code

Mit dem aktuellen Code ergeben sich einige Probleme:

• Je nach Plattform ist int lediglich 16 Bits breit: Der C-Standard garantiert mindestens 16 Bits für int, mehr jedoch nicht. Lösung wäre die Verwendung von stdin.h von C99 und Vermeidung von Überläufen wie sie momentan auftreten.
• Falls die Architektur nicht über Divisionsbefehle verfügt (Beispiel: AVR), ist die Berechnung keineswegs als "schnell" zu bezeichnen.
• Die angegebene Genauigkeit von 0.1% entspricht 10 Binärstellen. Es stellt sich die Frage, warum dafür überhaupt 32-Bit Arithmetik verwendet wird.
• Die Eingabe erfolgt in Grad, es sind also nur 91 Eingaben (0°...90°) möglich falls man sich auf den ersten Quadranten beschränkt. Dies erfordert eine Rundung der Eingabe auf ganze Grade, was einen Rundungsfehler von bis zu pi/360 bedingt. Dies entspricht einer Genauigkeit von nur 7 Binärstellen, was schneller, einfacher und kürzer durch eine 91 Byte große Lookup-Table bewerkstelligt werden kann.

--Gjlayde (Diskussion) 11:15, 28. Okt. 2013 (CET)

• Die 0.1% wird nicht erreicht, ich habe einen relativen Fehler von 2.59% bei 359 Grad, mit mehr Dezimalstellen geht der Fehler exponentiell hoch. Der durchschnittliche Fehler liegt bei 0.19472% .
• bei 360 Grad gibt es 9 Werte, wo der Fehler dann über 1% liegt, ansonsten ist er unter 1%. Eventuell würde sich hier eine IF Abfrage auszahlen.
• div10 kann man mit (x*205)>>11 realisieren, eventuell auch mit (x*26)>>8 bei dem begrenztem Wertebereich.
• die Modulo Operation sollte man durch while oder if ersetzen und die quadrant%2 durch ein and.
• Bei Auflösung unter einem Grad muss man entweder interpolieren, bzw sollte man einen anderen Code verwenden.

--Schris (Diskussion) 04:50, 31. Okt. 2013 (CET)

Inzwischen frag ich mich, ob ein simples [math]\displaystyle{ \sin(x+\epsilon) \approx \sin(x) + \epsilon \cos(x) }[/math] nicht besser geeignet wäre als die Formel im Artikel. Leztere erscheint zunächst zwar smart, allerdings multipliziert sie fehlerbehaftete Größen miteinander, so dass sich die Einzelfehler addieren.

Weiters wäre eine Fehlerabschätzung ganz nett, so dass man weiß, was man sich da an Land zieht. Die angegebenen 0.1% scheinen ja nicht zu stimmen. Mit relativen Fehlern muß man hier jedoch vorsichtig sein, da auch sin(0) bzw. sin(pi) etc. berechnet werden; dies ergibt dann relative Fehler von undendlich.

Viele der Vorschläge für die Grundarithmetik sind wohl auf AVR gemünzt aber für machtigere Architekturen wie ARM nicht vorteilhaft.

--Gjlayde (Diskussion) 19:38, 31. Okt. 2013 (CET)

• viele ARM haben keine HW Division. also doch zutreffend.

Datei:Sinus.c --Schris (Diskussion) 21:35, 31. Okt. 2013 (CET)

Optimierung

Wenn man 16 Stützstellen nimmt, kann die /10 Division durch eine Schiebeoperation optimiert werden.

Es verbleiben aber immer noch Divisionen bzw. Modulo durch 360 und 90. --Gjlayde (Diskussion) 13:59, 28. Okt. 2013 (CET)

Ginge mit INT und Abziehen direkter und einfacher. 87.166.187.53 21:05, 28. Okt. 2013 (CET)

Wenn nicht rad, dann könnte man anstatt in einer 360° Welt auch gleich in einer 256 oder 1024 Einheiten-Welt arbeiten. 07:02, 29. Okt. 2013 (CET)

Kommentar des Autors

Zugegeben, ich arbeite nur noch mit 32Bit-Arm Controllern und habe nicht über eine 8Bit Optimierung oder die Reduktion von Divisionen nachgedacht. Da gibt es sicher noch ein paar Optimierungsmöglichkeiten. Wichtig war mir, das Verständnis für einen so einfachen Algorithmus mit nur 188Byte code (CortexM4) zu erzeugen.

Vorschlag: Optimiert das doch für 8Bit und mit Bitschift-Divisionen und wir bieten das als zusätzlichen Download mit an.

MPetschke

Das ist ziemlich witzlos, weil schon jede Lookup-Tabelle für 8 Bit (256 Stützstellen) kleiner sein dürfte, als irgendwelche Berechnungen... --Haku (Diskussion) 11:27, 29. Okt. 2013 (CET)

256 Stützstellen sind garantiert größer als der vorliegende Code. MPetschke

Vertu dich da mal nicht. Ist immerhin ein 8-Bitter ohne Hardware-Dividierer. Und dann ist die Rechenzeit noch nicht berücksichtigt. Schon allein die Ganzzahl-Divisionsroutine frisst etwa 80 Bytes. Dazu kommen die je zehn Stützstellen für Sinus und Cosinus mit insgesamt 40 Bytes. Die Routine selbst braucht nochmals 192 Bytes. Macht insgesamt also rund 300 Bytes, bei starker Optimierung (-O2, avr-gcc 4.7.2). Spart bei ganzzahligen Winkeln also eigentlich quasi fast nichts und braucht noch viel mehr Rechenzeit als eine Tabelle mit 360 Einträgen. --Haku (Diskussion) 19:02, 29. Okt. 2013 (CET)

Sehr tolles Projekt!! und eine sehr interessante Diskussion. Aber anstatt zu diskutieren: Erweitert den Artikel doch einfach um einen Vergleich. 91.50.136.153 29.Okt.2013 - 20:26

Das würde ich auch begrüssen. Ich blicke kaum noch durch, wie schnell, wie gross und genau der Alog nun ist im Vergleich zu einer reinen Tabelle, einem Cordic oder eine tabellenbasierten Interpolation, wie sie hier beschrieben ist: Digitale_Sinusfunktion 87.166.170.19 14:41, 1. Nov. 2013 (CET)

Ergebnis für 8 Bit AVR-GCC

Der AVR-GCC-Compiler macht aus diesem Code mit 16Bit integer, (nur die Multiplikationen als long) 272 Bytes. Das sind 84Byte mehr als bei einem 32Bit-Arm. Jetzt kann sich jeder selbst ein Bild machen.

MPetschke