Pfad: Home => AVR-Überblick => Programmiertechniken => Teilen durch N    (This page in English: Flag EN) Logo

Programmiertechnik für Anfänger in AVR Assemblersprache

Dividieren durch Ganzzahlen in Assemblersprache: die Methode nach Schmidt

Das Teilen durch eine konstante Zahl kann man auch anders als durch Linksschieben und Abziehen: wie hier gezeigt, geht das auch anders: mit einer sukzessiven Näherung, mit Zweiteilen und abziehen.

Wie es funktioniert

Die Schmidt-Methode funktioniert folgendermaßen:
  1. Die Zahl wird mit 256 oder 65.536 malgenommen. Das geschieht beim Laden der Zahl, indem diese in die entsprechend höheren Bytes der 8-Bit- oder 16-Bit-Zahl gespeichert wird, die zusätzlichen unteren acht oder 16 Bits werden geleert.
  2. Diese zwei (8-Bit-Zahl) oder vier (16-Bit-Zahl) Bytes werden in zwei bzw. vier weitere Bytes kopiert.
  3. Nun wird die Kopie der Zahl fortgesetzt solange durch zwei geteilt, bis nichts mehr übrig bleibt. Nach dem Teilen wird die geteilte Zahl entweder von der Originalzahl subtrahiert oder auch nicht. Je nachdem ob und mit welchen der geteilten Zahlen das geschieht, bestimmt den Teilerwert.
  4. Wenn die kopierte Zahl leer ist, steht das Ergebnis im höheren Byte (bei 8-Bit-Zahlen) bzw. in den beiden höheren Bytes (bei 16-Bit-Zahlen).
  5. Ist das unterste Byte (bei einer 8-Bit-Zahl) bzw. das zweitunterste Byte (bei einer 16-Bit-Zahl) größer als oder gleich 0x80, dann wird das Ergebnis aufgerundet.
Ob eine durch zwei geteilte Zahl abgezogen wird oder nicht, ergibt sich aus einem Bitmuster. Das kriegt man folgendermaßen. Am Beispiel der Teilung durch 3 geht man mit einer Tabellenkalkulation, z. B. LibreOffice-Calc, so vor. Die Tabelle gibt es hier, das betreffende Tabellenblatt heißt "8-bit-reihe".

Berechnen der Reihe bei 8-Bit-Division Die Zahl, hier 255, wird durch den Teiler geteilt. Das ergibt den Sollwert des Ergebnisses.

Nun wird die Zahl in der zweiten Spalte "Abzug" 16 mal durch 2 geteilt, die linke Spalte zeigt den Divisor an. Ausgehend von der Originalzahl wird in der Spalte "Näherung" für jeden Abzug entschieden, ob die durch zwei geteilte Zahl abgezogen werden muss oder nicht. Das Ergebnis steht in der vierten Spalte: bei einer Eins wird abgezogen, bei einer Null nicht. Wie man sieht, nähert sich mit jedem Abziehen dem Endergebnis an (Spalte "Delta").

Ist das niedrige Byte des Ergebnisses größer oder gleich 0,5, muss das Ergebnis noch aufgerundet werden.

Die Reihe von Einsen und Nullen in der vierten Spalte bleibt dabei immer die gleiche, egal mit welcher Zahl man beginnt. Man darf nur nicht die Zahl zu klein wählen, sonst gehen die untersten Bits verloren. 128 ist ausreichend. Das Bitmuster (oben rechts in binär und hexadezimal) ist spezifisch für den Teiler. Wie man sieht, ist das Bitmuster im Falle von 3 sehr einfach und regelmäßig: beginnend vom Ende her immer 10. Das ist aber nicht immer der Fall, manche Teilermuster haben gar keine Regelmäßigkeit.

Das Bitmuster lässt sich nun sehr einfach in einen Assembler-Quellcode einbauen, der diese Teilung ausfüht. Der Quellcode kann hier bezogen werden. Er erwartet im Kopf nur die zu teilende Zahl als Konstante sowie das Bitmuster. Das kann aus dem LibreOffice Dokument per Kopie in die Zwischenablage und Einfügen in den Quellcode dorthin kopiert werden.

