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. 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" 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 to try it out:

python simulator.py example_programs/multiply_shift.asm