Erstellt: 10. November 2013 (zuletzt geändert: 1. Januar 2018)

MUL & DIV (Ganzzahl)

Ganzahl MULtiplikation und DIVision

C64 Studio & AMCE

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, das stimmt!
Es geht hier auch nicht um die perfekte Lösung, sondern um das 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 sowie 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 MULtiplikationen & DIVisionen mit 2, 4, 8, 16 usw. vornehmen und das 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. Solltet 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:

ZP_MULTIPLIKATOR        = $fb
ZP_DIVIDEND             = ZP_MULTIPLIKATOR
ZP_MULTIPLIKANT         = $fc
ZP_DIVISOR              = ZP_MULTIPLIKANT
ZP_ERGEBNIS             = $fd
ZP_HELP                 = $02

OFFSET                  = $28   ;Offset für die BS-Ausgabe

;*** Startadresse BASIC-Zeile
*=$0801
 !word asmStart-2,2018
 !text $9e," 2062",$00,$00,$00

!zone asmStart
asmStart 
 cld                            ;zur Sicherheit D-Flag löschen
 jsr clrScreen                  ;BS löschen

 lda #$83                       ;Multiplikator / Dividend
 sta ZP_MULTIPLIKATOR
 ;sta ZP_DIVIDEND

 ldy #OFFSET + $00
 jsr hexOut                     ;ausgeben

 lda #$17                       ;Multiplikant / Divisor
 sta ZP_MULTIPLIKANT
 ;sta ZP_DIVISOR
 ldy #OFFSET + $06
 jsr hexOut                     ;ausgeben

 lda #"*"
 sta $0404+OFFSET
 lda #"="
 sta $040a+OFFSET

 ;*** Rechenfunktion aufrufen


 ldy #OFFSET + $0c             ;Position festlegen
 lda ZP_ERGEBNIS+1              ;Ergebnis (MSB) 
 jsr hexOut                     ;inkl. $ ausgeben

 ldy #OFFSET + $0e              ;Position festlegen
 lda ZP_ERGEBNIS                ;Ergebnis (LSB)
 jsr hexOut2                    ;OHNE $ ausgeben

 rts                            ;zurück zum BASIC

 
 
;*******************************************************************************
;*** Bildschirm löschen (füllen)
;*******************************************************************************
;*** Übergabe: -
;*******************************************************************************
;*** Rückgabe: -
;*******************************************************************************
;*** ändert  : A, X, SR
;*******************************************************************************
!zone clrScreen
clrScreen
 ldx #$00                       ;256 Durchläufe
 lda #" "                       ;Zeichen zum Löschen (Füllen)
.loop
 sta $0400,x                    ;1. Page des BS-Speichers
 sta $0500,x                    ;2. Page
 sta $0600,x                    ;3. Page
 sta $0700-24,x                 ;4. Page (Sprite-Pointer beachten)
 dex
 bne .loop

 rts                            ;zurück

 
 
;*******************************************************************************
;*** Eine Zahl hexadezimal ausgeben
;*******************************************************************************
;*** Übergabe: A = Zahl
;***           Y = Position ab $0400
;*******************************************************************************
;*** Rückgabe: -
;*******************************************************************************
;*** ändert  : X, Y, SR
;*******************************************************************************
!zone hexOut
hexOut
 pha
 lda #"$"                       ;$ ausgeben
 sta $0400,Y
 pla
hexOut2                         ;start für Zahlen über 8-Bit
 pha
 pha
 and #%00001111
 tax
 lda hexvalues,x
 sta $0402,y                    ;unteres Nibble ausgeben
 pla
 lsr
 lsr
 lsr
 lsr
 tax
 lda hexvalues,x
 sta $0401,y                    ;oberes Nibble ausgeben
 pla

 rts                            ;zurück

hexvalues
 !scr "0123456789abcdef"        ;Text für die Ausgabe

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…

Brute-Force 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. Einen solchen Ansatz bezeichnet man häufig als Brute-ForceinfoBrute-ForceUmgangssprachlich: In der Informatik eine zwar funktionierende, aber nicht besonders elegante / effiziente Lösung für ein Problem finden.. Laßt uns auf diese Art einfach mal zwei 8-Bit Zahlen multiplizieren.

