MUL & DIV (Ganzzahl)

weitersagen ...
Tweet about this on TwitterShare on FacebookShare on Google+Share on LinkedIn

CBM prg StudioGanzahl MULtiplikation und DIVision

Hier geht es zwar nicht um die höhere Mathematik, aber etwas Erfahrung mit dem Assembler und der Programmierung solltet ihr bereits haben.

Die „Mnemonics“, „Zahlensysteme“, „Wie der Rechner rechnet“ und kleinere Programmieraufgaben stellen für euch sicher kein Problem mehr dar, sonst würdet ihr euch doch bestimmt nicht mit der Multiplikation und Division beschäftigen.

Bevor gleich jemand meint „Das kann man aber besser bzw. schneller lösen!JA, der hat recht! Es geht hier auch nicht um die perfekte Lösung, sondern ums grundsätzliche Verständnis.

Leider muss ich euch, wie bereits an anderer Stelle erwähnt, enttäuschen. Der 6510 (6502) besitzt weder für die Multiplikation noch für die Division entsprechende Mnemonics. Es gibt es also keinen MUL– oder DIV-Befehl. Wir müssen uns daher eigene Routinen schreiben, um diese Aufgaben zu erledigen.
 

Du lügst oder es gibt sie doch!
Wenn euch, wie ich hoffe, die verfügbaren Mnemonics gut bekannt sind, dann werdet ihr bei meiner Einleitung wohl gedacht haben, so ganz stimmt das aber nicht.

Eine Befehlsgruppe ermöglicht die Multiplikation und Division. Dabei handelt es sich zwar nur um einen Sonderfall, aber der ist häufig hilfreich. Gemeint sind die Verschiebebefehle asl / lsr und die Rotationsbefehle  rol / ror (vorsicht mit dem Carry-Flag). Mit diesen Befehlen könnt ihr durch eine Verschiebung der BITs nach links eine Multiplikation mit zwei und durchs Verschieben nach rechts eine Division durch zwei erreichen. Durch mehrfaches Anwenden eines Befehls könnt ihr so MUL & DIV mit 2, 4, 8, 16 usw. vornehmen und dass sehr flott. Über das C-Flag könnt ihr bei einer Verschiebung nach rechts sogar den Rest ermitteln. Auch wenn wir die Befehle gleich verwenden, möchte ich hier nicht erneut auf deren genaue Funktionsweise eingehen. Sollte ihr damit nicht so ganz vertraut sein, dann schaut euch besser nochmal die Erklärungen zum LSR und ROL an.

 

Das Rahmenprogramm
Um unsere Ergebnisse zu kontrollieren, schlage ich folgendes Progrämmchen als „Gerüst“ vor:

Wir verwenden gleich die Zero-Page, um dort unsere Zahlen abzulegen und das Ergebnis zu speichern. In unseren Beispielen rechnen wir immer mit 8-Bitzahlen. Dabei teilen sich Multiplikator und Dividend sowie Multiplikant und Divisior je eine Speicherstelle. Ich habe hier extra verschiedene Namen für die selbe Speicherstelle gewählt, damit in den Funktionen klarer wird, was wir dort gerade machen. Außerdem sehen wir noch jeweils 16-BIT für eine Hilfsvariable und das Ergebnis vor. Über die Konstante  OFFSET könnt ihr die Ausgabe etwas verschieben. Beachtet aber, dass sie sich immer komplett in der ersten Page des Bildschirmspeichers befinden muss.
Dann haben wir einen Hauptteil, der einfach den BS löscht, unsere Zahlen in die Zero-Page schreibt, die Rechenfunktion (kommt gleich) startet und schließlich das Ergebnis ausgibt.
Als Hilfsfunktionen verwenden wir clrScreen: (löscht den Bildschirm) und hexout: (Hex-Ausgabe).

Jetzt sollten wir mal etwas rechnen…

 

Die Brute-ForceinfoBrute-ForceUmgangssprachlich: In der Informatik eine zwar funktionierende, aber nicht besonders elegante / effiziente Lösung für ein Problem finden.-Methode
Eine funktionierende Möglichkeit wäre es, die Multiplikation und Division über Schleifen zu lösen. Dabei verwenden wir für MUL die wiederholte Addition und für DIV die Subtraktion. Um erstmal lauffähige Funktionen zu erhalten, setzen wir das einfach in die Tat um. Laßt uns auf diese Art zwei 8-BIT Zahlen multiplizieren.

