www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik 16 bit Div durch 100 bei AVR Mega32


Autor: Wolfram Quehl (quehl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich suche eine Problemlösung, um beim Mega32 eine 16bit Zahl durch 100 
zu teilen, ohne daß ein Großteil der Rechenzeit in Anspruch genommen 
wird. Ich hatte da was mit über 600 Takte gesehen, aber das ist mir zu 
viel. Das soll kein Selbstzweck sein, sondern ist Teil einer 
Ergebnisumwandlung.

mfg

Autor: Troll Blaubär (blaubeer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn es Teil der Wandlung 16Bit -> ASCII sein soll, dann findest Du 
Beispiele in der Cidesammlung und auch im restlichen Forum. Einfach mal 
nach "LCD" suchen, da diese Aufgabe meist in Verbindung mit LCDs zu 
lösen ist.

MfG, Blaubär

Autor: Michael Waiblinger (wiebel42)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mal 655 dann die leztzten 16Bit nehmen ist zwar nicht 100% exakt aber je 
nach Einsatzgebiet recht das dicke X*655/65536 = X/100.055. Besser wäre 
mit 41943 Multiplitzieren (2^22) wäre dann X/100.0001 braucht aber auch 
entsprechen 38bit. -wiebel

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wolfram Quehl wrote:

> Ich hatte da was mit über 600 Takte gesehen, aber das ist mir zu
> viel. Das soll kein Selbstzweck sein, sondern ist Teil einer
> Ergebnisumwandlung.

Was meinst Du damit, etwa für eine Anzeige ?

Dann sind 600 Zyklen bei weitem schnell genug, kein Mensch kann so 
schnell ablesen.

Im Gegenteil, Du mußt extra noch ~200ms (4.000.000 Zyklen) Delay 
einfügen, damit die Zahlen nicht flimmern.

Max 2..5 Anzeigewerte pro Sekunde sind ergonomisch.


Peter

Autor: Nailpainter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das steht aber nicht im Zusangehang mit einer Mittelung ? Div 128 ist 
viel oekonomischer.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nailpainter wrote:
> Das steht aber nicht im Zusangehang mit einer Mittelung ? Div 128 ist
> viel oekonomischer.

Ich finde schon, daß man jemand darauf hinweisen sollte, wenn er 
Probleme sieht, die gar keine sind.

Gerade Anfängern fällt es schwer, die benötigten CPU-Zeiten richtig 
einzuschätzen.


Peter

Autor: Nailpainter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, sicher. Deshalb ja auch mein Beitrag. Dass man besser uber 64 , oder 
128 Messungen addiert und teilt ist fuer den Anfaenger nicht 
offensichtlich. Der Beitrag, dass ein zu haeufiges visuelles Resultat 
unguenstig ist, ist auch gut. Oder dass manchmal reduzierte Genauigkeit 
genuegt, auch. Fuer einfach eine Rechnung haette ich (+ 1/4) div 128, 
ist besser als 3%, vorgeschlagen

Autor: Wolfram Quehl (quehl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
das Meßergebnis muß linearisiert werden und da steht in der Formel durch 
100. Da kann ich nicht durch 128 teilen. Der Fehler erscheint mir dann 
zu groß. Aber der Ansatz von Wiebel erscheint mir gut. Ich habe ja auch 
geschrieben Teilaufgabe, daher wird das Ergebnis nicht angezeigt. Ich 
neige zwar dazu, die optimale Geschwindigkeit zu programmieren, weil ich 
vorher noch nicht weiß, wie das Ergebnis aussehen wird. Langsamer wird 
alles von alleine. Das sieht man ja an Windows. Das hat auch nichts mit 
LCD zu tun.
Nur eine kleine Abweichung könnte ich zulassen.

mfg

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Der Fehler erscheint mir dann zu groß
Das ist der erste Fehler. DU bist der Programmierer. DU weißt welche 
Genauigkeit gefordert ist. Eventuelle mußt DU sie festlegen. Anscheinend 
hast du das noch nicht getan.
Also nicht der Fehler "scheint" mir zu groß, sondern der Fehler ist zu 
groß oder ist nicht zu groß.

Wenn der Fehler zu groß ist, denke an die Schule zurück. 5-6 Klasse 
Bruchrechnung. Eine Zahl kann man erweitern.
10000/100 ist auch 100. Ich denke du bist in der Lage einen Bruch mit 
128 als Teiler zu bilden der 100 ergibt oder zumindest eine hinreichende 
Genauigkeit für deine Rechnung garantiert. Es steht dir natürlich auch 
frei jeden anderen Teiler mit 2^n zu nehmen.

Autor: Troll Blaubär (blaubeer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wolfram wrote:

> Es steht dir natürlich auch
> frei jeden anderen Teiler mit 2^n zu nehmen.

Genau, mein Favorit wäre 256, das spart Shifterei.

MfG, Blaubär

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Troll Blaubär (blaubeer)

>> Es steht dir natürlich auch
>> frei jeden anderen Teiler mit 2^n zu nehmen.

>Genau, mein Favorit wäre 256, das spart Shifterei.

Ist alles ne Frage der Genauigkeit.

1/100 = 2,56/256 = 655,36/65536 = 167772,16/16777216 = 42949672,96 / 
4294967296

Wenn man nun auf ganze Zahlen rundet

1/100 = 3/256 = 655/65536 = 167772/16777216 = 42949673 / 4294967296

ergibt das ein Fehler von

0%     -14,6%    -0,054%      -0,0000953%       0,0000000931%

Na, immer noch ein Fan von 256?

MfG
Falk

Autor: Nealpotter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schaut doch gut aus. Mit einer Multiplikation mit 655, dh 6 additionen 
und 6 shifts ist man dabei und kriegt einen Fehler von 0.054% . super.

Autor: Troll Blaubär (blaubeer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Genau, mein Favorit wäre 256, das spart Shifterei.

Nachtrag: Oder eine Potenz davon (2^8, 2^16, 2^24, 2^32), je nachdem, 
was für den Einzelfall sinnvoll ist. Aber möglichst so, dass hinterher 
keine (oder möglichst wenig) Bitscheberei erforderlich ist.

Falk Brunner wrote:
> Na, immer noch ein Fan von 256?

Ja sicher doch, immer noch ein Fan von ganzen Bytes. Wenn die ersten 256 
nicht reichen, dann werden eben die nächsten hinzugefügt. Vielleicht 
solltest Du einen eingebrachten Gedanken mal zu Ende denken ehe Du 
darüber herfällst. ;-)

Die von mir genannten 256 sollten nur die zuvor genannte 128 in Frage 
stellen und zum Weiterdenken animieren.

MfG, Blaubär

Autor: Tippgeber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mal ein Beispiel für eine Division durch 10:

DivBy10

unsigned int A;
unsigned int Q; // the quotient

Q = ((A >> 1) + A) >> 1; // Q = A*0.11
Q = ((Q >> 4) + Q)     ; // Q = A*0.110011
Q = ((Q >> 8) + Q) >> 3; // Q = A*0.00011001100110011
// either Q = A/10 or Q+1 = A/10 for all A < 534,890

Der geneigte Leser möge es als Übungsaufgabe jetzt mal mit 100 
versuchen.

Hier das ganze für den MSP430:

  push  R14
  clrc
  mov  R15,R14
  rrc  R15
  add  R14,R15
  rrc  R15
  mov  R15,R14
  clrc
  rrc  R15
  rra  R15
  rra  R15
  rra  R15
  add  R14,R15
  mov  R15,R14
  swpb  R15
  and  #0ffh,R15
  add  R14,R15
  clrc
  rrc  R15
  rra  R15
  rra  R15
  pop  R14
  inc  R15
  ret

Autor: Tippgeber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
P.S.:
Frei nach der Appnote SLAA329 von TI ;-)

Autor: Willi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>DivBy10
>
>unsigned int A;
>unsigned int Q; // the quotient
>
>Q = ((A >> 1) + A) >> 1; // Q = A*0.11
>Q = ((Q >> 4) + Q)     ; // Q = A*0.110011
>Q = ((Q >> 8) + Q) >> 3; // Q = A*0.00011001100110011
>// either Q = A/10 or Q+1 = A/10 for all A < 534,890


Sorry, das verstehe ich nicht, irgendwo hakt es bei mir.
Könnte mir bitte mal jemand die letzten vier Zeilen erläutern ?

Vielen Dank

Willi

Autor: Tippgeber (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
dezimal: 1/10=0.1
binär: 1/10=0.00011001100110011......

Autor: Willi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, jetzt hab ichs...
Danke für den Hinweis. Hat geholfen.

MfG Willi

Autor: Wolfram Quehl (quehl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Wiebel und Falk Brunner

Danke, diese Ideen sind noch die Besten.
Bei 16 bit wie im Betreff angegeben werde ich aber keine höhere 
Genauigkeit erreichen, wenn ich die 24 bit oder 32 bit Multiplikation 
verwende. Max. kommen immer 655 raus. Auch wenn ich die 4 mille 
verwende. Darum hat die 4 mille keine bessere Genauigkeit als die 65536 
Version.
Aber für andere Zwecke oder Aufgaben kann das sicher sinnvoll sein, das 
dann ggf. auch mal zu betrachten.

mfg

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Diese Lösung hat +0.097% Fehler, kommt aber ohne Multiplikation aus:

1/100 ~ (1+1/4+1/32)/128, also q=(x+(x>>2)+(x>>5))>>7;

Cheers
Detlef

Autor: Troll Blaubär (blaubeer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Detlef _a wrote:
> Diese Lösung hat +0.097% Fehler, kommt aber ohne Multiplikation aus:
>
> 1/100 ~ (1+1/4+1/32)/128, also q=(x+(x>>2)+(x>>5))>>7;
>
> Cheers
> Detlef

Der Mega32, mit dem das realisiert werden soll, hat 
Hardware-Multiplikation, kann also innerhalb 2 Takte zwei Bytes 
multiplizieren. Beim Shiften fehlt im aber die Leistung, da er in einem 
Takt nur um 1 Bit innerhalb eines Bytes shiften/rotieren kann, mehr gibt 
seine Architektur nicht her. Deshalb ist Deine Lösung, die auf anderen 
Controllern (die mit einem Befehl über mehrere Stellen shiften/rotieren 
können) höchst effizient sein mag, beim Mega32 vermutlich etwas 
aufwendiger als die Hardware-Multiplikation.

MfG, Blaubär

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> kann also innerhalb 2 Takte zwei Bytes multiplizieren.

ja genau, Bytes. Wolfram will 16Bit verarbeiten und die '655' paßt auch 
nicht in ein Byte, dadurch wird der m.E. der Aufwand bei Multiplikation 
sehr viel höher. Machen wir uns nix vor, die Megas können schlecht 
multiplizieren UND schlecht schieben.

Cheers
Detlef

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Detlef _a (detlef_a)

>> kann also innerhalb 2 Takte zwei Bytes multiplizieren.

>ja genau, Bytes. Wolfram will 16Bit verarbeiten und die '655' paßt auch
>nicht in ein Byte, dadurch wird der m.E. der Aufwand bei Multiplikation
>sehr viel höher. Machen wir uns nix vor, die Megas können schlecht
>multiplizieren UND schlecht schieben.

???

eine 16x16 Bit Multiplikation besteht aus maximal 4 8x8 Bit 
Multiplikationen, der GCC schafft es irgendwie mit 3. Das Schieben 
dürfte deutlich länger dauern.

<C>
#include <avr/io.h>

int main (void) {
  uint16_t a,b;
  uint32_t c;

  c = a*b;

  return 0;
}
</C>

<AVRASM>
  c = a*b;
  96:  29 81         ldd  r18, Y+1  ; 0x01
  98:  3a 81         ldd  r19, Y+2  ; 0x02
  9a:  8b 81         ldd  r24, Y+3  ; 0x03
  9c:  9c 81         ldd  r25, Y+4  ; 0x04
  9e:  28 9f         mul  r18, r24
  a0:  a0 01         movw  r20, r0
  a2:  29 9f         mul  r18, r25
  a4:  50 0d         add  r21, r0
  a6:  38 9f         mul  r19, r24
  a8:  50 0d         add  r21, r0
  aa:  11 24         eor  r1, r1
  ac:  ca 01         movw  r24, r20
  ae:  aa 27         eor  r26, r26
  b0:  bb 27         eor  r27, r27
  b2:  8d 83         std  Y+5, r24  ; 0x05
  b4:  9e 83         std  Y+6, r25  ; 0x06
  b6:  af 83         std  Y+7, r26  ; 0x07
  b8:  b8 87         std  Y+8, r27  ; 0x08

</AVRASM>

MFg
Falk

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Überzeugt, Multiplikation.

Dann aber die 16Bit Multiplikation richtig ausnutzen:

1/100 ~ 10486/(2^20) also q=(10486*x)>>20;

macht +0.0023% Fehler.

Das ist mit int16 Multiplikationen das Optimum. Der shift um 20 läßt 
sich umgehen mit Zuweisungen und dem 'swap' Befehl der Megas.

Schieben/aaddieren ist das Verfahren der Wahl bei FPGAs: addieren ist 
billig und schieben kost nix.

Cheers
Detlef

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Detlef _a (detlef_a)

>Überzeugt, Multiplikation.

Uups, das klappt ja nicht. Es fehlt der Cast auf 32 Bit, die Rechnung 
macht nur 16x16 und einen schönen Überlauf! Mit Cast ist die 
Schiebevariante wieder schneller, denn die 32x32 Bit Multiplikation 
braucht 10 MUL.

>Schieben/aaddieren ist das Verfahren der Wahl bei FPGAs: addieren ist
>billig und schieben kost nix.

Yep.

MfG
Falk

Autor: Troll Blaubär (blaubeer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es soll aber in Assembler gearbeitet werden.

MfG, BlauBär

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Na, wenns denn mit der Multiplikation doch nich geht, hier nochmal ne 
Variante 0.0023% mit nur schieben:

1/100 ~ (1+1/2+1/16-1/512-1/2048)/256

q=x+x+(x>>1); // 1 mal schieben
x>>=4       ; // 1mal swap
q+=x        ;
x>>=1       ; // 1mal schieben
x>>=4       ; // 1mal swap
q-=x        ;
x>>=2       ; // 2 mal schieben
q-=x        ;
q>>=8       ;

Cheers
Detlef

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Detlef _a wrote:
> 1/100 ~ (1+1/2+1/16-1/512-1/2048)/256

Ähm, so:

 1/100 ~ (2+1/2+1/16-1/512-1/2048)/256


Cheers
Detlef

Autor: Troll Blaubär (blaubeer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dir ist aber schon bewusst, dass beim AVR SWAP nicht um 4 Stellen 
schiebt, sondern oberes und unteres Nibble vertauscht, oder?

MfG, Blaubär

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was macht:

>>  x >>= 2

??

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ja.

So:
//0xabcd
highbyte=swap(Highbyte); //0xbacd
lowbyte =swap(lowbyte) ; //0xbadc
lowbyte =(lowbyte&0xf)|(highbyte&0xf0);//0xbabc
highbyte=highbyte&0xf;//0x0abc

Vielleicht auch nicht viel kürzer als 2*4 shifts durch das carry. Mit 
nem scharfen Blick auf den Befehlssatz des AVR sollte sich 
möglicherweise noch was besseres finden lassen, der Tausch der Bytes z.B 
mit XOR oder so. Den Megas fehlt der Barrelshifter.

Cheers
Detlef

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@lippy:

x >>=2 ist die Kurzform von x= x >> 2, das schiebt die Bits von x 2 
Stellen nach rechts, teilt den Wert also durch 4.

Cheers
Detlef

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
aso, ja klar.
wie

x += 1;

Danke

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.