Brute-Force Muliplikation

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

;*******************************************************************************
;*** Brute-Force: 8-BIT Multiplikation durch wiederholte Addition
;*******************************************************************************
;*** Übergabe: ZP_MULTIPLIKATOR
;***           ZP_MULTIPLIKANT
;*******************************************************************************
;*** Rückgabe: ZP_ERGEBNIS (16-BIT)
;*******************************************************************************
;*** ändert  : A, X, SR
;*******************************************************************************
!zone bruteforce_mul
bruteforce_mul
 lda #$00                       ;Ergebnis auf 0 setzen
 sta ZP_ERGEBNIS
 sta ZP_ERGEBNIS+1
 ldx ZP_MULTIPLIKATOR           ;Multiplikator als Schleifenzähler
 bne .loop                      ;wenn größer 0 'rechnen'

 rts                            ;sonst zurück zum Aufrufer

.loop
 lda ZP_MULTIPLIKANT            ;Multiplikant in den Akku
 clc                            ;C-Flag löschen
 adc ZP_ERGEBNIS                ;Akku zum LSB addieren
 sta ZP_ERGEBNIS                ;und speichern
 lda ZP_ERGEBNIS+1              ;MSB in den Akku
 adc #$00                       ;0 addieren (wg. Carry)
 sta ZP_ERGEBNIS+1              ;speichern
 dex                            ;Schleifenzähler (MULTIPLIKATOR) verringern
 bne .loop                      ;solange größer 0, nochmal

 rts                            ;zurück zum Aufrufer

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

Brute-Force Division

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

;*******************************************************************************
;*** Brute-Force: 8-BIT Division durch wiederholte Subtraktion
;*******************************************************************************
;*** Übergabe: ZP_DIVIDEND
;***           ZP_DIVISOR
;*******************************************************************************
;*** Rückgabe: ZP_ERGEBNIS (8-BIT)
;***           ZP_DIVIDEND (8-BIT) enthält den evtl. Rest
;*******************************************************************************
;*** ändert  : A, X, SR
;*******************************************************************************
!zone bruteforce_div
bruteforce_div
 lda #$00                       
 sta ZP_ERGEBNIS                ;Ergebnis auf 0 setzen
 lda ZP_DIVISOR                 ;wenn durch 0 geteilt wird
 beq .exit                      ;raus (eigentlich einen Fehler anzeigen)
 lda ZP_DIVIDEND                ;falls 0 geteilt werden soll
 beq .exit                      ;raus (Ergebnis wäre wieder 0)
.skip
 cmp ZP_DIVISOR                 ;vergleiche Dividend und Divisior
 bcs .skip1                     ;wenn der Dividend größer oder gleich ist, weitermachen
 sta ZP_DIVIDEND                ;sonst Rest merken
.exit
 rts                            ;zurück zum Aufrufer

.skip1
 sec                            ;C-Flag für Subtraktion setzen
 sbc ZP_DIVISOR                 ;Divisor vom Dividend abziehen
 inc ZP_ERGEBNIS                ;Ergebnis um 1 erhöhen
 jmp .skip                      ;nochmal versuchen

Auch hier verwenden wir wieder die Zero-Page, dort speichern wir Dividend, Divisor und das Ergebnis. Dieses Mal 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 wollen, habe ich das Rahmenprogramm etwas umgebaut.

ZP_MULTIPLIKATOR        = $fb
ZP_DIVIDEND             = ZP_MULTIPLIKATOR
ZP_MULTIPLIKANT         = $fc
ZP_DIVISOR              = ZP_MULTIPLIKANT
ZP_ERGEBNIS             = $fd
ZP_HELP                 = $02

OFFSET                  = $28   ;Offset für die BS-Ausgabe

DOMUL                   = 1     ;Für DIVision auskommentieren!

;*** Startadresse BASIC-Zeile
*=$0801
 !word asmStart-2,2018
 !text $9e," 2062",$00,$00,$00

!zone asmStart
asmStart 
 cld                            ;zur Sicherheit D-Flag löschen
 jsr clrScreen                  ;BS löschen

 lda #$83                       ;Multiplikator / Dividend