Nehmt diese Funktion in das Rahmenprogramm (z. B. vor clrScreen:) auf.

Wir legen Multiplikator und Multiplikant als 8-BIT auf der Zero-Page ab, dort finden wir zum Schluß ebenfalls das 16-BIT Ergebnis. Zu Beginn von bruteforce_mul:  setzen wir das Ergebnis erstmal auf Null. Wir benötigen für die Multiplikation zweier 8-BIT Zahlen, natürlich ein 16-BIT großes Ergebnis. Dann laden wir den Multiplikator ins X-Register und prüfen, ob dieser ungleich null ist. Falls ja geht es zur Schleife, sonst verlassen wir die Funktion direkt wieder. Diese Prüfung ist wichtig, da sonst statt 0 mit 256 multipliziert wird.
In der @loop:-Schleife wird zunächst der Multiplikant in den Akku geholt und zum LSB vom Ergebnis addiert. Den Akkuinhalt schreiben wir dann zurück und holen das MSB. Um das Carry-Flag zu verarbeiten addieren wir anschließend einfach eine 0 und schreiben das MSB zurück in den Speicher. Dann wird das X-Register verringert und wir wiederholen das Ganze, solange X größer 0 ist. Somit wurde der Multiplikant, so oft, wie es der Multiplikator vorgibt, zum Ergebnis addiert.

Schon ist die Routine fertig! Ruft diese Funktion jetzt noch im Hauptteil (hinter ;*** Rechenfunktion aufrufen) mit jsr bruteforce_mul: auf und startet das Programm.

Sofern ihr die Werte aus meinem Beispiel beibehalten habt, sollte eure Ausgaben dieser gleichen.

Ausgabe der Multiplikation
Ausgabe der Brute-Force Multiplikation

Probiert jetzt mal verschiedene Werte für den Multipliaktor und Multiplikanten aus.

Wenn man diese Holzhammer-Methode verwenden möchtet, bieten sich durchaus noch Verbesserungen im Detail an. Vielleicht fallen euch ja welche ein und ihr setzt sie um (denkt z. B. mal über die Schleifen-Anzahl und Sonderfälle nach).

 

Die Division kann man auf die gleiche Weise angehen. Nur wird diesmal die Subtraktion benötigt. Teilen wir zwei 8-BIT-Zahlen…

Auch hier verwenden wir wieder die Zero-Page, dort speichern wir Dividend, Divisor und das Ergebnis. Diesmal reichen aber drei 8-BIT Speicherstellen. Gleich am Anfang von bruteforce_div: setzen wir das Ergebnis natürlich wieder auf 0. Danach prüfen wir, ob „durch 0“ geteilt werden soll. Wir verlassen die Funktion dann einfach, eigentlich gehört dort eine Fehlermeldung „Division durch null“ oder zumindest ein Fehler-Kennzeichen hin. Falls der Dividend 0 ist, brauchen wir nicht zu teilen und können die Routine direkt wieder verlassen. Sind alle Voraussetzungen gegeben, dann beginnen wir bei @skip: mit dem Teilen. Wir werden gleich laufend den Divisior vom Dividend abziehen, aber nur solange der Dividend größer oder gleich dem Divisor ist. Das prüfen wir als erstes, ist er größer oder gleich, geht es bei  @skip1: weiter, sonst wird der Rest, der sich im Akku befindet in die Zero-Page nach ZP_DIVIDEND zurückgeschrieben. Bei @skip1: subtrahieren wir vom Akku einfach den Divisor und erhöhen unser Ergebnis um eins. Nun springen wir wieder nach @skip:, wo erneut geprüft wird, ob der „restliche“ Dividend (immer noch) größer als der Divisor (oder zumindest gleich groß) ist.

Am Schluß findet ihr in  ZP_ERGEBNIS den ganzzahligen Quotinenten und in ZP_DIVIDEND den eventuellen Rest. Wer die original Werte nicht verändern möchte, kann den Rest natürlich auch anderweitig speichern.

