SIN COS Tabelle mit weniger Speicher

[Thorsten S. (whitejack)]

Hi,

habe hier folgendes im Quelltext:


float    _SIN[180];  // variables for the precalculated sin &
float    _COS[180];  // cos values


// calculate sin/cos-table
void InitTrigotable(void)
{
   int8 i;
   float a;
   for(i=0; i<180; i++)
   {
      a=(float)i*pi/90.0;
      _SIN[i]=sin(a);
      _COS[i]=cos(a);
   }
}


Ist ein bisschen happig für einen Atmega168 und das kanns so einfach 
nicht sein.
Wie gehe ich das am besten für einen 8bitter mit wenig Speicher an? Bin 
jetzt bei 230%....

Danke,
TS




Matrix4x4   temp,matWorld;      // Transformation matrices

// calculate a rotation matrix
void CreateRotateMat(int8 rx,int8 ry,int8 rz)
{
   Matrix4x4   mrot;

   // multiply the world-matrix with the rotation matrices
  M4X4_Copy(temp,MatWorld);

   M4X4_Identity(mrot);
  mrot[1][1] = _cos[rx];
  mrot[1][2] = _sin[rx];
  mrot[2][1] = -mrot[1][2];
  mrot[2][2] = mrot[1][1];

  M4X4_Mul(MatWorld,mrot,temp);

  M4X4_Identity(mrot);
  mrot[0][0] = _cos[ry];
  mrot[0][2] = -_sin[ry];
  mrot[2][0] = -mrot[0][2];
  mrot[2][2] = mrot[0][0];

  M4X4_Mul(temp,mrot,MatWorld);

  M4X4_Identity(mrot);
  mrot[0][0] = _cos[rz];
  mrot[0][1] = _sin[rz];
  mrot[1][0] = -mrot[0][1];
  mrot[1][1] = mrot[0][0];

  M4X4_Mul(MatWorld,mrot,temp);

}

[Lucas K. (lucas_k)]

Erstmal eine kleine Bemerkung mit der du den Speicher für die Tabellen 
halbieren und nur beim Zugriff ein wenig mehr draufschieben musst:

Ein Cosinus ist nur ein um 90° verschobener Sinus.

[Matthias S. (Firma: matzetronics) (mschoeldgen)]

Hier ist ein netter Generator für Sinus Tabellen:
http://www.daycounter.com/Calculators/Sine-Generator-Calculator.phtml
Nur die Zahle der Punkte eingeben und die Amplitude, per Copy&Paste 
passts direkt in dein C Array.
Und ja, nimm 16-bit Integer, alles andere frisst dem Mega die Haare vom 
Kopf. Du könntest zwar noch auf einen 328P upgraden, aber das verschiebt 
das Problem nur ein paar Tage.

[holger (Gast)]

>Wie gehe ich das am besten für einen 8bitter mit wenig Speicher an? Bin
>jetzt bei 230%....

Am besten gar nicht. Wenn du float rechnen willst nimm einen PC
oder einen STM32F4;)

Immer dieses rumgemurkse mit unterbelichteten veralteten Controllern;)

[Ulrich (Gast)]

Bei so einem kleinen µC ist oft das SRAM knapper als Flash-Speicher. 
Auch braucht der Code zum Erstellen der Tabelle mit relativ wenig 
Einträgen relativ Platz, ggf. mehr als die eigentliche Tabelle. Da ist 
es besser die Tabelle vorab zu berechnen, und als konstante Tabelle im 
Flash zu haben.  In diesem Beispiel braucht man z.B. den Code für Sin() 
und Cos() nicht mehr.

Der Zugriff auf den Flash Speicher ist allerdings etwas anders, und 
erfordert eine extra Funktion: in der Funktion kann man dann auch gleich 
zur Laufzeit ein bisschen der Symmetrie ausnutzen, also z.B. nur eine 
Tabelle für den Cosinus von 0 bis 179 oder ggf. auch nur von 0 bis 90.

