mikrocontroller.net

Forum: Compiler & IDEs Division mit WinAVR sehr langsam?


Autor: Thomas Kusch (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Thomas Kusch wrote:

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

Seit wann?
Weiß Atmel davon?

Autor: Thomas Kusch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hai!

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

Danke:)

Gruss
Th

Autor: Axel Preuss (funkydunky)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: crazy horse (Gast)
Datum:

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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: tt (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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  ??????

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

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

Regel kenn ich keine.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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 );

Autor: tt (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: Gast (Gast)
Datum:

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

Autor: Hannes Jaeger (pnuebergang)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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!

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: 3357 (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Hannes Lux (hannes)
Datum:

Bewertung
0 lesenswert
nicht 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.

...

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Thomas Kusch (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: yalu (Gast)
Datum:

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

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.