Da wir jetzt auch noch den Rest ausgeben müssen, habe ich das Rahmenprogramm etwas umgebaut.

Ich verwende hier die „bedingte Assemblierung“. Mit den Anweisungen ifdef <KONSTANTE> ... else ... endif können wir den Assembler dazu bringen, dass nur aktuell benötigte Befehle ins endgültige Programm übernommen werden. Ich habe hier die Konstante DOMUL für die Prüfungen festgelegt und auf 1 gesetzt. Nur wenn diese Konstante einen Wert ungleich null hat (dies war nur bis zum CBM prg Studio 3.3.0 so! Dank am Marko, der dies festgestellt und gemeldet hat.) überhaupt definiert ist, werden die Anweisungen hinter ifdef bis zum  endif oder einem else ausgeführt, sonst ignoriert der Assembler den entsprechenden Block bei der Programmerstellung. Ihr  müsst also nur ein Semikolon ; vor die Zeile  DOMUL = 1 ;Für DIVision auskommentieren! schreiben, damit die DIVision, statt der MULtiplikation ausgeführt wird.

Ein kleines Beispiel

Dieses Vorgehen ist immer dann interessant, wenn ihr z. B. Testausgaben in euer Programm aufnehmen wollt oder verschiedene Fassungen (z. B. für PAL oder NTSC) benötigt. Dann könnt ihr durch die bedingte Assemblierung alles in den Source aufnehmen und braucht vor der Erstellungen nur die entsprechenden „Schalter“ zu setzen, sprich die Konstanten ein- oder auskommentieren (z. B. DEBUG = 1 oder ;DEBUG = 1).
Sehr schade ist, dass das CBM prg Studio, im Gegensatz zu anderen Assemblern, keine Verschachtelung bei der bedingten Assemblierung beherrscht!

Ihr könnt nun DOMUL = 1 einfach ein- oder auskommentieren, um die jeweilige Rechenfunktion auszuführen. Wir wollen nun die Division kontrollieren, achtet also auf das Semikolon ;DOMUL = 1 und startet dann das Programm.

Das Ergebnis der Brute-Force Division.
Das Ergebnis der Brute-Force Division.

Wie ihr seht passt die $17 fünf mal in $83 (5 * $17 = $73) es bleibt also ein Rest von $10, der nicht verteilt werden konnte (wir rechnen hier ja nur mit Ganzahlen).

Damit haben wir jetzt schon zwei einfache Möglichkeiten um Zahlen zu multiplizieren oder zu teilen. Diese lassen sich natürlich noch etwas optimieren oder für größere Zahlen umbauen. Um mal schnell (OK, kurz) etwas zu berechnen reichen diese Funktionen evtl. aus, aber sollten sie häufiger oder in zeitkritischen Situationen benötigt werden, dann wäre ein eleganterer und vor allem schnellerer Ansatz wünschenswert.

 

Optimierte MUL- & DIV-Funktionen
Die Brute-Force-Funktionen klappen zwar, benötigen aber ggf. unverschämt viel Rechenzeit (zählt mal die Taktzyklen für 255 * 255). Schade, dass nicht alles so schnell wie mit den Verschiebe- / Rotations-Befehlen geht. Gibt es evtl. einen Weg die obige Addition- und Subtraktion-Methode damit zu kombinieren?

Vielleicht sollten wir erstmal klären, wie man Binärzahlen überhaupt multipliziert. Bitte nicht lachen, eigentlich kennt ihr dass aus der Grundschule. Um das Beispiel übersichtlich zu halten, nehmen wir nur zwei Nibble.

Wir gehen also genau so vor, wie wir es in der Schule, beim schriftlichen Multiplizieren gelernt, haben. Es wird die erste Stelle des Multiplikators mit dem Multiplikanten multipliziert (watn Satz 😉 ), dann die nächste und das Ergebnis um eine Stelle nach rechts verschoben usw. Hier ist es sogar noch einfacher, da wir nur 0 und 1 haben. Zum Schluß werden dann die einzelnen Werte wieder addiert.

Dass schreit doch förmlich nach den Schiebe- & Rotations-Befehlen, oder? Laßt uns also eine neue Funktion entwickeln.