Falls der Code wirklich so zeitkritisch ist, das die minimal höhere 
Rechenzeit stört, sollte man ohnehin überlegen keine Fließkomma-Zahlen 
zu nehmen, sondern mit Festkomma-zahlen rechnen.

[Super Troll (Gast)]

Weshalb float? Byte sollte genuegen. Bei einer amplitude von +-1 als 
+-128 ist man auf 1 % genau. Falls das nicht geniegt, dann geht man auf 
Word.
Ein Winkelbereich von 0 bis 45 Grad genuegt.

[Matthias S. (Firma: matzetronics) (mschoeldgen)]

holger schrieb:
> Immer dieses rumgemurkse mit unterbelichteten veralteten Controllern;)

Naja, veraltet ist er ja eigentlich nicht, aber für 
Transformationsmatrizen ist ein Mega eben einfach nicht gedacht - LEDs 
kann er aber super blinken lassen :-) Ich muss hier gerade auch Sinus 
und Cosinus mit einem Mega 88 machen, aber die Tabelle im Flash verkürzt 
die ganze Berechnung auf ein paar Taktzyklen.
Ganz zum Schluss dann von Integer auf Float und fertig is'.

[... (Gast)]

Thorsten S. schrieb:
> Wie gehe ich das am besten für einen 8bitter mit wenig Speicher an? Bin
> jetzt bei 230%....

Zu 8051-Zeiten habe ich sowas mit einer Reihenentwicklung gelöst.
Da hatte ich noch nicht den Riesenspeicher der heutigen Prozessoren.
Es bedurfte aber zur Implementierung der Anwendung des eigenen Hirns.

[Markus B. (russenbaer)]

Servus,

Wenn Du ausreichend Rechenzeit hast genügt Dir eine Viertelperiode 
abzuspeichern.

Angenommen Du speicherst cos(x) von 0-90 Grad in einer Tabelle ab, dann 
kannst Du mit folgenden Formeln den ganzen Bereich abdecken:

cos(x) = -cos(180-x) wenn x=[90 bis 180]
cos(x) = cos(360-x) wenn x=[180 bis 360]
x in Grad

Weiters gilt, wie ein anderer Poster schon geschrieben hat:

sin (x) = cos(x-90)


=> mit ein paar Abfragen und Berechnungen kommst Du, wenn Du es 
geschickt machst, mit nur 1/4 Periode durch.

Beste Grüße,
Markus

[Rufus Τ. F. (rufus)]

Eine Sinustabelle muss nicht 180 Einträge haben, 90 reichen. Man 
bedenke, daß eine Sinushalbwelle spiegelsymmetrisch ist ... und eine 
Sinusvollwelle punktsymmetrisch. Also reicht ein Viertel einer 
Vollwelle. Und wie schon einer der Vorposter bemerkte, reicht das auch 
für den Cosinus.

Dann muss die Tabelle nicht zur Laufzeit berechnet und im RAM abgelegt 
werden, sondern kann auch als Konstantentabelle ins Flash gepackt werden 
(auch wenn das Auslesen auf einem AVR "dank" der Harvard-Architektur 
etwas krampfig ist).

[Freund des Festkommas (Gast)]

Thorsten S. schrieb:
> Wie gehe ich das am besten für einen 8bitter mit wenig Speicher an?

Erste Maßnahme ist, die Floatingpoint-Library rauszuschmeißen und die 
Tabelle Off-Line zu berechnen. Die Ausnutzung von Symmetrien und 
Beziehungen zwischen Cosinus- und Sinusfunktion zur Reduktion der 
Tabellengröße wurde schon genannt.

[M. B. (Firma: TH Nürnberg) (ohmen)]

Ich habe mal das hier eingesetzt für ne Schrittmotorrampe:
http://www.mikrocontroller.net/articles/AVR_Arithmetik/Sinus_und_Cosinus_(Lineare_Interpolation)