Teilen von 255 durch 3 im Simulator Simuliert man den Quellcode, z. B. mit avr_sim, kommt nach einigem Gezappel das Ergebnis in Register rRH heraus. Es sollte stimmen, und tut das auch. Man sieht an der Ausführungszeit von 165 Takten, dass das Teilen mit dieser Methode nicht so ganz üppig schnell ist. Aber wir sehen unten noch, dass es auch schneller geht.

8-Bit-Divisionsreihen Das hier sind ausgewählte Reihen zum Dividieren mit 8-Bit-Zahlen. Angegeben sind jeweils
  1. der Teiler,
  2. das Bitmuster des Teilers in binär und hexadezimal,
  3. die Anzahl Takte, die das Dividieren von 255 benötigt, sowie
  4. die Anzahl Takte, die man für das fortgesetzte Abziehen des Divisors brauchen würde.
Man erkennt, dass diese Software zum Dividieren zwischen 138 und 177 Takten braucht, je nachdem wieviele Einsen im Bitmuster sind und ob und wie oft der Divisor und das Endergebnis aufgerundet werden mussten.

Als Beispiel gibt es den Quellcode für das Teilen durch 1,1, was mit fortgesetztem Subtrahieren ohne größere Verrenkungen gar nicht geht. Der Quellcode dafür ist hier. Das Programm umfasst 20 Worte Code und braucht für das Teilen von 255 durch 1,1 96 Taktzyklen.

Im Vergleich zur Methode mit fortgesetztem Subtrahieren ist diese Methode ab 6 abwärts schneller als das fortgesetzte Abziehen. Allerdings kann man die Methode mit dem fortgesetzten Abziehen beschleunigen, indem man zunächst mit höheren Zweierpotenzen des Divisors teilt und dann noch ein einfaches (/2), ein zweifaches (/4) oder mehr Rechtsschieben (jeweils mit Runden) anhängt. Vergleicht man diese Zeiten, verliert die Schmidt-Methode ihren Reiz, weil sie immer länger braucht als das so optimierte Abziehen. Bei unganzzahligen Teilerverhältnissen, die sich nicht aus h¨heren ganzzahligen Zweiervielfachen bilden lassen, ist die Schmidt-Methode hingegen nicht zu schlagen.

Beschleunigung durch radikale Optimierung

Aber gemach, wir kriegen das Beschleunigen der Schmidt-Methode auch noch hin, und dann sind wir schneller als das optimierte fortgesetzte Abziehen. Und das geht so.

Bei kleinen Zahlen geht durch die Schieberei die Zahl, geteilt durch Zweien sehr schnell gegen Null. Wenn aber der Teiler schon Null ist, dann kann man das weitere Teilen und Abziehen auch bleiben lassen. Immer dann wenn das MSB des Teilers Null ist und wenn der LSB-Rest des Teilers schon kleiner ist als der LSB-Rest des Ergebnisses, kann man ebenfalls das weitere Teilen einstellen, denn kein weiteres Teilen und Subtrahieren kann mehr zu einer Änderung des MSB führen. Das spart eine Menge unnötige Teilungen ein, die ehedem nichts mehr am Ergebnis ändern werden.

Einen Nachteil hat das: das Endergebnis ist beim Abbruch noch gar rundungsfähig, denn es fehlen ja noch einige Subtraktionsschritte. Macht aber nix, wir runden das Ganze schon im Vorhinein, indem wir etwas mehr als die Hälfte des Teilers zu der Zahl hinzuaddieren. Das sorgt dann schon für zuverlässiges Runden von Beginn an. Den beim Abbruch erreichten Resultatstand lassen wir also ungerundet und vergessen dessen LSB.

Das Addieren im Vorhinein wiederum hat einen anderen Nachteil: je nach Teilergröße kann jetzt nicht mehr jede Zahl bis 255 gerechnet werden, denn beim Addieren würde ein Überlauf erfolgen. Aber dieser Nachteil dürfte verschmerzbar sein.