Die Funktion ist eigentlich ganz einfach. Sie legt den Multiplikanten in einem 16-BIT Hilfsregister ab. Dabei wird der Multiplikant ins MSB geschrieben und das LSB auf 0 gesetzt. Auch das Ergebnis setzen wir natürlich auf 0. Da wir eine 8-BIT-Multiplikation vornehmen, muss unsere Schleife max. 8 mal durchlaufen werden, das X-Register dient als Schleifenvariable. Bei @loop: beginnt nun die Schleife für die Multiplikation. Als erstes wird die 16-BIT-Hilfsvariable um ein BIT nach rechts „geshiftet“. Dann wird der Multiplikator um ein BIT nach links geshiftet und kontrolliert, ob das herausgefallene BIT eine 1 war (die landet dann ja im Carry-Flag). War es eine 1, dann müssen wir die Hilfsvariable zum Ergebnis addieren, sonst geht es direkt bei  @skip: weiter. Dort angekommen wird die Schleifenvariable im X-Register verringert und solange zu @loop: gesprungen, bis X null ist. Dann sind wir auch schon fertig.

Auf den ersten Blick sieht die Funktion aufwändiger, als die Brute-Force-Methode aus. Sie benötigt in dieser Form auch mehr Speicher und in bestimmten Fällen sogar mehr Taktzyklen als die BF-Funktion.

Werft mal einen Blick auf die Taktzyklen:

Wie ihr seht bewegen sich die Zeiten für die Shift-Version in einem überschaubaren Rahmen, bei Brute-Force explodieren sie geradezu. Ich hoffe zwar, dass ich mich oben nicht verzählt habe, aber es kommt nicht wirklich auf die korrekte Anzahl Taktzyklen an. Wichtig ist zu erkennen, dass die Brute-Force-Version ab einem bestimmten Punkt (hier sobald der Multiplikant größer als 14 ($0E) ist) immer mehr Zeit als die Shift-Fassung benötigt.
Wir rechnen hier nur mit 8-BIT Zahlen, wenn wir zwei 16- oder gar 32-BIT Zahlen multiplizieren wollen, wird die BF-Funktion endgültig unbrauchbar. Dort müssten im „worst case“ bei 16-BIT schon 65535, bei 32-BIT sogar 4294967295 Schleifendurchläufe getätigt werden. Bei der Shift-Fassung bräuchte die Schleife nur 16 oder 32 mal durchlaufen werden. Es ist klar, dass beide Routinen dafür noch angepasst werden müssten und dann natürlich auch mehr TZ benötigen!

Diese Fassung ist zwar nicht das Optimum, aber als Ausgangspunkt für eure eigenen Routinen schon mal ein Anfang.

Ihr müsst nun nur statt jsr bruteforce_mul: die neue Funktion mit jsr shift_mul: aufrufen. Ein Start sollte keinen erkennbaren Unterschied zeigen. Warum auch, dass Ergebnis ist ja gleich. Aber es greifen die eben erwähnten Vorteile.

 

Dass ihr eigentlich auch die Division von zwei Binärzahlen schon seit der Grundschule beherrscht, sollte euch jetzt nicht mehr überraschen.

Das sollte jetzt kein Problem mehr darstellen, also direkt auf zur neuen Funktion  shift_div:. Um nicht zu Copy & Paste Programmieren zu werden, solltet ihr mal selbst versuchen, die benötigte Funktion zu schreiben. Denn dass bedeutet Programmieren eigentlich. Eine gegebene Aufgabe in ein eigenes Programm umwandeln. Setzt einfach obiges Vorgehen Schritt für Schritt um. Es kommt dabei nicht auf Eleganz oder eine optimale Lösung an.

Eine Möglichkeit findet ihr sonst hier, diesmal sollten die Kommentare im Source als Erklärung reichen.

Ich hoffe ihr habt erfolgreich eure eigene Routine entwickelt, dass war es dann auch schon mit der Division.

 

Wo ist das Vorzeichen?
Ist euch aufgefallen, dass wir bisher keine Rücksicht auf das Vorzeichen genommen haben? Solange wir nur mit Zahlen größer/gleich Null arbeiten, ist alles kein Problem. Rechnen wir aber -1 * -1 (in Hex bei 8-BIT $FF * $FF) dann erhalten wir $FE01, dass kann so nicht stimmen, richtig wäre 1 (oder $01). Auch bei der Division gibt es Probleme. Teilen wir die Zahlen von eben, dann kommt sogar das Richtige raus: -1 / -1 ($FF / $FF) ergibt 1. Aber schon bei 1 / -1 ($01 / $FF) kommen wir auf $00 mit dem Rest: $01.