[Alexander S. (esko)]

Super Troll schrieb:
> Ein Winkelbereich von 0 bis 45 Grad genuegt.

Ein super Trick oder nur verschrieben?

[MaWin (Gast)]

So ist es recht kompakt und rechnet nur mit 16 bit Integer Worten

static WORD intsin(WORD x)
{
    static WORD sin_table[]=
    {
  0,    572,  1144, 1716, 2286, 2856, 3425, 3993, 4560, 5126,
  5690, 6252, 6813, 7371, 7927, 8481, 9032, 9580, 10126,10668,
  11207,11743,12275,12803,13328,13848,14364,14876,15383,15886,
  16383,16876,17364,17846,18323,18794,19260,19720,20173,20621,
  21062,21497,21925,22347,22762,23170,23571,23964,24351,24730,
  25101,25465,25821,26169,26509,26841,27165,27481,27788,28087,
  28377,28659,28932,29196,29451,29697,29934,30162,30381,30591,
  30791,30982,31163,31335,31498,31650,31794,31927,32051,32165,
  32269,32364,32448,32523,32587,32642,32687,32722,32747,32762,
  32767,32767
    };
    WORD c,d,e,f;

    while(x>=3600) x-=3600;
    while(x<0) x+=3600;
    d=x/900;
    switch(d)
    {
    case 1:
        x=1800-x;
        break;
    case 2:
        x-=1800;
        break;
    case 3:
        x=3600-x;
        break;
    }
    c=x/10; /* effizienter waere x/8 = x>>3 und x%8 = x&7, dann aber */
    e=x%10; /* Tabelle von 114 Werten und /8 bei Interpolation unten */
    f=sin_table[c];
    if(e!=0)
    {
  f+=((sin_table[c+1]-f)*e)/10; /* lineare Interpolation */
  /* SMUL_DIV nicht notwendig, da sin_table[c+1]-f <= 572 */
  /* und e < 10 */
    }
    if(d>=2) return -f;
    return f;
}

static WORD intcos(WORD x)
{
    return intsin(x+900);
}

So machte es Digital Research's GEM.

[Thorsten S. (whitejack)]

Hi,

vielen Dank für die vielen Tips. Thema Geschwindigkeit muss ich noch 
klären.

Ich werde einen Teil der Möglichkeiten die Tage umsetzen, mal sehen wie 
weit ich damit komme. Tendiere zu 0-44° und der Rest wird 
hingeschoben...

Was mich jetzt gerade noch am Rande interessiert. Irgendwo habe ich mal 
eine vereinfachte Funktion ohne Float gesehen, die den Sin() ganz gut 
und rel. schnell errechnet, ohne Tabelle...

Ich habe hier schon Ansätze dazu gefunden:

http://www.mikrocontroller.net/articles/Digitale_Sinusfunktion

aber ich bin mir nicht sicher ob es das ist, zumal dort ja mehr oder 
weniger 2 Ansätze vorgeschlagen werden...

TS

[Markus B. (russenbaer)]

Meine Mathematikvorlesungen liegen schon etwas länger zurück, deshalb 
kann ich mich nicht mehr so genau erinnern, aber ich glaube es wird 
recht kompliziert nur 0-44 Grad abzuspeichern. (Willst Du mit der 
relation sinx * sinx + cosx * cosx = 1 arbeiten?)

Ich denke es ist einfacher die Werte von 0-90 Grad abzuspeichern.

Beste Grüße,
Markus

[MaWin (Gast)]

> Irgendwo habe ich mal eine vereinfachte Funktion ohne Float gesehen,

Da der Sinus eine Zahl kleiner 1 ist, wird man floats brauchen,
auch wenn man sie, wie im Algorithmus oben drüber, mit
ints die die fractional bits speichern realisiert.

Als Algorithmus kommt höchstens noch CORDIC in Frage, der aber
nicht kürzer ist als die Tabelle.