!ifdef DOMUL {
 sta ZP_MULTIPLIKATOR
} else {
 sta ZP_DIVIDEND
}
 ldy #OFFSET + $00
 jsr hexOut                     ;ausgeben

 lda #$17                       ;Multiplikant / Divisor
!ifdef DOMUL {
 sta ZP_MULTIPLIKANT
} else { 
 sta ZP_DIVISOR
}
 ldy #OFFSET + $06
 jsr hexOut                     ;ausgeben

 lda #"*"
 sta $0404+OFFSET
 lda #"="
 sta $040a+OFFSET

 ;*** Rechenfunktion aufrufen
!ifdef DOMUL {
 jsr bruteforce_mul
 
 ;*** Ausgabe der Multiplikation
 lda #'*'
 sta $0404 + OFFSET
 ldy #OFFSET + $0c              ;Position festlegen
 lda ZP_ERGEBNIS+1              ;Ergebnis (MSB) 
 jsr hexOut                     ;inkl. $ ausgeben
 
 ldy #OFFSET + $0e              ;Position festlegen
 lda ZP_ERGEBNIS                ;Ergebnis
 jsr hexOut2                    ;OHNE $ ausgeben
} else {
 jsr bruteforce_div
 
 ;*** Ausgabe der Division
 ldy #OFFSET + $0c              ;Position festlegen
 lda ZP_ERGEBNIS                ;Ergebnis
 jsr hexOut                     ;inkl. $ ausgeben
 
 ldy #OFFSET + $15              ;Position festlegen
 lda ZP_DIVIDEND                ;Rest
 jsr hexOut                     ;inkl. $ ausgeben

 lda #":"
 sta $0404 + OFFSET
 lda #$12						;R
 sta $0410 + OFFSET
 lda #$05						;E
 sta $0411 + OFFSET
 lda #$13						;S
 sta $0412 + OFFSET
 lda #$14						;T
 sta $0413 + OFFSET
}

 rts                            ;zurück zum BASIC

Ich verwende hier die „bedingte Assemblierung“.
Mit !ifdef <KONSTANTE> { … } else { … } 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, der Wert ist vollkommen willkürlich und hat keinen Einfluss auf die !ifdef-Prüfung. Sobald diese Konstante definiert ist (unabhängig vom zugewiesenen Wert), werden die Anweisungen zwischen den geschweiften Klammern { … } hinter !ifdef DOMUL assembliert. Ist die Konstante nicht definiert, dann wird der Block hinter !ifdef komplett ignoriert. Sollte es (wie hier) einen else-Block geben, dann werden stattdessen die Anweisungen zwischen den geschweiften Klammern hinter else ins Programm übernommen. 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

Wir gehen davon aus, dass DOMUL definiert ist...

 lda #$83                       
!ifdef DOMUL {
 sta ZP_MULTIPLIKATOR
} else {
 sta ZP_DIVIDEND
}
 ldy #OFFSET + $00

Durch die bedingte Assemblierung sieht der Quellcode
für den Assembler bei der Programmerstellung so aus:

 lda #$83                       
 sta ZP_MULTIPLIKATOR
 ldy #OFFSET + $00

Die Zeile sta ZP_DIVIDEND wird überhaupt nicht beachtet.

Kommentieren wir DOMUL = 1 aus und lassen das Programm erstellen,
dann ignoriert der Assembler sta ZP_MULTIPLIKATOR

 lda #$83                       
 sta ZP_DIVIDEND
 ldy #OFFSET + $00

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

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.

