Diskussion:AVR Arithmetik/Sinus und Cosinus (Lineare Interpolation)
Hallo,
ich dachte mir schon, dass jetzt das Übergabeformat für lineare Interpolation sich gegenüber Cordic ändert, um leichter rechnen zu können ;-) Mein Vorschlag von 0.16 als Zahlenformat bei der Cordic-Diskussion Diskussion:AVR Arithmetik/Sinus und Cosinus (CORDIC),
bezog sich nur auf die Tabelle selbst linsin_tab:
..const int16_t linsin_tab[91] PROGMEM = ... Damit wäre ein Bit Genauigkeit gewonnen, ohne am Platzbedarf etwas zu ändern.
Eine quadratische Interpolation mit den Werten:
a := sintable[i]; b := sintable[i+1] /2; c := sintable[i-1] /2; // Parabel durch sintable[i-1],sintable[i],sintable[i+1] sinquadratNaeh := ((b+c-a)*frak + b-c)*frak+a; //oder sinquadratNaeh := (Diff2*frak + Diff1)*frak+a; Ließe sich auch in einer Tabelle speichern, in der a,diff1,diff2 in einer Reihe stehen, speichern type tfloat = 1.15; tquaTab = record Diff2,Diff1,a: Tfloat; end; const quaTable = array [-1,16] of tquaTab;
Das schöne daran ist, man kann mit frak im Bereich -1..1 rechnen.
sinquadratNaeh(i,Frak=-1) = sintable[i-1]; sinquadratNaeh(i,Frak=0) = sintable[i]; sinquadratNaeh(i,Frak=1) = sintable[i+1];
Man kommt also mit einer halben Tabelle aus. Wenn man Tabelle [1,frak=0] rechnen will, kann man man Tabelle[0,frak=1] oder Tabelle[2,frak=-1] rechnen, oder Tabelle[1,frak=0.7]=Tabelle[2,frak=0.7-1] Damit kann Tabelle[1] wegfallen. Weil aber die Genauigkeit etwas darunter leidet, braucht man vielleicht einen Tabellenplatz mehr. Ausserdem müssen die Konstanten anders skaliert sein, da Diff2>0 und Werte im Bereich von -0.004815..0 hat müßte um -256 erweitert werden, damit daraus noch etwas vernünftiges wird.
Nun fehlt noch die klassische Taylor-Reihe, mit weniger Konstanten:
Taylor Reihe für x im Bogennmass:
sin(x) = x-x^3/3!+x^5/5!-x^7/7!+..-..+ mittels Horner Schema, wenn man weiß wann man aufhören will. sin(x) = x*(1/1 - x^2/(2*3)*(1-x^2/(4*5)*(1-x^2/(6*7)*(1-x^2...-x^2/((2*n-2))*(2*n-1)){n-fach})) function SinTaylor(x:float):float; var x2 : float; i,n,n2_1:integer; begin n := 7; // anpassen an geforderte Genauigkeit x2 := x*x; n2_1 := n+n-1; result := 1.0; For i := n downto 2 do begin result := 1-x2/((n2_1-1)*n2_1)*result; n2_1 := n2_1-2; end; //den Rest mal x result := x*result; end;
oder schneller mit Tabelle der Kehrwerte:
function SinTaylor(x:float):float; const rezSinFakt : array[0..4] of float(oder 1.15/0.16 ... ) = (1/(2*3), 1/(4*5) ,1/(6*7) ,1/(8*9) ,1/(10*11)); rezCosFakt : array[0..4] of float = (1/(1*2), 1/(3*4) ,1/(5*6) ,1/(7*8) ,1/(9*10)); var x2 : float; i:integer; begin Umwandeln von x in Bogenmass x Auf den Bereich 0..pi/2 bringen, passendes Vorzeichen merken falls x >= 1 dann x = pi/2-x -> cos_rechnen = true damit bleibt x< 1 und x^2<1 da man bei sin_rechnen ab x=0.69 sowieso schon dreimal durch die Schleife muss und für x = 1 die Genauigkeit dann bei 17.5 Bit liegt (Taschenrechner) x2 := x*x; result := 1.0; if not(cos_rechnen) then begin For i := 4 downto 0 do begin result := 1-x2*result*rezSinFakt[i] end; result := x*result; end else //cos_rechnen begin For i := 4 downto 0 do begin result := 1-x2*result*rezCosFakt[i] end; end; Vorzeichen anpassen end;
Da es eine alternierende Reihe ist, wird der Abbruchfehler kleiner als das erste weggelassene Glied. Hier also delta < x^13/13! (x= 1 → delta < 1.6 e-10 (auf meinem Aldi-Taschenrechner 2.17e-10) )
Für eine Genauigkeit von 2^-15 reicht für sin Rechnung: bis x[rad] = 0.23 For i := 0 downto 0 bis x[rad] = 0.69 For i := 1 downto 0 bis x[rad] = 1.19 For i := 2 downto 0 Multiplikationen ( 1.15 x 1.15-> 1.15) : 1 (x^2)+1 (x*result) + 2*Anzahl Schleifendurchläufe Multiplikationen : (1+Anzahl Schleifendurchläufe)*2
Also statt 16 Multiplkationen wie bei Cordic (aber nur, weil es keinen schnellen Shifter gibt) maximal 8 für sin+cos Berechnung also etwa gleich schnell oder schneller.
Ich schon sagen, dass Du Dir ausgesprochen viel Mühe gibst.
Heisst das heute chapeau oder Hut ab ?
- Wie an der Abschätzung für die linsin_tab zu erkennen, wird der Fehler dominiert durch den Eingabefehler im Bereich von 2 Inkrementen, nicht durch den Interpolationsfehler. Dementsprechend wird eine Umstellung auf eine 0.16-Tabelle keine wesentliche Verkleinerung des Fehlers bringen. Eine Probeimplementierung bestätigt dies: die Standardabweichungen werden zwar was kleiner, aber die Maximalfehler bleiben unverändert.
- Die Implementierungen habe ich aus Interesse gemacht – es ging mit nicht darum, den ganzen Zoo von denkbaren sin-Implementierungen für AVR durchzunudeln. Meine mathematische Intuition sagt mir immer noch, daß Taylor nicht sinnvoll ist (u.a. gerade weil die Reihe alternierend ist) und quadratische Interpolation mit unangenehmen Fußangeln aufwartet.
- Im übrigen rechnet man nicht im Intervell [-1,1] sondern in [-1,1) bzw. hier – da zunächst keine negativen Werte auftauchen – in [0,1).
- Da mit der linearen Interpolation eine Implementierung mit halbwegs akzeptabler Laufzeit zur Verfügung steht, wäre eher zu überlegen, CORDIC auf Codegröße zu optimieren anstatt auf Geschwindigkeit. Ohne Fallunterscheidungen und mit Schiebeschleifen anstatt Multiplikation solle deutlich an Flash gespart werden können – natürlich auf Kosten der Laufzeit. --Gjlayde 10:08, 26. Jul. 2009 (CEST)
Hallo,
ich habe es mal mit Taylor simuliert( mit smallint ) und vorerst nur Winkel von 0..32787 /32767 also von 0..1 im Bogenmass betrachtet.
abs. Abweichung: Anzahl -2: 0 -1: 2791 0:27291 1: 2686 2: 0
bis 590 keine Iteration, bis 8100 ( 14.16° ) eine, bis 18000 (31.47°) zwei und dann drei bis 57.29°. Also kommt nie eine Abweichung von +-2 zustande.
Lange Rede keinen Sinn. Warum sollte man Cordic nutzen, wenn es Abweichungen bis +-7 hat und nicht schneller rechnet?
program TayLorTest; type tfloat = smallint; var i : smallint; count: longint; Fehler :array[-10..10] of longint; function SinTaylor(x:tfloat):tfloat; const // (1/(2*3), 1/(4*5) ,1/(6*7) ,1/(8*9) ,1/(10*11) *65536); rezSinFakt : array[0..2] of smallint = (10923,3277,1560); var x2 : longint; i : shortint; cos_rechnen:boolean; begin If x > 590 then begin result := $7FFF;//= 1 IF (x >= 0) AND (x <= 32767) then begin x2 := (x*x ) shr 15; i := 2; if x < 18000 then i := 1; if x < 8100 then i := 0; while i>= 0 do begin result := $7FFF - result*((x2*rezSinFakt[i]) shr 16 ) shr 15; dec(i); end; result := x*result shr 15; end; // else cos (90-alpha) = 51472-x rechnen end; else // x < 590 result := x-1; inc(count); inc(Fehler[round(result-int(32768*sin(x/32768)))]); end; begin for i := -10 to 10 do Fehler[i]:= 0; count:= 0 ; for i := 0 to 32767 do sinTaylor(i); for i := -10 to 10 do write(i:4,Fehler[i]:12); writeln(count) end.
- CORDIC ist leicht zu implementieren. Im Vergleich zu Taylor dürfte eine deutlich schlankere Implementierung möglich sein. Zudem braucht er keine Multiplikation, taucht also auch für Tiny AVR. Weiterer Vorteil ist, daß man nicht auf einem erweiterten Wertebericht rechnen muss.
- Anstatt Taylor würde ich eher mit einem polynomialen Best-Fit experimentieren . Den Fit startet man mit der Taylorreihe um π/4 und optimiert die Fit-Koeffizienten zur Minimierung des Maximalfehlers hin.
Oder eine quadratische Interolation explizit machen, dann aber /konkret/ was lauffähiges auf AVR.
- Allerdings stellt sich die Frage, wozu man sowas auf einem AVR überhaupt braucht. Gehen wir von einer Fräse aus, die einen Radius von 1m rausknabbern soll, dann liegt der Maximalfehler bei 60µm bzw 0.0035°. Das sollte ausreichen. Für noch höhere Auflösung muss man eh Sonderlocken in Angriff nehmen. Komplexe Multiplikation dürfte wegen der Fehlerakkumulation nicht so prickelnd sein. Denkbar ist auch ne langsame Berechnung eines Startwertes und -fehlers im Zusammenspiel mit Bresenham. --Gjlayde 23:57, 27. Jul. 2009 (CEST)
Sinus und Cosinus: Präzision der linearen Approximation
(Frage kopieret von [1]. Bitte nicht in einen Artikel reinkritzeln. Für Fragen gibe es Diskussionsseiten und das Forum.)
Eigentlich reicht eine Berechnung von sin(0..45°) weil sin(x) = 1-sin(90°-x), oder? Das würde die Präzision bei gleicher Codegrösse etwa verdoppeln...
- Nein, die Gleichung ist nicht korrekt: Es ist sin(π/2-x) = cos(x) und es ist cos + sin ≠ 1. --Gjlayde 00:32, 17. Feb. 2012 (UTC)