Brute-forcing 8-bit multiplication

As the 6502 does not have instructions for multiplication, if we want to do any multiplication then we need to write our own routine to multiply numbers. There is a very easy way to do this, but it is not efficient. Still, lets take a look at the obvious brute force method before working out a more efficient way of doing this.

In the discrete math courses I took, multiplication was defined as adding a number which is called the multiplicand by itself the number of times specified by another number which is called the multiplier. We have an add instruction and we have looping constructs to repeat the addition a number of times. To make this a proper function we need to have a way of getting information into the function and returning the results. In this case, we have two bytes so we will have the multiplicand in the accumulator and the multiplier in x returning the result in the accumulator.

The following code is a very rough way of doing this but is not what I would consider production code which would check for the 0 case, and would have a nicer loop. As I am planning on writing a better version, this will do for demonstration purposes.

; brute force 8-bit multiplication
JMP test
; create a placeholder for the multiplicand
multiplicandLo: 
.BYTE 0
;
; Multiply method A = multiplicand, X = multiplier result returned in A
multiply:
STA multiplicandLo
multiplyLoop:
DEX
BEQ multiplyDone
CLC
ADC multiplicand
JMP multiplyLoop
multiplyDone:
RTS

test:
; fourty-two test
LDA #7
LDX #6
JSR multiply
; 10*20 test
LDA #10
LDX #20
JSR multiply
BRK


The trace results shows us pretty much what we would expect. The first test does take a while to run as it starts at cycle 3 and returns at cycle 93 (the instruction after the RTS) giving us a 90 cycle run time.

(0) 0:JMP $12
(3) 12:LDA #$7 ' A: 0 -> 7
(5) 14:LDX #$6 ' X: 0 -> 6
(7) 16:JSR $4# 
(13) 4:STA $3# ' [3]: 0 -> 7
(17) 7:DEX ' X:6 -> 5
(19) 8:BEQ $11
(21) a:CLC 
(23) b:ADC $3 ' A: 7 -> $E
(27) e:JMP $7
(30) 7:DEX ' X: 5 -> 4
(32) 8:BEQ $11
(34) a:CLC
(36) b:ADC $3 ' A: $E -> $15
(40) e:JMP $7
...
Additional loops removed as you get the idea!
...
(75) b:ADC $3 ' A: $23 -> $2A
(79) e:JMP $7
(82) 7:DEX ' X: 1 -> 0; Z set
(84) 8:BEQ $11
(87) 11:RTS

A slightly larger 10 * 20 multiply, however, does not give us that good of results.

(93) 19:LDA #$A ' A: $2A -> $A 
(95) 1b:LDX #$14 ' X: 0 -> $14
(97) 1d:JSR $4
(103) 4:STA $3 ' [3] 7 -> $A
(107) 7:DEX ' X: $14 -> $13
(109) 8:BEQ $11
(111) a:CLC 
(113) b:ADC $3 ' A: $A -> $14
...
Additional loops removed as you get the idea!
...
(345) a:CLC
(347) b:ADC $3 ' A: $BE -> $C8
(351) e:JMP $7
(354) 7:DEX ' X: 1 -> 0; Z set
(356) 8:BEQ $11
(359) 11:RTS
(365) BRK

The time for this was 272 cycles which is tolerable but getting bad. For our random number generator we need to multiply by 141. This would result in 1845 cycles to perform the multiplication. Not a good result at all. Obviously we need to come up with a better way of handling multiplication. This will be covered next fortnight.