Optimiertes 8-Bit-Dividieren Das optimierte Teilen kann man in der LibreOffice-Datei hier testen, und zwar im Rechenblatt "8bit-optimiert". Da bei einem Teiler von 3 zur Rundung etwa 1,5 addiert werden müssen, beginnt die Berechnung nicht mit 255, sondern nur mit 254. Den Rundungsbetrag von 0x0187 kann man übrigens direkt in den Quellcode div3_8.asm hier kopieren.

Nun sieht man in der ersten Spalte, dass der Abbruch der Berechnung schon nach 10 Teilungen erfolgt und gar keine 15 nötig sind. Das beschleunigt das Verfahren entsprechend immens. Bei kleineren Zahlen ist das noch eindrucksvoller, weil schon nach vier oder fünf Teilungen Schluss ist.

Wie man an der Dreier-Teiler-Reihe sieht, wiederholt sich das Schema nach jeder zweiten Teilung des Divisors: einmal subtrahieren und danach einmal nicht. Daher brauchen wir eigentlich auch die hexadezimalen Bitmuster eigentlich nicht und wir können ohne deren Rechtsschieben auskommen.

Division von 100 durch 3, nach Takt und Quellcode optimiert Das ist im Quellcode div3_8.asm hier vorgeführt. Mit ganzen 19 Befehlsworten und in 56 Taktzyklen ist das Ganze erledigt. Und das mit 254 als Divident.

Bei 100 ist es ein Takt mehr. Die Division von 100 durch drei ist rechts im Detail gezeigt. Das
  1. Laden der Zahl dauert einen Takt,
  2. das Addieren von 1,3988 (zur Rundung) schlägt mit 5 Takten zu Buche,
  3. das Kopieren braucht nur zwei Takte,
  4. zweifaches Rechtsschieben und Subtrahieren brauchen je zwei Takte,
  5. ein weiteres Rechtsschieben ohne Abziehen braucht etwas länger, weil die Prüfung ob das MSB schon Null ist, noch hinzukommt,
  6. nach einigen weiteren Durchgängen ist neben dem MSB=0 auch das LSB des Abziehregisterpaars in rN0 kleiner als das LSB des Ergebnisses in rR0 und die weitere Berechnung kann übersprungen werden.
Der Abkürzungsstrategie fallen insgesamt 19 Taktzyklen zum Opfer. Das rechtfertigt den etwas höheren Prüfaufwand für die beiden Abbruchbedingungen gerade noch so. Immerhin entfallen dadurch Teilt man 50, sind es nur noch 47 Taktzyklen, bei 10 nur noch 38. Das ist unschlagbar schnell und auch von getrickstem fortgesetzten Abziehen nicht zu schlagen.

Die Zeichnung gibt es auch als Grafikdatei hier im LibreOffice-Format.

Zuviel versprochen? Nein. Aber noch etwas Wasser in den Wein: bei Teilern ab 11 versagt die Rundungsmethode in ganz seltenen Fällen. Das kommt daher weil 0,51 als Zuschlagfaktor zum Runden bei großen Zahlen etwas zuviel des Guten ist. Nimmt man als Faktor 0,501 oder gar nur 0,500, dann klappts auch mit dem Runden bei großen Zahlen.

Hier noch ein paar Quellcodes mit festen Teilern für eigene Experimente:
Teilen durchReiheBinärreiheQuellcodeTakteWorte
1,520b1010101010101010div1_5_85215
2,540b1001100110011001div2_5_85625
61+30b0100100100100101div6_84923
730b1011011011011011div7_85025


Viel Erfolg mit dem neuen und rasanten 8-Bit-Teilen.

16-Bit-Teilen nach Schmidt

Ermittlung von Bitmuster und Division/Subtraktion bei 16-Bit-Zahlen 16-Bit-Teilen geht im Prinzip genauso wie 8-Bit, nur werden die Zahlen etwas größer. Hier ein Auszug aus dem Blatt "16bit" in der LibreOffice-Calc-Datei hier, das links die Bitmuster-Ermittlung demonstriert und rechts die Division von 65.533 durch 3 mit diesem ermittelten Muster.

