mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Division von unsigned char


Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

kann mit jemand einen schnellen Algorithmus für eine Division zweier 
unsigned char Variablen nennen? Als Controller habe ich den ATMEGA8. Es 
stehen nur 16 Takte zur Verfügung.

Geht das überhaupt? Meine erste Idee war eine Tabelle zu verwenden. 
Diese wird aber viel zu groß.

Martin

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Es stehen nur 16 Takte zur Verfügung.

Das wären 2 Takte pro Dividendenbit. Damit geht es mit der klassischen
(tabellenlosen) Methode nicht, selbst wenn man die Schleife abwickeln
würde, um einen Sprungbefehl pro Iterationsschritt einzusparen.

Eine zweidimensionale Tabelle mit allen Kombinationen aus Dividend und
Divisor benötigt fast 64KiB und ist ganz klar zu groß.

Wenn das Ergebnis etwas ungenauer sein darf, kannst aber eine Tabelle
mit den Kehrwerten aller Zahlen von 2 bis 255 benutzen, die braucht
nur 254 Bytes. In C würde die Funktion so aussehen:
uint8_t rec[254] = {
  128,  86,  64,  52,  43,  37,  32,  29,  26,  24,
   22,  20,  19,  18,  16,  16,  15,  14,  13,  13,
   12,  12,  11,  11,  10,  10,  10,   9,   9,   9,
    9,   8,   8,   8,   8,   8,   7,   7,   7,   7,
    7,   7,   6,   6,   6,   6,   6,   6,   6,   6,
    6,   6,   5,   5,   5,   5,   5,   5,   5,   5,
    5,   5,   5,   5,   5,   5,   4,   4,   4,   4,
    4,   4,   4,   4,   4,   4,   4,   4,   4,   4,
    4,   4,   4,   4,   4,   4,   4,   4,   4,   4,
    4,   3,   3,   3,   3,   3,   3,   3,   3,   3,
    3,   3,   3,   3,   3,   3,   3,   3,   3,   3,
    3,   3,   3,   3,   3,   3,   3,   3,   3,   3,
    3,   3,   3,   3,   3,   3,   3,   3,   3,   3,
    3,   3,   3,   3,   3,   3,   3,   3,   3,   3,
    3,   3,   3,   3,   3,   3,   3,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2,   2,   2,   2,   2,   2,   2,
    2,   2,   2,   2
};

uint8_t div(uint8_t a, uint8_t b) {
  if(--b)
    return a*rec[b-1]/256U;
  else 
    return a;
}

Das Programm berechnet a*(256/b)/256, wobei 256/b der Tabelle
entnommen wird. Da die Tabelleneinträge rundungsfehlerbehaftet sind,
weichen die Ergebnisse des Ausdrucks teilweise vom ganzzahligen Anzeil
von a/b ab. Damit der Fehler nicht zu groß wird, wurden die
Tabellenwerte so auf- oder abgerundet, dass der Ergebnisfehler
betragsmäßig möglichst klein wird. Er liegt im Bereich -0,966..+0,962,
während er für a/b im Bereich 0..1 liegt.

Die Sonderbehandlung von b=1 ist erforderlich, weil 256/1=256 zu groß
ist, um in die Tabelle eingetragen zu werden.

In (nachoptimiertem) Assembler sieht das dann so aus:
  subi r30,1
  breq div_end
  clr  r31
  subi r30,lo8(-(rec-1))
  sbci r31,hi8(-(rec-1))
  lpm  r0,Z
  mul  r0,r29
  mov  r29,r0
div_end:
  ...

rec:
  .byte  128
  .byte  86
  .byte  64
  .byte  52
   ... (bitte Zahlenwerte dem obigen C-Programm entnehmen)
  .byte  2
  .byte  2

Der Divisor (b) steht anfangs in r30, der Dividend (a) in einem
beliebigen Register im Bereich r1..r29 (im Beispiel in r29). Das
Ergebnis steht anschließend ebenfalls im Dividendenregister (r29). Die
Codesequenz benötigt 11 Zyklen. Für einen CALL/RET (8 Zyklen) reicht
es leider nicht mehr, deswegen muss die Sequenz direkt dorthin
geschrieben werden, wo sie benötigt wird, bspw. mit einem Makro. Die
noch zur Verfügung stehenden 5 Zyklen können bei Bedarf zum Umkopieren
der Ein-/Ausgaberegister genutzt werden.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Alternativ könnte man in den 5 Zyklen eine weitere Abfrage
unterbringen, und damit die vielen 2en in der Tabelle einsparen.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo yalu,

vielen Dank für Deine ausführliche Antwort.

Bin angenehm überrascht über die von Dir vorgestellte Lösung. Hätte 
nicht gedacht, dass es einen gangbaren Weg gibt.

Mit Grüßen für ein sonniges Wochenende

Martin

Autor: eProfi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Werden bei beiden Operatoren der gesamte Wertebereich ausgeschöpft?

Wenn nein, könnte man diese (zugegeben geniale) Methode dahingehend 
optimieren.

Autor: eProfi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
noch was:
"Die Sonderbehandlung von b=1 ist erforderlich, weil 256/1=256 zu groß
ist, um in die Tabelle eingetragen zu werden."

hmmm? wie soll denn (uint8) a = 256 werden?

Vielmehr müsste man eine Sonderbehandlung für b = 0 machen, denn das ist 
nicht definiert.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> hmmm? wie soll denn (uint8) a = 256 werden?

Nicht a wird 256, sondern 256/b, also der Wert, der in die Tabelle
eingetragen werden müsste.

> Vielmehr müsste man eine Sonderbehandlung für b = 0 machen, denn das
> ist nicht definiert.

Diesen Fall habe ich einfach unter den Tisch fallen lassen, da es
ohnehin keine für alle Anwendungsfälle sinnvolle Behandlung dafür
gibt. Normalerweise ist es aber kein Problem, den Rest des Programms
so zu schreiben, dass dieser Fall gar nicht erst eintritt.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man könnte 4 Divisionen a 4 Bit über Tabellen abwickeln. Wird aber auch 
eng.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@I_ H. (i_h)

Kannst Du Deine Idee etwas näher erläutern?

Autor: Bernd (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@I_ H.

Interessiert mich auch!

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man kann zwar zur Vereinfachung von  Multiplikationen beide Operanden
in kleinere Einheiten splitten, bei Divisionen geht das aber nur mit
dem Dividenden. Beim Divisor muss mit den vollen 8 Bit gerechnet
werden, so dass man eine 8/8-Division höchstens in zwei 4/8-Division
zerlegen kann. Damit lässt sich die Tabelle von 256*256=64K auf
16*256=4K Werte reduzieren, was immer noch ziemlich groß ist.

Falls es dennoch einen Trick gibt, eine 8/8-Division in vier
4/4-Divisionen zu unterteilen, wäre ich ebenfalls sehr daran
interessiert.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Man kann zwar zur Vereinfachung von  Multiplikationen beide Operanden
>in kleinere Einheiten splitten, bei Divisionen geht das aber nur mit
>dem Dividenden.

Man kann dieses Splitting, eg. Karatsuba/Toom-Cook Trick bei 
Multipikationen und auch Divisionen anwenden. Also auch bei der Division 
kann man nach dem "Teile&Herrsche" Prinzip (Divide&Conquer) arbeiten. 
Siehe:

File: TechRep.ps,
"Fast Recursive Division"
Christoph Burnikel & Joachim Ziegler
MPI-I-98-1-022     October 1998
Forschungsbericht     Research Report
Max Planck Institut für Informatik

Allerdings macht dies auf einem AVR keinen Sinn. Selbst Karatsuba für 
Multiplikationen macht auf dem AVR wenig Sinn da die Zahlenbereiche zu 
klein sind und das Taktverhältnis von 1:2 -> ADD:MUL zu gering ist. Hat 
man also eine schnelle HW-MUL dann bestimmt das Verhältnis an Takten die 
man für Additionen/Subtraktionen/Shifts im Vergleich zur 
HW-Multiplikation benötigt über die Sinnhaftigkeit solcher Algortihmen. 
Sie substituieren immer eine math. Operation durch andere meistens 
schnellere Oparationen. Karatsuba spart durch Divide&Conquer Techniken 
eine bestimmte Anzahl an Multiplikationen ein und ersetzt diese durch 
einen erhöhten Aufwand an Additionen/Subtrationen/Shifts und 
Speicherkopierungen. Wenn die Multiplikation aber sehr effizient ist 
dann machen solche Algos. keinen Sinn mehr.

Gruß Hagen

PS: http://cr.yp.to/bib/1998/burnikel.ps

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich werd mir nachher nochmal 'n Kopf drüber machen, aber im Grunde 
sollte es wie schriftliche Division funktionieren, nur dass jede Ziffer 
einem Nibble entspricht. Man bräuchte dann 2 Tabellen a 256 Einträge.

Aber wie schon oben gesagt, es wird auch damit eng.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
512 Bytes Flashspeicheropfer für einen merklichen Zeitgewinn wären bei
mir in vielen Fällen akzeptabel, da ich die größeren AVRs mit >=32k
sowieso selten voll bekomme ;-)

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich reiße mal kurz an, wie ich mir das gedacht hatte. Variablen stehen 
für Ziffern.

Für eine Division AB/CD berechnet man erstmal AB/C0. Der Quotient 
entspricht dem von A0/C0=:Q, der Rest ergibt sich über den Rest von 
A0/C0 + B=:R.

Das Ergebnis hat jetzt erstmal wenig mit AB/CD zu tun. Die Differenz zum 
Quotienten und Rest von AB/CD müsste man aber über 2 LUTs abhängig von Q 
und D ermitteln können (eine für Quotienten, eine für Rest).

Ok, das wären dann 4 Tabellen, nicht 2. Ich bin mir auch noch nicht 
sicher ob das wirklich immer funktioniert, ein paar Testrechnungen haben 
jedenfalls geklappt.
Aber mein Gefühl sagt mir, dass das irgendwie mit einer LUT gehen muss. 
Bewiesen ist natürlich noch garnix.

Nach der Rechnung könnten auch negative Reste auftauchen, und Reste 
größer dem Quotienten. Das muss man dann noch umrechnen.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielleicht kann das ja mal jemand von euch nachprüfen. Beispielrechnung 
(dezimal):

56:12 = 4 Rest 8

56:10 = 5 Rest 6 (über 5:1, Rest+6)

Nun braucht man den LUT-Eintrag für Q=5, D=2.

Die LUT kann man füllen indem man einfache irgendeine Testrechnungen 
macht, die auf den Eintrag passt (natürlich 1mal am anfang und nicht 
während der Rechnung).
Im einfachsten Fall bleibt A "ähnlich", also zB. 58:12. 58:10 gibt 5 
Rest 8, passt also. 58:12 macht 4 Rest 10.
Für den LUT-Eintrag ergibt sich damit 0 für Q und -10 für R (R sollte 
immer negativ sein).

Wir waren bei 56:10 = 5 Rest 6. 5 bleibt 5, 6-10 macht -4.
Also ergibt sich für 56:12 = 5 Rest (6-10) = 5 Rest -4 = 4 Rest 8 - 
stimmt offensichtlich.


Komplizierteres Beispiel mit LUT-Eintrag Q=3, D=2:

30:12 = 2 Rest 6, 30:10=3 Rest 0.

LUT-Eintrag mal über was ganz anderes ermittelt: 60:22. Hat mit 60:20=3 
Rest 0 den selben Eintrag, 60:22 = 2 Rest 16. Ergibt sich 0 für Q und -6 
für R.

30:10=3 Rest 0 -> 30:12=3 Rest (0-6) = 3 Rest -6 = 2 Rest 6 - passt 
auch.


Ob man die LUT für Q wirklich braucht weis ich grad nicht, glaub eher 
nicht. Dann wären's noch 3 Tabellen, 2 für 4bit Div und Rest, und eine 
für die Verschiebung vom Rest. Dann sollten die Werte für die 
Restverschiebung auch positiv sein können.

