owned this note
owned this note
Published
Linked with GitHub
# Efficient multiplication using left-shift on Ben Eater's 8-bit breadboard computer
###### tags: `8bit`
This code and an emulator to run it can be found at: https://github.com/wmvanvliet/8bit
## Slow multiplication
In one of his video's, Ben Eater showed us [a program to multiply two numbers](https://youtu.be/Zg1NdPKoosU?t=1971).
In short, to multiply $x$ by $y$, you would add $x$ to the result $y$ times, using a loop:
```
;
; Multiply two numbers using a loop (Ben Eater's design)
;
loop: lda prod
add x
sta prod
lda y
sub one
jz end
sta y
jmp loop
end: lda prod
out
hlt
one: db 1
x: db 5
y: db 7
prod: db 0
```
If we were to compute $17 \times 15$ in this manner, the loop would iterate 15 times.
Can we do better?
## A better multiplication algorithm
Computer science text-books will tell you that multiplication is usually performed using a ["shift and add"](https://en.wikipedia.org/wiki/Multiplication_algorithm#Usage_in_computers) algorithm, which is the binary version of the "long multiplication" method of multiplying you may have learned in elementary school.
This is how one would compute $17 \times 15$ in binary using this method:
```
00010001
00001111
------------------- x
00010001
00010001
00010001
00010001
00000000
00000000
00000000
00000000
------------------- +
000000011111111
```
At least, that is how we were taught in Dutch elementary schools: multiply with the least significant digit first.
According to Wikipedia, in German schools, they multiply using the most significant digit first:
```
00010001 x 00001111
-------------------
00000000
00000000
00000000
00000000
00010001
00010001
00010001
00010001
------------------ +
000000011111111
```
As it turns out, the German method is more suited to our computer architecture, so we'll be using that.
At any rate, this method is much faster, as it always loops 8 times (given our 8-bit numbers).
As the multiplication examples show, during an iteration of the loop, we only do three things with the binary numbers:
1. left-shifting the intermediate result
2. determining whether the next most-significant bit of $y$ is a 1 or 0
3. adding $x$ to the intermediate result if it was a 1
Our computer can do all of those things!
## Left-shift without a left-shift instruction
But Marijn, we don't have a left-shift instruction!
Oh, but we do. Sort of. A number added to itself will left-shift that number:
```
10011101
10011101
---------- +
1 00111010 (carry flag is set)
```
Easy enough to create a left-shift instruction by modifying the microcode, but even in the original architecture, we can left-shift a number at a memory location like this:
```
lda x ; load memory contents at address 'x' into A
add x ; add memory contents at address 'x' to A
sta x ; store A into memory at address 'x'
x: db 157 ; store a literal '157' at this address
```
## Writing a fast multiplication program
When we left-shift a number, the carry-flag will tell us whether we just shifted a 1 or 0 out of the register, so we can use the `jc` instruction to either add $x$ to the intermediate result or not.
Here's what I came up with, given the 16-bytes of memory that we have.
There's not enough room for a counter to properly terminate the program after 8 iterations, so we'll just keep on running, but the output will keep displaying the proper result:
```
;
; Multiply two numbers (x and y) using left-shift
;
loop: lda y ; Step 1: look at the most-significant bit of y
add y ; Left-shift y, sets the carry flag if MSB was a 1
sta y ; Store y with the MSB removed
lda prod ; Load intermediate result (the product)
jc add_x ; Step 2: If the MSB was a 1, add x to the intermediate result
jmp shift_result ; Else skip over the adding part
add_x: add x ; Add x to the intermediate result
out ; Output our intermediate result
shift_result:
sta prod ; Step 3: Left-shift intermediate result
add prod ;
sta prod ;
jmp loop ; Next iteration
x: db 17 ; We are computing 17 x 15
y: db 15 ;
prod: db 0 ; The (intermediate) result is stored here
```
If you have Python installed, you can [download the code and an emulator](https://github.com/wmvanvliet/8bit) to try it out:
```
python simulator.py example_programs/multiply_shift.asm
```