Das Bitmuster hat jetzt 32 Bits. Damit es nicht durch Rundungsfehler der Tabellenkalkulation verfälscht wird, erfolgt dessen Ermittlung aus einer großen Zahl. Beim letzten Teilen (4.294.967.296) kommt immer Null heraus, daher würde das letzte Bit (das erste im binären Bitmuster) immer Eins werden. In späteren Tabellen habe ich es manchmal Eins gesetzt (wenn es um die Erkennung wiederkehrender Bitmuster geht, siehe unten). Das letzte Bit ist also egal.

Beim Teilen auf der rechten Seite des Bilds wird das links ermittelte Bitmuster angewendet. Hier erfolgt zunächst die Aufrundung der Ausgangszahl: der Zahl wird das 0,51-fache des Teilers hinzu-addiert (im Quellcode ist das die Konstante cAdd, im Falle von drei als Teiler sind das 1,52999 oder hexadezimal 0x000187AE. Obacht beim Verwenden dieser vereinfachten Formel: ab Teilern von 50 aufwärts rechnet das Teil verkehrt, dann müsste die Formel eigentlich Teiler * 0,501 lauten, bei 500 aufwärts Teiler * 0,5001. Wer so hohe Teiler verwenden will, muss nur die Rundungszelle entsprechend ändern oder riskiert Rundungsfehler.

Die Zahlen sind dezimal deshalb so krumm, weil sie auf zwei Binärbytes hinter dem Komma gerundet sind. Beim Dividieren durch zwei und beim Abziehen wurde übrigens stets abgerundet, um sich das unnütze Aufrunden im Binärcode zu ersparen: es funktioniert auch ohne und kommt auch richtig heraus.

In der folgenden Tabelle sind die Bitmuster und die Rundungsaddierer für das Teilen mit 1,1, 1,5 und 2,5 sowie für 3 bis 30 (außer den Zweierpotenzen) zusammengestellt. Wer noch krummere Teiler verwenden will, muss die Tabellenkalkulation hier anwerfen und sich das Bitmuster selber stricken.

Teilen
durch
Bitmuster: Reihe der binären Teiler zum Subtrahieren:
0=nicht subtrahieren, 1=subtrahieren
Runden
BinärHexadezimalPerioden-
Länge
DezimalHexadezimal
1,10b010011101000101110100010111010000x4E8BA2E8100,5610050x00008F9E
1,50b101010101010101010101010101010100xAAAAAAAA20,7649990x0000C3D7
2,50b100110011001100110011001100110010x9999999941,2749940x00014666
30b010101010101010101010101010101010x5555555521,5299990x000187AE
50b001100110011001100110011001100110x3333333342,5500030x00028CCD
70b110110110110110110110110110110110xDB6DB6DB33,5700070x000391EC
90b110001110001110001110001110001110xC71C71C764,5899960x0004970A
100b011001100110011001100110011001110x666666671 + 45,100060x0005199A
110b010100010111010001011101000101110x51745D17105,6100010x00059C29
120b010101010101010101010101010101110x555555572+26,119950x00061EB8
130b001101110010001101110010001101110x37237237126,6300050x0006A148
140b101101101101101101101101101101110xB6DB6DB71+37,1399990x000723D7
150b011101110111011101110111011101110x7777777747,6499940x0007A666
170b000011110000111100001111000011110x0F0F0F0F88,6699980x0008AB85
180b010011100011100011100011100011110x4E38E38F1+69,1799930x00092E14
190b000001010011110101100001010011110x053D614F189,6900020x0009B0A4
200b110011001100110011001100110011110xCCCCCCCF2+49,6900020x0009B0A4
210b110011110011110011110011110011110xCF3CF3CF1210,7100070x000AB5C3
220b011000101110100010111010001011110x62E8BA2F1+1011,2200010x000B3852
230b110010111101100101111011001011110xCBD97B2F1111,7299960x000BBAE1
240b101010101010101010101010101011110xAAAAAAAF3+212,2400050x000C3D71
250b001110101111000101000011101011110x3AF143AF2012,7500000x000CC000
260b001011100100011011100100011011110x2E46E46F1+1213,2599950x000D428F
270b100001011011110100100001011011110x85BD216F1813,7700040x000DC51F
280b011011011011011011011011011011110x6DB6DB6F2+314,2799990x000E47AE
290b111100101100010000110100111011110x72C434EF3214,7899930x000ECA3D
300b111011101110111011101110111011110xEEEEEEEF1+415,3000030x000F4CCD


Man erkennt an der Tabelle, dass nur beim Teilen durch 29 kein Periodenmuster auftritt. Bei allen anderen ist die Periodenlänge kürzer. Manchmal muss man eine oder zwei Teilungen vorher durchführen, um zu einer Periode zu gelangen. Das ist bei 12, 14, 18, 22, 24, 26 und 30 der Fall und mit "1 +" etc. angegeben.

In der folgenden Tabelle sind Assembler-Quellcodes für ausgewählte Periodenlängen verlinkt, sodass man sich den Quellcode anschauen und für eigene Zwecke abkupfern kann. In der Tabelle sind auch die nötigen Takte Ausführungszeit für Null und für die größtmögliche Zahl angegeben sowie die Anzahl an Instruktionsworten.

TeilerPeriodenQuellcodeTakteBefehls-
worte
Min.Max.
32div3_p2_169520036
73div7_p3_1611220444
141+3div14_1p3_1616628152
54div5_p4_1610118248
div5_p4v_169921550
101+4div10_1p4_1610919056
div10_1p4v_1610520866
216div21_p6_1610819665
1110div11_p10_168822689
2932div29_p32_1644743
19 diskretdiv29_14_16110111
KlassischdivN_16_821724


Sind für den gleichen Teiler zwei Quellcodes angegeben, dann enthält der zweite eine zusätzliche Abbruch-Abfrage nach einem Teil der Dividiererei-Periode. Man sieht am Falle der Teilers 5 und 10, dass solche zusätzlichen Abfragen bei kleinen Zahlen nicht viel Unterschied machen, aber bei großen die Ausführungszeiten erheblich verlängern.

Beim Teiler 29 wurde in der ersten Variante mit Periodenlänge 32 das gesamte Bitmuster 0x72C434EF in vier Register gepackt und jeweils nach jedem Teilen eine Position nach rechts geschoben. Rotierte dabei eine Null heraus, wurde nicht abgezogen. Erreicht das unterste Byte des Bitmusters Null, wurde die Schieberei beendet. Da dabei alle 32 Schiebe- und zusätzlich auch noch 17 Subtrahier-Operationen zu je vier Takten ausgeführt werden müssen, dauert diese Variante mit 447 Takten am allerlängsten. Dafür ist sie die code-sparendste Schmidt-Divisions-Variante.

Dass es auch vier Male schneller geht, zeigt die zweite Variante: da bei 29 als Teiler im Höchstfall nur 17 Divisionen maximal ausgeführt werden müssen und laut 29-er Bitmuster die letzten drei davon gar nicht subtrahiert werden müssen, reichen 14 Divisionen durch zwei und 10 Subtraktionen schon aus. Und: wenn die 14 Divisionen und 10 Subtraktionen einfach hintereinander weg stehen und zwischendurch gar keine Abfragen nötig sind, kriegt man zwar mit 111 Worten das längste Programm, aber mit 110 Takten auch das Schnellste. Das gilt zwar nur für große Zahlen, aber diese Methode braucht IMMER 110 Takte, egal für welche Zahl. Man sieht: bei der Schmidt-Methode gibt es jede Menge Optimierungspotenzial.

Fazit

Als Vergleichsmaßstab ist in der letzten Zeile der Tabelle auch noch der Quellcode für den klassischen 8-Bit-Teiler angegeben. Man sieht, dass
  1. die klassische Methode den kürzesten Controllercode produziert (wer also Flash sparen muss, nimmt den),
  2. die Ausführungszeiten bei der Schmidt-Methode häufig viel kürzer sind als bei der klassischen Methode, nur bei sehr großen Zahlen und beim Teilen durch 11 oder 14 ist die klassische Methode schneller (deren Zeiten bei allen Zahlen gleich lang sind).
  3. Liegt gar keine Periodizität vor, wie beim Teilen durch 29, kann man dennoch viel Ausführungszeit sparen, wenn man es elegant und intelligent anstellt.


Zum Seitenanfang

©2021 by http://www.avr-asm-tutorial.net