Hallo!
Ich habe hier einen Mega644 mit 20MHz und WinAVR-20080512. Ich habe ein
Stueck Code, in dem eine 16-bit-Zahl durch 3 geteilt wird:
sPos/=3;
Nun habe ich bemerkt, dass diese Division "unendlich" lange dauert (ca.
2-3ms!!). Die gleiche Divsion habe ich nun mit Schieben realisiert:
sPos=(sPos>>1)-(sPos>>3)-(sPos>>5)-(sPos>>7);
Das geht wiederum im Vergleich "blitzschnell" (ist eine
Quick&Dirty-Loesung und nicht sonderlich genau, also bitte nicht
steinigen).
Das hat mich sehr gewundert, denn der Atmel hat doch einen
Hardware-Divider.
Daraufhin habe ich mir den Assembler-Code angeschaut. Dort ist zu sehen,
dass die Division mit einem call auf __divmodhi4 gemacht wurde..
Kann mir das vielleicht jemand erklaeren?
Gruss
Th.
ich kann leider nichts dazu sagen.
aber ich habe eine Frage zu einer Sache die ich hier jetzt schon öfters
gesehen habe:
sPos=(sPos>>1)-(sPos>>3)-(sPos>>5)-(sPos>>7)
Wenn ich das richtig verstehe, soll die das dividieren nur mit
addition/subtraktion und schiebebefhlen durchgeführt werden?
wie kommt man denn auf diese Formeln? gibts da einen Trick oder Kniff m
möglichst schnell sowas aufzustellen?
Axel Preuss wrote:
> ich kann leider nichts dazu sagen.>> aber ich habe eine Frage zu einer Sache die ich hier jetzt schon öfters> gesehen habe:>> sPos=(sPos>>1)-(sPos>>3)-(sPos>>5)-(sPos>>7)>> Wenn ich das richtig verstehe, soll die das dividieren nur mit> addition/subtraktion und schiebebefhlen durchgeführt werden?> wie kommt man denn auf diese Formeln?
Fasse die Schiebebefehle als Divisionen durch 2-er Potenzen
auf.
1 mal nach rechts schieben ist ident zu / 2
2 mal / 4
3 mal / 8
4 mal / 16
5 mal / 32
6 mal / 64
7 mal / 128
8 mal / 256
und jetzt setzt du eine beliebige Division zusammen.
Die Behauptung oben war
x/3 = x/2 - x/8 - x/32 - x/128
x/3 = 64x/128 - 16x/128 - 4x/128 - x/128
x/3 = ( 64x - 16x - 4x - x ) / 128
x/3 = 43x / 128
x/3 = 0.3359 * x
0.3359 ist nahe genug an 1/3, so dass das für moderate Zahlen x
genau genug sein wird.
gibts denn auch eine Regel wie man die Teiler bestimmt oder muss man
ausprobieren?
Also woher weiss ich welche ich brauche und welche nicht?
bei /3 so: /2 /8 /32 /128
was bei /5 oder /6 ??????
Karl heinz Buchegger wrote:
> tt wrote:>> gibts denn auch eine Regel wie man die Teiler bestimmt oder muss man>> ausprobieren?>> Regel kenn ich keine.
Aber man kann das systematisch probieren.
du nimmst erst mal /2 und nimmst dann probehalber jeden der
Faktoren /4 /8 /16 ... in der Reihenfolge dazu und siehst nach
ob das Ergebnis zu gross oder zu klein ist. Je nachdem bleibt
er drinnen oder auch nicht.
/5 x/5 = 0.2 x
Da nehmen wir mal /2 das Ergebnis lautet also bisher x/2
Probehalber mal /4 mit dazu
x/2 - x/4 = 2x/4 - x/4 = x/4 = 0.25 x
also zu gross, daher /8 noch mit dazu
x/2 - x/4 - x/8 = 4x/8 - 2x/8 - x/8 = x/8 = 0.125 x
zu klein, also fliegt x/8 wieder raus
x/2 - x/4 - x/16 = 8x/18 - 4x/16 - x/16 = 3x/16 = 0.1875 x
zu klein, x/16 raus
x/2 - x/4 - x/32 = 16x/32 - 8x/32 - x/32 = 7x/32 = 0.21875 x
zu gross, x/32 bleibt drinnen
x/2 - x/4 - x/32 - x/64 = 32x/64 - 16x/64 - 2x/64 - x/64 =
0.203125 x
zu gross, x/64 bleibt drinnen
x/2 - x/4 - x/32 - x/64 - x/128 = ( 64 - 32 - 4 - 2 - 1 ) x/128 =
0.1953125 x
Was kleineres als x/128 gibts bei 8 Bit nicht mehr.
Also musst du jetzt entscheiden: lasse ich x/128 drinnen, dann
ist das Ergebnis 0.1953125x anstelle von 0.2x oder lasse ich
x/128 raus, dann ist das Ergebnis 0.203125x Welche Variante liegt
näher an den geforderten 0.2x
0.2 - 0.1953125 = 0.0046875
0.203125 - 0.2 = 0.003125
Die Variante ohne x/128 liegt also näher am Ergebnis und wird genommen
x/5 kann also angenähert werden durch
y = x/2 - x/4 - x/32 - x/64;
oder in Bitschiebeform
y = ( x >> 1 ) - ( x >> 2 ) - ( x >> 5 ) - ( x >> 6 );
besten Dank für die prompte Antwort. Also "systematisch" ausprobieren.
Hätte ja sein können das irgend ein Matheass da mal ne Formel
hergeleitet hat.
Schönens Wochenende noch...
Gast wrote:
> Der Zeitwurm wird ganz woanders stecken. Eine Int-Division dürfte unter> 10µs liegen. Selber 'herumzuschifften' ist m. E. voll daneben.
Komisch nur, dass die Leute, die Erfahrung mit dem AVR haben das anders
sehen.
Hannes Jaeger wrote:
> Gast wrote:>> Der Zeitwurm wird ganz woanders stecken. Eine Int-Division dürfte unter>> 10µs liegen. Selber 'herumzuschifften' ist m. E. voll daneben.>> Komisch nur, dass die Leute, die Erfahrung mit dem AVR haben das anders> sehen.
Würde ich so nicht sagen.
Eine allgemeine 16 Bit Division sind (unoptimiert)
16 mal schieben (16 Bit)
maximal 16 Subtraktionen (16 Bit)
16 Vergleiche (16 Bit)
16 Dekrements
16 Sprünge
Dazu noch etwas push/pop um Reister zu sichern.
Das darf bei 20Mhz keine 2ms dauern. 2ms wären bei dieser
Taktfrequenz ~40000 Instruktionen!
Gast wrote:
> Der Zeitwurm wird ganz woanders stecken. Eine Int-Division dürfte unter> 10µs liegen. Selber 'herumzuschifften' ist m. E. voll daneben.
Das beste, was Atmel selbst dazu zustande brachte, dauert bei 20MHz
immer noch 17,3µs und reecht viel Code, oder 24,3µs und wenig Code.
Andreas Kaiser wrote:
> Das beste, was Atmel selbst dazu zustande brachte, dauert bei 20MHz> immer noch 17,3µs und reecht viel Code, oder 24,3µs und wenig Code.
(Streiten wir doch nicht um ein paar µs)
Schon. Da sind wir aber immer noch weit weg von 2ms
Für mich bleibt immer noch die Frage: Wo kommen die 2ms her?
Es gibt libraries, die alle operationen in eine minimale menge an
instruktionen aufgeteilt, und kompensieren das mit push/pop und viel
herumspringen. zB die ShiftRight16 muss es in der library nur einmal
geben, wird mit den 16 bit aufm Stack angesprungen, pop-shift-push-ret,
absolut graesslich.
Die minimale Menge an shift-sub fuer eine division mit einer konstanten
ist ein einfacher algorithmus. Eine kleine Uebung fuer vor dem
Fruehstueck.
Aus ASM-Sicht fällt mir bei Division durch Konstante (also wenn der
Divisor zur Entwurfszeit bekannt ist) immer Multiplikation mit dem
Kehrwert ein.
Der Kehrwert von 3 ist 1/3. Da der AVR (wia alle anderen MCs auch) in
Bytes arbeitet, erweitere ich den Wert, um auf 256 (oder notfalls 65536)
zu kommen, dann kann ich die Division durch Byteshifting realisieren.
Durch 3 entspricht 1/3 bzw. 85/256 (1 / 3 * 256).
Ich multipliziere also mit 85 und werfe das untere Byte weg.
...
tt wrote:
> gibts denn auch eine Regel wie man die Teiler bestimmt oder muss man> ausprobieren?> Also woher weiss ich welche ich brauche und welche nicht?>> bei /3 so: /2 /8 /32 /128
Im Prinzip ganz einfach: du musst den Faktor durch eine Binärzahl
ausdrücken. Beispiel: 1/5=0.2 mit maximal 7 Verschiebungen:
0.2 * x = x * 2^7 * 0.2 / 2^7
= x * 25.6 / 2^7
~= x * 0b11010 / 2^7
= x * (2^4 + 2^3 + 2^1) / 2^7
= x * (2^-3 + 2^-4 + 2^-6)
= (x >> 3) + (x >> 4) + (x >> 6) ~= x*0.2031
Hallo!
Bitte vergisst mein Posting wieder!! Habe einen riesigen Bock
geschossen. Die Laufzeiten habe ich mit einem Timer gemessen und dabei
den Timer-Tick mit dem Overflow verwechselt (ich rechnete mit 819us
statt 3,2us). Asche auf mein Haupt!!
Gruss
Th
Andreas Schwarz wrote:
> = x * 25.6 / 2^7> ~= x * 0b11010 / 2^7
Platsch (Geräusch wenn die flache Hand an der Stirn aufklatscht)
Du glaubst gar nicht, wie lange ich an diesem Schritt getüftelt
habe ohne weiterzukommen.
Manchmal hat man aber auch ein Brett vorm Kopf.
Nimmt man Deine vormals errechnete Zeit mit 2,5ms als Basis und
korrigiert Deine Berechnungen um 3.2/819, so ergibt sich eine Dauer von
ca. 9,8µs. Vielen Dank :-)
Oder, wenn man die benötigten fünf Befehle von Karl Heinz zu Grunde legt
und jedem zwei Takte für die Ausführung zugesteht, so kommt man auf 160
Takte; gut, nehmen wir 200 Takte. Bei 20MHz wären das auch 10µs.
Wie man sieht, gibt es keinen Grund für eigene Schiebereien.
Gast wrote:
> Selber 'herumzuschifften' ist m. E. voll daneben.
Nicht unbedingt.
Wenn ich eine 32/8 Bit Division brauche, ist die in C geschrieben
schneller als die Bibliothek für 32/32 Bit.
Z.B. um aus 32 Bit Sekunden die Uhrzeit und Datum zu berechnen.
Peter
>Z.B. um aus 32 Bit Sekunden die Uhrzeit und Datum zu berechnen.
Na ja, für diese Umrechnung reicht doch eine Sekunde Rechenzeit :-)
Zudem packt der Linker zumeist die 32/32 Routinen zum Code dazu, wenn
irgendwo soclh eine Berechnung angefordert wird, sodaß zusätzliche
Routinen nur wertvolle Bits im Programmspeicher brauchen.
Wer ist denn hier immer so geizig mit Bits und Bytes?
Gast wrote:
> Wer ist denn hier immer so geizig mit Bits und Bytes?
Ja, der ATtiny2313 hats leider nicht so dicke mit Flash und die
DS1994-Uhr braucht nirgends sonst 32-Bit Operationen.
Die Codeersparnis wiegt daher mehr, als die Zeitersparnis.
Peter
Ja, ja, Du drehst Dir die Dinge immer so, daß sie DIR in den Kram
passen.
Schreibt jemand ein Programm, was äußerst geschickt mit wenig Code
auskommt, dann argumentierst Du, daß Du einen Mega128 noch nie
vollbekommen hast.
Man muß die Ausnahme nur zur Regel machen, um dann als Retter in den
Olymp einzuziehen :-)
>Ich habe hier einen Mega644 mit 20MHz und WinAVR-20080512.
Nur zur Erinnerung.
Gast wrote:
>>Ich habe hier einen Mega644 mit 20MHz und WinAVR-20080512.> Nur zur Erinnerung.
Ich habe aber geschrieben:
>>z.B. ...
Es bezog sich also definitiv nicht auf den Threaderöffner.
Es sollte nur klarstellen, daß Deine generelle Aussage falsch ist.
Das ist das schöne am Programmieren, daß man seine Phantasie spielen
lassen kann (und sollte).
Es gibt nichts, was generell immer richtig oder immer falsch ist (außer
"vielleicht" Delays in Interrupts).
Peter
Gast wrote:
> Schreibt jemand ein Programm, was äußerst geschickt mit wenig Code> auskommt, dann argumentierst Du, daß Du einen Mega128 noch nie> vollbekommen hast.
Da verlassen mich leider meine grauen Zellen.
Ich kann mich nicht erinnern, daß ich jemals an effizientem Code
gemeckert hätte.
Im Gegenteil, ich erfreue mich an effizientem Code.
Und wer nen Mega128 (ich nicht) benutzt, braucht in der Regel nicht auf
Effizienz zu achten.
Aber oftmals ist ein kürzerer Code auch schneller und dann kann es sich
auch auf nem Mega128 Boliden lohnen.
Peter
Etwas spät zwar, aber trotzdem noch zwei Anmerkungen zur
Implementierung von Divisionen durch Konstanten mittels
Schiebeoperationen:
1. Genauigkeit
Ausdrücke wie (x>>1)-(x>>3)-(x>>5)-(x>>7) werden vom GCC zwar ganz gut
optimiert (x wird nicht 1+3+5+7=16mal, sondern nur 8mal geshiftet),
jedoch läßt die Genauigkeit zu wünschen übrig.
Die Überlegung von Karl Heinz vom 7.6.08 um 00:13 geht davon aus, dass
der obige Ausdruck gleich dem ganzzahligen Anteil von x*43/128 ist.
Das stimmt aber nicht ganz: Bei x*43/128 werden die Nachkommastellen
des Ergebnisses einmal, nämlich ganz am Schluss, abgeschnitten. Der
durch das Abschneiden entstehende Fehler liegt im Intervall (-1,0].
Bei x/2-x/8-x/32-x/128 werden die Nachkommastellen bei jeder der
Einzeldivisionen abgschnitten. Der Fehler liegt damit in (-1,+3), kann
also deutlich größer werden.
Damit verbunden ist eine weitere Unschönheit, mämlich die
Nichtmonotonie des Ergebnisses. So ist bspw. ist für x=31 das Ergebnis
12, für x=32 aber nur 11.
Genauer wird das Ergebnis, wenn man den Ausdruck durch fortgesetztes
Ausklammern von Zweierpotenzen umformt:
Der Fehler liegt jetzt in (-1,+1/2). Die obere Grenze von +1/2 rührt
von der Subtraktion in dem Ausdruck her, die den zuvor gemachten
Fehler negiert.
Gewinnt man den Näherungsausdruck, wie von Andreas Schwarz
beschrieben, über die Binärdarstellung des Kehrwerts des Divisors,
enthält der enstehende Ausdruck nur Additionen, aber keine
Subtraktionen:
