Forum: Compiler & IDEs Division mit WinAVR sehr langsam?


von Thomas Kusch (Gast)


Lesenswert?

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.

von Karl H. (kbuchegg)


Lesenswert?

Thomas Kusch wrote:

> Das hat mich sehr gewundert, denn der Atmel hat doch einen
> Hardware-Divider.

Seit wann?
Weiß Atmel davon?

von Thomas Kusch (Gast)


Lesenswert?

Hai!

Uhm.... stimmt.. der hat ja keinen!! DOH

Danke:)

Gruss
Th

von Axel P. (funkydunky)


Lesenswert?

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?

von crazy horse (Gast)


Lesenswert?

ist wohl eher ein Compilerproblem...
Ich komme auf 66/56µs (signed/unsigned)

von Karl H. (kbuchegg)


Lesenswert?

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.

von tt (Gast)


Lesenswert?

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  ??????

von Karl H. (kbuchegg)


Lesenswert?

tt wrote:
> gibts denn auch eine Regel wie man die Teiler bestimmt oder muss man
> ausprobieren?

Regel kenn ich keine.

von Karl H. (kbuchegg)


Lesenswert?

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 );

von tt (Gast)


Lesenswert?

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...

von Gast (Gast)


Lesenswert?

Der Zeitwurm wird ganz woanders stecken. Eine Int-Division dürfte unter 
10µs liegen. Selber 'herumzuschifften' ist m. E. voll daneben.

von Hannes J. (Firma: _⌨_) (pnuebergang)


Lesenswert?

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.

von Karl H. (kbuchegg)


Lesenswert?

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!

von Andreas K. (a-k)


Lesenswert?

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.

von Karl H. (kbuchegg)


Lesenswert?

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?

von 3357 (Gast)


Lesenswert?

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.

von Hannes L. (hannes)


Lesenswert?

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.

...

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

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

von Thomas Kusch (Gast)


Lesenswert?

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

von Karl H. (kbuchegg)


Lesenswert?

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.

von Gast (Gast)


Lesenswert?

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.

von Peter D. (peda)


Lesenswert?

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

von Gast (Gast)


Lesenswert?

>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?

von Peter D. (peda)


Lesenswert?

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

von Gast (Gast)


Lesenswert?

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.

von Peter D. (peda)


Lesenswert?

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

von Peter D. (peda)


Lesenswert?

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

von yalu (Gast)


Lesenswert?

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:
1
  (x<<1)-(x<<3)-(x<<5)-(x<<7) = x/2-x/8-x/32-x/128 =
2
  = (x-(x+(x+x/4)/4)/4)/2 = x-(x+(x+(x>>2)>>2)>>2)>>1

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:
1
  x/3 ~ x*0,0101011b = x/4+x/16+x/64+x/128 =
2
  = (((x/2+x)/4+x)/4+x)/4 = (((x>>1)+x>>2)+x>>2)+x>>2

Der Fehler durch das Abschneiden der Nachkommastellen liegt nun in
(-1,0), und das Ergebnis ist nun genau der ganzzahlige Anteil von
x*43/128 ~ x*0,3359.

Die folgende Tabelle zeigt die Ergebnisse im Vergleich. Dabei ist

  A = (x>>1)-(x>>3)-(x>>5)-(x>>7)  und
  B = (((x>>1)+x>>2)+x>>2)+x>>2 = x*43/128

Die Ergebnisse, die sich von x/3 unterscheiden, sind fett gedruckt.

   x   x/3   A    B        x   x/3   A    B        x    x/3   A    B
+----+----+----+----+   +----+----+----+----+   +-----+----+----+----+
|  0 |  0 |  0 |  0 |   | 50 | 16 | 18 | 16 |   | 100 | 33 | 35 | 33 |
|  1 |  0 |  0 |  0 |   | 51 | 17 | 18 | 17 |   | 101 | 33 | 35 | 33 |
|  2 |  0 |  1 |  0 |   | 52 | 17 | 19 | 17 |   | 102 | 34 | 36 | 34 |
|  3 |  1 |  1 |  1 |   | 53 | 17 | 19 | 17 |   | 103 | 34 | 36 | 34 |
|  4 |  1 |  2 |  1 |   | 54 | 18 | 20 | 18 |   | 104 | 34 | 36 | 34 |
|  5 |  1 |  2 |  1 |   | 55 | 18 | 20 | 18 |   | 105 | 35 | 36 | 35 |
|  6 |  2 |  3 |  2 |   | 56 | 18 | 20 | 18 |   | 106 | 35 | 37 | 35 |
|  7 |  2 |  3 |  2 |   | 57 | 19 | 20 | 19 |   | 107 | 35 | 37 | 35 |
|  8 |  2 |  3 |  2 |   | 58 | 19 | 21 | 19 |   | 108 | 36 | 38 | 36 |
|  9 |  3 |  3 |  3 |   | 59 | 19 | 21 | 19 |   | 109 | 36 | 38 | 36 |
| 10 |  3 |  4 |  3 |   | 60 | 20 | 22 | 20 |   | 110 | 36 | 39 | 36 |
| 11 |  3 |  4 |  3 |   | 61 | 20 | 22 | 20 |   | 111 | 37 | 39 | 37 |
| 12 |  4 |  5 |  4 |   | 62 | 20 | 23 | 20 |   | 112 | 37 | 39 | 37 |
| 13 |  4 |  5 |  4 |   | 63 | 21 | 23 | 21 |   | 113 | 37 | 39 | 37 |
| 14 |  4 |  6 |  4 |   | 64 | 21 | 22 | 21 |   | 114 | 38 | 40 | 38 |
| 15 |  5 |  6 |  5 |   | 65 | 21 | 22 | 21 |   | 115 | 38 | 40 | 38 |
| 16 |  5 |  6 |  5 |   | 66 | 22 | 23 | 22 |   | 116 | 38 | 41 | 38 |
| 17 |  5 |  6 |  5 |   | 67 | 22 | 23 | 22 |   | 117 | 39 | 41 | 39 |
| 18 |  6 |  7 |  6 |   | 68 | 22 | 24 | 22 |   | 118 | 39 | 42 | 39 |
| 19 |  6 |  7 |  6 |   | 69 | 23 | 24 | 23 |   | 119 | 39 | 42 | 39 |
| 20 |  6 |  8 |  6 |   | 70 | 23 | 25 | 23 |   | 120 | 40 | 42 | 40 |
| 21 |  7 |  8 |  7 |   | 71 | 23 | 25 | 23 |   | 121 | 40 | 42 | 40 |
| 22 |  7 |  9 |  7 |   | 72 | 24 | 25 | 24 |   | 122 | 40 | 43 | 40 |
| 23 |  7 |  9 |  7 |   | 73 | 24 | 25 | 24 |   | 123 | 41 | 43 | 41 |
| 24 |  8 |  9 |  8 |   | 74 | 24 | 26 | 24 |   | 124 | 41 | 44 | 41 |
| 25 |  8 |  9 |  8 |   | 75 | 25 | 26 | 25 |   | 125 | 41 | 44 | 41 |
| 26 |  8 | 10 |  8 |   | 76 | 25 | 27 | 25 |   | 126 | 42 | 45 | 42 |
| 27 |  9 | 10 |  9 |   | 77 | 25 | 27 | 25 |   | 127 | 42 | 45 | 42 |
| 28 |  9 | 11 |  9 |   | 78 | 26 | 28 | 26 |   | 128 | 42 | 43 | 43 |
| 29 |  9 | 11 |  9 |   | 79 | 26 | 28 | 26 |   | 129 | 43 | 43 | 43 |
| 30 | 10 | 12 | 10 |   | 80 | 26 | 28 | 26 |   | 130 | 43 | 44 | 43 |
| 31 | 10 | 12 | 10 |   | 81 | 27 | 28 | 27 |   | 131 | 43 | 44 | 44 |
| 32 | 10 | 11 | 10 |   | 82 | 27 | 29 | 27 |   | 132 | 44 | 45 | 44 |
| 33 | 11 | 11 | 11 |   | 83 | 27 | 29 | 27 |   | 133 | 44 | 45 | 44 |
| 34 | 11 | 12 | 11 |   | 84 | 28 | 30 | 28 |   | 134 | 44 | 46 | 45 |
| 35 | 11 | 12 | 11 |   | 85 | 28 | 30 | 28 |   | 135 | 45 | 46 | 45 |
| 36 | 12 | 13 | 12 |   | 86 | 28 | 31 | 28 |   | 136 | 45 | 46 | 45 |
| 37 | 12 | 13 | 12 |   | 87 | 29 | 31 | 29 |   | 137 | 45 | 46 | 46 |
| 38 | 12 | 14 | 12 |   | 88 | 29 | 31 | 29 |   | 138 | 46 | 47 | 46 |
| 39 | 13 | 14 | 13 |   | 89 | 29 | 31 | 29 |   | 139 | 46 | 47 | 46 |
| 40 | 13 | 14 | 13 |   | 90 | 30 | 32 | 30 |   | 140 | 46 | 48 | 47 |
| 41 | 13 | 14 | 13 |   | 91 | 30 | 32 | 30 |   | 141 | 47 | 48 | 47 |
| 42 | 14 | 15 | 14 |   | 92 | 30 | 33 | 30 |   | 142 | 47 | 49 | 47 |
| 43 | 14 | 15 | 14 |   | 93 | 31 | 33 | 31 |   | 143 | 47 | 49 | 48 |
| 44 | 14 | 16 | 14 |   | 94 | 31 | 34 | 31 |   | 144 | 48 | 49 | 48 |
| 45 | 15 | 16 | 15 |   | 95 | 31 | 34 | 31 |   | 145 | 48 | 49 | 48 |
| 46 | 15 | 17 | 15 |   | 96 | 32 | 33 | 32 |   | 146 | 48 | 50 | 49 |
| 47 | 15 | 17 | 15 |   | 97 | 32 | 33 | 32 |   | 147 | 49 | 50 | 49 |
| 48 | 16 | 17 | 16 |   | 98 | 32 | 34 | 32 |   | 148 | 49 | 51 | 49 |
| 49 | 16 | 17 | 16 |   | 99 | 33 | 34 | 33 |   | 149 | 49 | 51 | 50 |
+----+----+----+----+   +----+----+----+----+   +-----+----+----+----+

Man erkennt, dass B bis 0<=x<=127 genaue Ergebnisse liefert, während
die Ergebnis von A in diesem Bereich um bis zu 3 vom gewünschten Wert
abweichen.

Ein willkommener Nebeneffekt von Ausdruck B ist, dass er von AVR-GCC
mit zwei Befehlen weniger kompiliert wird als A, was auch zwei
Prozessorzyklen spart (21 statt 23 Zyklen).


2. Implementierung mit Multiplikation

Soll das Ganze auf einem ATmega laufen (wie beim Threadstarter der
Fall), erscheint die Nutzung des Hardwaremultiplizierers angebracht.
Man kann bspw. einfach, wie von Hannes Lux vorgeschlagen, x*85/256
berechnen. Allerdings sind dabei verschiedene Dinge zu beachten:

Der Ausdruck x*85/256 benötigt 15 Zyklen, der äquivalente Ausdruck
(((x>>2)+x>>2)+x>>2)+x>>2 dagegen 23. Während letzterer aber den
vollen Wertebereich für x von 0 bis 65535 abdeckt, darf x bei
Verwendung der Multiplikation maximal 771 sein, um einen Überlauf zu
vermeiden. Kann x größer werden, muss die Multiplikation 32 Bit breit
durchgeführt werden. Das dauert in C aber schon 61 Zyklen, da beide
Operanden der Multiplikation erweitert werden und eine echte
32*32-Bit-Multiplikation als Bibliotheksfunktion aufgerufen wird. Wenn
man schon so viele Zyklen opfert, kann man natürlich gleichzeitig die
Genauigkeit erhöhen und in derselben Zeit x*21845/65536 ~ x*0,333328
berechnen, was selbst für große x noch eine sehr gute Näherung für x/3
darstellt. Das gleiche Ergebnis erhält man aber auch durch den
Ausdruck

  (((((((x>>2)+x>>2)+x>>2)+x>>2)+x>>2)+x>>2)+x>>2)+x>>2

der nur 47 statt 61 Zyklen benötigt.

Man sieht: Die aus Schiebeoperationen zusammengesetzten
Näherungsausdrücke für Divisionen haben in vielen Anwendungsfällen
auch auf einem ATmega mit Hardwaremultiplizierer ihre
Daseinsberechtigung. Und schneller als eine Softwaredivision sind sie
allemal.

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
Noch kein Account? Hier anmelden.