Wie ihr seht, passt die $17 fünf mal in $83 ($05 * $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.

Rechnen wir einfach:

%1100 * %0011     (also 12 * 3)
         ----           -------
 1       0011           1    3 
  1       0011           2    6
   0       0000              == 
    0       0000             36 
         =======             |
         0100100 <------------

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.

MUL mit Shift & Rotate

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

;*******************************************************************************
;*** 8-BIT Multiplikation durch Bitverschiebung
;*******************************************************************************
;*** Übergabe: ZP_MULTIPLIKATOR
;***           ZP_MULTIPLIKANT
;*******************************************************************************
;*** Rückgabe: ZP_ERGEBNIS (16-BIT)
;*******************************************************************************
;*** ändert  : A, X, SR
;*******************************************************************************
!zone shift_mul
shift_mul
 lda ZP_MULTIPLIKANT            ;Multiplikant
 sta ZP_HELP+1                  ;ins MSB der Hilfsvariablen
 lda #$00                       ;auf null setzen:
 sta ZP_HELP                    ;LSB der Hilfsvaribalen
 sta ZP_ERGEBNIS                ;Ergebnis
 sta ZP_ERGEBNIS+1
 ldx #$08                       ;8-BIT, also 8 Durchläufe
.loop
 lsr ZP_HELP+1                  ;Hilfsvariable nach
 ror ZP_HELP                    ;rechts shiften
 asl ZP_MULTIPLIKATOR           ;Multiplikator <- shiften
 bcc .skip                      ;prüfe ob höchstes BIT gesetzt war
                                ;falls nicht -> .skip (keine Addition)
 clc                            ;sonst für Addition C-Flag löschen
 lda ZP_HELP                    ;LSB von Hilfsvariablen
 adc ZP_ERGEBNIS                ;und Ergebnis addieren
 sta ZP_ERGEBNIS                ;und speichern
 lda ZP_HELP+1                  ;jetzt ist das MSB inkl. Carry-Flag dran
 adc ZP_ERGEBNIS+1              
 sta ZP_ERGEBNIS+1
.skip
 dex                            ;Schleifenzähler verringern
 bne .loop                      ;solange nicht 0 nochmal -> .loop
 
 rts                            ;sonst zurück zum Aufrufer 

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:

Aufgabe (HEX) | Brute-Force   |   Shift
 00*00        |     19 TZ     |  208 TZ
 01*01        |     43 TZ     |  227 TZ   
 02*01        |     67 TZ     |  227 TZ   
 1F*01        |    763 TZ     |  303 TZ
 80*80        |   3091 TZ     |  227 TZ
 FF*FF        |   6139 TZ     |  360 TZ

Brute-Force TZ-Berechnung:
Läßt man den Sonderfall 0 mal außer Acht,
dann werden 20 + (MULTIPLIKATOR * 24) - 1 Taktzyklen benötigt.

Shift Berechnung:
Die Berechnung ist etwas aufwendiger, die Anzahl der Zyklen hängt von der 
Anzahl Nullen und Einsen im MULTIPLIKATOR ab.
25 + (0_BITs * 23) + (1_BITs * 42) - 1

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

DIV mit Shift & Rotate

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

Rechnen wir einfach:

%01111010 / %0011             (also 122 / 3)
%0        = %0                      1   = 0
%01       = %00                     12  = 04
%011      = %001                    002 = 040 
%0001     = %0010                   Rest: 2
%00011    = %00101
%000000   = %001010
%0000001  = %0010100
%00000010 = %00101000 
      Rest: %00000010

zur Übung nochmal:
 %10101010 / %1100            (also 170 / 12)
 %1        = %0                     1   = 0
 %10       = %00                    17  = 01
 %101      = %000                  -12 
 %1010     = %0000                 ===  
 %10101    = %00001                  50 = 014
-%01100                             Rest: 2
 ======                             
 %010010   = %000011                  
-%001100
 =======
 %0001101  = %0000111
-%0001100
 ========
 %00000010 = %00001110
       Rest: %00000010

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 das 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, dieses Mal sollten die Kommentare im Source als Erklärung reichen.

;*******************************************************************************
;*** 8-BIT Division durch Bitverschiebung
;*******************************************************************************
;*** Übergabe: ZP_DIVIDEND
;***           ZP_DIVISOR
;*******************************************************************************
;*** Rückgabe: ZP_ERGEBNIS (8-BIT)
;***           ZP_DIVIDEND (8-BIT) enthält den evtl. Rest
;*******************************************************************************
;*** ändert  : A, X, SR
;*******************************************************************************
!zone shift_div
shift_div
 lda #$00                       ;erstmal eine 0
 sta ZP_ERGEBNIS                ;ins Ergebnis
 sta ZP_HELP                    ;und in die Hilfsvariable
 lda ZP_DIVISOR                 ;prüfen ob durch 0 geteilt werden soll
 beq .exit                      ;falls ja -> .exit
 ldx #$08                       ;acht Schleifendurchläufe
.loop
 asl ZP_DIVIDEND                ;höchstes BIT ins Carry-Flag shiften
 rol ZP_HELP                    ;C-Flag ins niedrigste BIT rotieren 
 lda ZP_HELP                    ;ZP_HELP in den Akku
 cmp ZP_DIVISOR                 ;prüfen ob ZP_HELP größer/gleich Divisor
 bcc .skip                      ;falls nein -> weiter bei .skip
 sbc ZP_DIVISOR                 ;sonst Divisor vom Akku abziehen
 sta ZP_HELP                    ;Akku bei ZP_HELP speichern
.skip
 rol ZP_ERGEBNIS                ;C-Flag ins Ergebnis rotieren
 dex                            ;Schleifenzähler verringern
 bne .loop                      ;solange größer 0, nochmal -> .loop
.exit 
 lda ZP_ERGEBNIS                ;falls das Ergbnis 0 ist, enthält der Dividend
 beq .skip1                     ;den Rest, also -> RAUS
 lda ZP_HELP                    ;sonst das LSB der Hilfsvariablen in den
 sta ZP_DIVIDEND                ;Dividend kopieren
.skip1
 rts                            ;zurück zum Aufrufer

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

Wo ist eigentlich 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, das kann so nicht stimmen, richtig wäre 1. 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 0 mit dem Rest 1.

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:

 ;*******************************************************************************
;*** Vorzeichenbehaftete 8-BIT Multiplikation durch Bitverschiebung
;*******************************************************************************
;*** Übergabe: ZP_MULTIPLIKATOR
;***           ZP_MULTIPLIKANT
;*******************************************************************************
;*** Rückgabe: ZP_ERGEBNIS (16-BIT)
;*******************************************************************************
;*** ändert  : A, X, Y, SR
;*******************************************************************************
shift_mul_signed:
 ldy #$00                       ;im Y-Reg. merken obs Vorzeich umgekehrt werden muss
 bit ZP_MULTIPLIKATOR           ;Multiplikator negativ?
 bpl @skip:                     ;falls nicht -> @skip:
 ldx ZP_MULTIPLIKATOR           ;sonst den Multiplikator in eine
 dex                            ;positive Zahl umwandeln
 txa
 eor #%11111111
 sta ZP_MULTIPLIKATOR           ;und speichern
 iny                            ;Y erhöhen (wenn ungleich 0 Verzeichen verschieden)

@skip:
 bit ZP_MULTIPLIKANT            ;Multiplikant negativ?
 bpl @skip1:                    ;falls nicht -> @skip1:
 ldx ZP_MULTIPLIKANT            ;sonst wie eben Vorzeichen umkehren
 dex
 txa
 eor #%11111111
 sta ZP_MULTIPLIKANT            ;speichern
 dey                            ;und Y um eins verringern
                                ;war der Multiplikator auch negativ, dann hat
                                ;Y wieder den Wert 0 und wir brauchen das 
                                ;Ergebnis später nicht zu ändern.

@skip1:
 jsr shift_mul:                 ;'normale' MUL-Funktion starten
 cpy #$00                       ;falls Y 0 ist, bleibt das Vorzeichen erhalten
 beq @exit:                     ;dann raus -> @exit:
 lda ZP_ERGEBNIS+1              ;sonst das Vorzeichen vom Ergebnis ändern
 eor #%11111111
 sta ZP_ERGEBNIS+1

 lda ZP_ERGEBNIS
 eor #%11111111
 clc
 adc #$01
 sta ZP_ERGEBNIS
 lda ZP_ERGEBNIS+1
 adc #$00
 sta ZP_ERGEBNIS+1

@exit:
 rts                            ;zurück

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! (10 Bewertungen | Ø 4,40 von 5 | 88,00%)

Loading...


Zurück

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

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

Protected by WP Anti Spam