Für Division durch einstellige Werte funktioniert der Algorithmus so 
nicht.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, ganz so einfach geht's doch nicht, bei großen D und kleinen C gibt's 
Probleme. Bei etwa der hälfte aller möglichen Divisionen sollte es 
funktionieren wie oben beschrieben... mal schauen ob mir noch was für 
die andere Hälfte einfällt.
Vielleicht funktioniert's wenn man Q rundet und bei zB. 50:19 nicht 
50:10 sondern 50:20 rechnet, und einen LUT-Eintrag Q=2, D=-1 nachschaut. 
Die Tabelle wird dadurch nicht größer, da D nach wie vor nur 10 Werte 
(in Dez.) annehmen kann. Die Restverschiebungen werden dadurch aber 
kleiner.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Martin wrote:
> Hallo,
>
> kann mit jemand einen schnellen Algorithmus für eine Division zweier
> unsigned char Variablen nennen? Als Controller habe ich den ATMEGA8. Es
> stehen nur 16 Takte zur Verfügung.
>
> Geht das überhaupt? Meine erste Idee war eine Tabelle zu verwenden.
> Diese wird aber viel zu groß.
>
> Martin

Die Sterne stehen schlecht...

Mit folgendem Verfahren (16-Bit Reziprok-Tabelle) braucht's trotz der 
Tabelle über 20 Ticks. Dafür stimmen die Ergebnisse exakt mit a/b 
überein (unsigned).
static unsigned short quo[256] =
{
    0, 0, 384, 22101, 320, 13363, 43818, 37668, 288, 29212,
    39449, 17943, 22037, 45587, 18962, 4625, 272, 4111, 14606, 31245,
    52492, 12556, 41739, 8715, 43786, 15882, 55561, 31753, 9481,
    54280, 35080, 17160, 264, 49671, 34823, 20743, 7431, 60422, 48390,
    37126, 26374, 16134, 6406, 62725, 53765, 45317, 37125, 29445,
    22021, 14853, 7941, 1541, 60676, 54532, 48644, 43012, 37636,
    32260, 27140, 22276, 17668, 13060, 8708, 4356, 260, 61699, 57603,
    54019, 50179, 46595, 43267, 39939, 36611, 33283, 30211, 27139,
    24323, 21507, 18691, 15875, 13315, 10755, 8195, 5635, 3331, 1027,
    64258, 61954, 59650, 57602, 55554, 53506, 51458, 49410, 47618,
    45570, 43778, 41986, 40194, 38402, 36866, 35074, 33538, 32002,
    30466, 28930, 27394, 25858, 24322, 23042, 21506, 20226, 18946,
    17410, 16130, 14850, 13570, 12546, 11266, 9986, 8962, 7682, 6658,
    5378, 4354, 3330, 2306, 1282, 258, 64769, 63745, 62721, 61697,
    60673, 59905, 58881, 57857, 57089, 56065, 55297, 54529, 53505,
    52737, 51969, 51201, 50177, 49409, 48641, 47873, 47105, 46337,
    45825, 45057, 44289, 43521, 42753, 42241, 41473, 40705, 40193,
    39425, 38913, 38145, 37633, 36865, 36353, 35585, 35073, 34561,
    33793, 33281, 32769, 32257, 31489, 30977, 30465, 29953, 29441,
    28929, 28417, 27905, 27393, 26881, 26369, 25857, 25345, 24833,
    24321, 23809, 23297, 22785, 22529, 22017, 21505, 20993, 20737,
    20225, 19713, 19201, 18945, 18433, 18177, 17665, 17153, 16897,
    16385, 16129, 15617, 15361, 14849, 14593, 14081, 13825, 13313,
    13057, 12545, 12289, 12033, 11521, 11265, 10753, 10497, 10241,
    9729, 9473, 9217, 8705, 8449, 8193, 7937, 7425, 7169, 6913, 6657,
    6401, 5889, 5633, 5377, 5121, 4865, 4609, 4097, 3841, 3585, 3329,
    3073, 2817, 2561, 2305, 2049, 1793, 1537, 1281, 1025, 769, 513
};

#define DIV8_TAB(__a,__b)                       \
({                                              \
    unsigned char __a2 = __a;                   \
    unsigned char __b2 = __b;                   \
    unsigned short * __p1b = & quo[__b2];       \
    unsigned char __ab;                         \
    asm ("lpm  r0, z+"             "\n\t"       \
         "mul  %[a], r0"           "\n\t"       \
         "mov  %[c], r1"           "\n\t"       \
         "mov  r18, r0"            "\n\t"       \
         "lpm  r0, z"              "\n\t"       \
         "mul  %[a], r0"           "\n\t"       \
         "add  r18, r1"            "\n\t"       \
         "clr  __zero_reg__"       "\n\t"       \
         "adc  %[c], __zero_reg__"              \
         : [c] "=&r" (__ab), "+z" (__p1b)       \
         : [a] "r"   (__a2)                     \
         : "18");                               \
    __ab;                                       \
})

unsigned char div8_tab (unsigned char a, unsigned char b)
{
    if (b != 1)
        a = DIV8_TAB (a,b);

    return a;
}

Getestet hab ich's aber nur für i386 in C und für AVR mit Brain 0.9b 
simuliert.

Der erzeugte Assembler sieht so aus:
.global  div8_tab
  .type  div8_tab, @function
div8_tab:
/* prologue: frame size=0 */
/* prologue end (size=0) */
  cpi r22,lo8(1)   ;  b,   ;  12  cmpqi/2  [length = 1]
  breq .L2   ; ,   ;  13  branch  [length = 1]
  mov r30,r22   ;  __p1b, b   ;  21  zero_extendqihi2/2  [length = 2]
  clr r31   ;  __p1b
  add r30,r30   ;  __p1b, __p1b   ;  23  *addhi3/1  [length = 2]
  adc r31,r31   ;  __p1b, __p1b
  subi r30,lo8(-(quo))   ;  __p1b,   ;  24  *addhi3/4  [length = 2]
  sbci r31,hi8(-(quo))   ;  __p1b,
/* #APP */
  lpm  r0, z+
  mul  r24, r0   ;  a
  mov  r25, r1   ; 
  mov  r18, 0
  lpm  r0, z
  mul  r24, r0   ;  a
  add  r18, r0
  clr  __zero_reg__
  adc  r25, __zero_reg__   ; 
/* #NOAPP */
  mov r24,r25   ;  a,   ;  52  *movqi/1  [length = 1]
.L2:
  clr r25   ;  <result>   ;  40  zero_extendqihi2/1  [length = 1]
/* epilogue: frame size=0 */
  ret

viel unnötig ist da nicht...

Vielleicht kannst Du die Echtzeit-Anforderung Deiner Anwendung 
entschärfen. Ausserdem steht bei Frequenzmessung im Zähler womöglich ne 
Konstante?

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hab meine Variante mal implementiert und alle möglichen 
uchar-divisionen durchgetestet. So wie's oben dasteht stimmen 58737 von 
65536 Rechnungen (div durch 0 als stimmt immer angenommen, div durch 
einstelliges immer als falsch (betrifft 2304 Rechnungen)), Quotient 
und Rest.

Schaut also schonmal ganz gut aus, das sind 89.6%. Irgendwie wird man 
den Rest auch noch an's Laufen bekommen.

Während der Rechnung lässt sich übrigens absehen, ob das Resultat gültig 
sein wird. Da könnte man abbrechen und eine normale Division 
durchführen. Bringt dann halt nur in 90% aller Fälle deutlich mehr 
Geschwindigkeit. Aber in 16 Takte wird es, wie gesagt, nicht passen.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die einstelligen Divisionen betreffen 3840, nicht 2304 Rechnungen.