Was kann man nun dagegen machen?
Frei nach „minus mal minus ergibt plus“ können wir die beiden Zahlen positiv betrachten und dann beim Ergebnis und ggf. beim Rest das Vorzeichen wieder umkehren, falls diese vorher unterschiedlich waren.

Hier die umgebaute Multiplikation:

Die Funktion sollte mittlerweile selbsterklärend sein. Das Umwandlung einer negativen in eine positive Zahl erfolgt durch Umkehrung der Schritte für das Zweierkomplement. Die Division anzupassen überlasse ich nun euch.

Eine weitere schöne Übung wäre es die Bildschirmausgabe von hex auf dezimal umzustellen (da ihr nun durch 10 teilen könnt, läßt sich das relativ einfach bewerkstelligen) und dabei sollte natürlich auch das Vorzeichen beachtet werden.

Wie immer liegt es natürlich bei euch bzw. an eurem Programm, ob ihr Vorzeichen benötigt oder nicht.


Fazit
Damit sind wir am Ende der Ganzahl Multiplikation und Division angelangt.
Nun wisst ihr also, wie man mit dem 6510 (6502) multipliziert und dividiert. Mit obigen Routinen  solltet ihr für die Zukunft ( :mrgreen: Zukunft bei so einer alten Kiste) gewappnet sein. Es gibt natürlich noch andere Wege, wie man diese Rechnungen vornehmen kann. Einige erkaufen sich z. B. Geschwindigkeit, durch vorberechnete Tabellen (die zum Teil einige KB im Speicher belegen). Wenn man den Platz hat und eine flottere Berechnung benötigt ist das sicher eine Alternative.


Schrott!!Naja...Geht so...Ganz gut...SUPER! (9 Bewertungen | Ø 4,33 von 5 | 86,67%)

Loading...


<<< zurück |

weitersagen ...
Tweet about this on TwitterShare on FacebookShare on Google+Share on LinkedIn

4 Gedanken zu „MUL & DIV (Ganzzahl)“

  1. Hallo Jörn,

    Vielen Dank für Dein Assembler Tutorial!

    Mir ist folgendes aufgefallen (korrigiere mich, falls ich falsch liege):
    Die Compiler-Direktive „ifdef“ prüft doch nur auf Definiertheit, oder?
    Es sollte doch egal sein, welchen Wert DOMUL hat.
    Solange es definiert ist, wird der Codeteil mit der Multiplikation eineblendet.
    Sobald ich DOMUL auskommentiere, sollte wieder der Divisionsteil eingeblended werden.

    Zumindest der Assembler im CBM prg studio verhält sich so.

    1. Hallo Marko,
      natürlich hast du prinzipiell recht, aber…
      Als ich den Beitrag Ende 2013 geschrieben habe, hat sich das zu der Zeit aktuelle CBM prg Studio, wie im Text beschrieben, verhalten.
      Erst mit der Version 3.3.0 wurde dies geändert:
      Bugs Fixed:
      Assembler:
      Wrong rules for ifdef when variable is zero.

      Um solchen Problemen auf die Spur zu kommen, bin ich auf die Mithilfe der Leser angewiesen.

      Daher vielen Dank fürs Melden und ich habe den Text eben überarbeitet.

      Gruß,
      Jörn

  2. Hallo Jörn,

    in die Routine zum Löschen des Bildschirms hat sich ein kleiner Fehler eingeschlichen. Die 3. Page des Bildschirmspeichers muss mit „sta $0600,X“ beschrieben werden und nicht mit „sta $0500,X“.

    Schöne Grüße
    Alex

Schreibe einen Kommentar


Beachtet bitte, dass ich eure Kommentare erst manuell freigegeben muß, bevor sie auf der Seite erscheinen! Da ich nicht pausenlos am Rechner sitze, kann es schon mal etwas dauern, bis ein Kommentar für alle sichtbar ist.

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Protected by WP Anti Spam