Diskussion:AVR Arithmetik/Sinus und Cosinus (Lineare Interpolation)

Aus der Mikrocontroller.net Artikelsammlung, mit Beiträgen verschiedener Autoren (siehe Versionsgeschichte)
Wechseln zu: Navigation, Suche

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)
Abgerufen von „https://www.mikrocontroller.net/index.php?title=Diskussion:AVR_Arithmetik/Sinus_und_Cosinus_(Lineare_Interpolation)&oldid=64352“