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
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
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
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
Das steht aber nicht im Zusangehang mit einer Mittelung ? Div 128 ist viel oekonomischer.
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
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
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
>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.
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
@ 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
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.
> 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
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
>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
Ok, jetzt hab ichs... Danke für den Hinweis. Hat geholfen. MfG Willi
@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
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
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
>> 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
@ 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
Ü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
@ 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
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
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
Dir ist aber schon bewusst, dass beim AVR SWAP nicht um 4 Stellen schiebt, sondern oberes und unteres Nibble vertauscht, oder? MfG, Blaubär
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
@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
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.