Autor: Siegfried (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die 8051-Familie kennt den DIV AB Befehl. Wie ist die Division bei 
diesen Controllern gelöst? Ist es möglich die Vorgehensweise für einer 
AVR-Controller zu übernehmen?

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da ich kein AVR Assembler kann, hier mal der Code in x86 asm. Ihr könnt 
ja dann schauen ob das in 16 Takte passt:

Gerechnet wird ax/bx, edi zeigt auf 4bit div lut, esi auf 4bit mod lut 
(jeweils a/b -> index=a*16+b), und ebp auf die mit der Restverschiebung.
Auf'm AVR gehen einige der Operationen sicher mit weniger Befehlen als 
auf x86. Vielleicht ließen sich die Tabellen auch besser anordnen.
MOV  CL, AL    // AB/CD 
AND  CL, 0xF0

MOV  CH, BL
SHR  CH, 4
AND  CL, CH    // CL=AC

MOV  DL, [EDI+CL]  // div - &0xF0 is always 0
MOV  DH, [ESI+CL]  // mod
      // DL=A0/C0
      // DH=A0%C0=:Q1
AND  AL, 0xF    
ADD  DH, AL    // DH=AB%C0


MOV  CL, DL    // EBP tabelle umsortieren
SHL  CL, 4    // spart instruktionen
MOV  CH, BL
AND  CH, 0x0F
AND  CL, CH    // CL=Q1D

ADD  DH, [EBP+CL]  // restverschiebung

JNBZ  noadjust

DEC  DL

noadjust:

So in etwa müsste das aussehen, für die Korrektheit übernehm ich keine 
Garantie, hab das nicht ausprobiert (es wird nur der Quotient berechnet, 
damit der Rest stimmt müssen noch 1 oder 2 Anweisungen dazu). Das 
Displacement mit CL funktioniert glaub ich so nicht (hab auf x86 schon 
ewig nimmer mit 8 und 16bit Registern rumgemacht), ist aber egal, beim 
AVR hat man das Problem nicht.

Es sind genau 16 Befehle, es fehlt aber die Erkennung ob die Operation 
überhaupt möglich ist. Es gibt 2 Punkte wo's scheitern kann. Wenn 
BL&0xF0==0 (könnte man in der DIV oder MOD Tabelle mit einem extra Wert, 
zB. 255 markieren), und wenn die Restverschiebung zu groß ist (in der 
Restverschiebungstabelle markieren, zB. auch 255).

Vielleicht könnte man das auch zusammenfassen, indem man zB. in die DIV 
Tabelle einen Wert schreibt, der dann in der Restverschiebungstabelle 
einen ungültigen Wert gibt. Dann reicht eine Abfrage.

Wenn man den Rest mitberechnet kann man die Erfolgsquote mit einem 2. 
Adjust Durchlauf (wenn Rest <0 Rest+Divisor, Quotient--) auf etwa 95% 
steigern.

Autor: Siegfried (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ist doch ein Scherz - oder? Ein Algorithmus der eine Erfolgsquote 
von 95 % hat!

Autor: Ekschperde (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Das ist doch ein Scherz - oder? Ein Algorithmus der eine Erfolgsquote
> von 95 % hat!

Das scheint bei den Anhängern des AVR verbreitet zu sein.
Hab sowas schon mal im Board bei AVR-Freaks gesehen.
Da war die Ausbeute aber geringfügig besser.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man weiß in welchen Fällen der Algorithmus fehlschlägt, ist doch 
alles in Ordnung.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Simon K. wrote:
> Wenn man weiß in welchen Fällen der Algorithmus fehlschlägt, ist doch
> alles in Ordnung.

Eben, und dann kann man die langwierige Division durchführen. Wobei sich 
für einstellige Divisoren sicher auch schnellere Varianten finden 
lassen.

Wenn's um einen Algorithmus geht wo viele Divisionen mit 
gleichverteilten Parametern vorkommen, und der Algorithmus von oben 1/4 
der Zeit einer normalen Division braucht, reduziert sich die benötigte 
Zeit auf 30%.

Bei CPUs mit Divisionsbefehl dauert diese übrigens auch nicht immer 
gleich lang.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit einer zusätzlichen 256 Byte Tabelle müssten auch einstellige 
Divisionen funktionieren. So ungefähr, am Beispiel 51/4:

51/4 = 50/4+1/4

1/4 kann man über die vorhandene Tabelle berechnen, 0 Rest 1

50/4 geht so: Über die vorhandene Tabelle 5/4, 1 Rest 1. Der Rest 
braucht nie mehr als 4 Bit (bzw. eine Stelle Dez.), da Divisior immer 
einstellig.

Der Rest und der Quotient von 1/4 beschreiben nun die letzte Stelle vom 
Quotienten von 51/4, der Quotient aus 5/4 die erste Stelle.

Man müsste die letzte Stelle über eine Tabelle, die den Divisor und den 
Rest von 5/4 auf die letzte Stelle mappt, berechnen können - dazu dann 
noch der Quotient von 1/4.

In dem Fall hier wäre das dann Q=4, R=1 -> 2.

Andere Rechnung mit dem Wert: 59/4. 5/4 ist wieder 1R1, 9/4=2R1. 59/4 
ist dann also (1*10+2)+2=14 - stimmt. Der Rest stimmt nicht, um den zu 
berechnen bräuchte man noch eine Tabelle.


Auf die Weise stimmen schonmal 63453 von 65536 möglichen Rechnungen (mit 
2fachem Test statt 1fachem wie im Code oben), also 96.8%. Insg. braucht 
man dafür 1kB Tabellen.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man so ca. 4kB verheizt bekommt man übrigens noch schnellere 
Algorithmen. Damit könnte man dann vll sogar unter 16 Takte kommen. Aber 
4kB ist schon einiges.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>> Bei CPUs mit Divisionsbefehl dauert diese übrigens auch nicht immer
>>> gleich lang

Beim Standard 8051-Kern sind es immer 4 Zyklen!

Autor: Marcus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Müssen es denn wirklich 8bit durch 8bit sein?

Mit z.B. 7bit durch 5 bit wär es nur eine 4k Tabelle.

Autor: crazy horse (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich halte nix von solchen Ausquetschereien. Was bringt ein Algorithmus, 
der in 90% der Fälle die Arbeit in der geforderten Zeit erledig, in den 
restlichen 10% aber versagt? Was passiert, wenn die Ausnahmefälle 
gehäuft direkt hintereinander auftreten? Versagt dann das System? Oder 
kann man das tolerieren, ist also die Forderung 16 Takte gar nicht so 
ernst zu nehmen?
Anderer Prozessor ist die einfache Antwort. Also einer, der den 
Anforderungen gewachsen ist. Oder die Anforderungen herunterschrauben, 
alles andere ist doch Murks. Schlechte Vorplanung schützt nicht davor, 
alles noch mal umschmeissen zu müssen...

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich schrieb "nicht immer", nicht "stets". Auf den MIPS Kollegen dauert 
das zB. unterschiedlich lang. Aber ich nehm an du bist der Typ aus dem 
Fusionsthread - erledigt.


@crazy horse

Ist ja nicht ausgeschlossen, dass sich noch was schnelles findet. Wenn 
sich hier eine gute Lösung findet, kann man die ja auch in anderen 
Problemstellungen verwenden. Ich find das Thema ansich auch nicht 
uninteressant.

Man könnte es auch so probieren:

Herkömmlich wäre zB. so (a/b): b shift left bis oberes Bit gesetzt, 
Schiebeweite merken (=:l). Ergebnis e:=0.

b>=a? wenn ja: a-=b, e|=0x80
b>>=1;
b==0 -> springe zu ende

b>=a? wenn ja: a-=b, e|=0x40
b>>=1;
b==0 -> springe zu ende

usw, die Maske verschieb sich jeweils um 1 (man könnte auch immer das 
gleiche Bit in e setzen, und dann schieben - ist aber langsamer).

ende:

e>>=l;


Im dümmsten Fall braucht man 7 Schritte (a/1), im einfachsten Fall nur 
einen (b>=128) und man ist sehr schnell fertig.
Für a<16 braucht man 4..7 Schritte, die Divisionen durch einstellige 
Divisoren braucht also am längsten.

Man nimmt sich nun eine Tabelle her, die für alle 256 Divisoren die 
Schrittzahl enthält (256 Byte) - damit kann man auch auf l schließen und 
muss das nicht berechnen.

Bei <= 4 Schritten rechnet man wie oben durch und hat für nachgucken in 
der Tabelle, springen, und 4 Schritte 16 Takte. Könnte reichen, bleibt 
aber eng.

Bei > 4 Schritten benutzt man einen anderen Algorithmus. Man könnte eine 
fertige Tabelle für 8bit/4bit benutzen, die braucht 4kB. Damit sollte es 
für jede Rechnung in <=16 Takten gehen.


Wenn man's schafft die Werte einzuschränken ist allerdings wirklich sehr 
viel gewonnen. Je mehr man optimiert, desto weiter muss man sich von 
allgemeingültigen Algorithmen entfernen.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@I_ H. (i_h)

Der Unterschied zwischen Dir und mir ist einfach: Du arbeitest mit 
Meinungen, Vermutungen & Behauptungen. Ich fordere die Leute auf sich 
ein eigenes Urteil zu bilden, und biete ihnen nachprüfbare Fakten und 
Tatsachen.

Jeder kann den Thread durcharbeiten und Deine Beiträge mit denen von 
yalu und Johann vergleichen.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
crazy horse wrote:
> ich halte nix von solchen Ausquetschereien. Was bringt ein Algorithmus,
> der in 90% der Fälle die Arbeit in der geforderten Zeit erledig, in den
> restlichen 10% aber versagt?

Nein, das muss man völlig anders sehen. Möglicherweise lassen sich die 
Spezialfälle, in denen der Algorithmus nicht funktioniert ganz einfach 
per IF-Abfrage abfangen und sofort ein festes Ergebnis zurückgeben. Dann 
wäre die Laufzeit des Algorithmus unter Umständen sogar kürzer!

Außerdem kann man diesen "halb funktionierenden" Algorithmus ja auch 
einstellen, damit andere mit der Idee weiterarbeiten können und sich der 
Algorithmus mglw. noch verbessert.

Ich erinnere da nur an die Algorithmen, die es alle schon gab um 
Primzahlen hervorzusagen, welche allerdings nur bis zu einer bestimmten 
Zahl ging und ab da sehr häufig Fehler aufwiesen.

Autor: Siggi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Johann

Dein Algorithmus funktioniert nicht. 200 geteilt durch 7 ergibt 4!?

Getestet mit GCC und AVR-Studio 4.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Siggi wrote:
> @Johann
>
> Dein Algorithmus funktioniert nicht. 200 geteilt durch 7 ergibt 4!?
>
> Getestet mit GCC und AVR-Studio 4.


hmmm...

An Stelle 7 der Tabelle steht 37668, also LOW=36, HIGH=141.

Zunächst wird das LOW-Byte mit 200 multipliziert, gibt 200*36 = 28*256 + 
32.

Nach dem ersten MUL müsste R1=%[c] also 28=0x1c sein und R0=R18=32=0x20.

Dann wird gerechnet 200*141=110*256 + ...

110 + R18 gibt kein 8-Bit-Überlauf, daher bleibt das Ergebnis auf 28, 
dem korrekten Ergebnis.

Von den Werten her stimmt es, es müsste ein blöder Fehler im asm sein, 
den ich nicht sehe (hab leider keine Testplattform ausser Brain 1.0)

Im asm-Template fehlen ein paar Unterstriche, die lässt die 
Foren-Software gerne großzügig unter den Tisch fallen. Hast Du die 
nachgebessert? Ich weiß nicht, wie ich's hier hinschreiben soll, weil 
die Unterstriche ja flöten gehen... So wie ~~zero~reg~~ muss es heissen.

Hier ne bessere Version, die nicht explizit R18 belegt:

#define DIV8_TAB(__a,__b)                       \
({                                              \
    unsigned char __a2 = __a;                   \
    unsigned char __b2 = __b;                   \
    unsigned short * __p1b = & quo[__b2];       \
    unsigned char __ab;                         \
    unsigned char __d;                          \
    asm ("lpm  r0, z+"             "\n\t"       \
         "mul  %[a], r0"           "\n\t"       \
         "mov  %[c], r1"           "\n\t"       \
         "mov  %[d], r0"           "\n\t"       \
         "lpm  r0, z"              "\n\t"       \
         "mul  %[a], r0"           "\n\t"       \
         "add  %[d], r1"           "\n\t"       \
         "clr  __zero_reg__"       "\n\t"       \
         "adc  %[c], __zero_reg__"              \
         : [c] "=&r" (__ab), "+z" (__p1b), [d] "=&r" (__d) \
         : [a] "r"   (__a2));                   \
    __ab;                                       \
})

Autor: Siggi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Deinen Quelltext habe ich so übernommen. Er ließ sich ohne Probleme 
übersetzen. Am Montag werde ich Befehl für Befehl durchgehen.

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.