Classic Computer Magazine Archive COMPUTE! ISSUE 57 / FEBRUARY 1985 / PAGE 121
MACHINE LANGUAGE
Jim Butterfieild Associate Editor

Multiplication
Part 2

In Part 1, we discussed a multiplication such as:

(X)      1 1 0 1 0
(y)          1 0 1
         1 1 0 1 0
       0 0 0 0 0
     1 1 0 1 0    
(z)1 0 0 0 0 0 1 0

    We indicated that the logic might most usefully work this way:
  1. Set the product area (z) to zero.
  2. Examine the highest bit of the multiplier (y).
  3. If the bit is 1, add the multiplicand (x) into the product (z).
  4. If the multiplier (y) has no more bits, quit.
  5. Shift the product (z) left one bit.
  6. Examine the next highest bit of the multiplier, and go to step 3.
    Thus, we start with 11010, shift left to get 110100, add nothing, shift left to get 1101000, add 11010 to give 10000010, then quit. Answer: 10000010, or hex 82, or decimal 130.

Working Another Shift
That's not hard to do, but we have one more trick in our bag. Notice that the product is shifted left. We could test the bits of the multiplier (y) if we shifted it left, too. The highest bits would pop into the carry flag as we shifted, and we could test each bit with a BCC or BCS as it goes by.
    Now-and this is the neat part-if we need to shift both the product and the multiplier left, maybe we could put them together and shift them as one large collection of bits. We can see this best graphically:

  00000101 00000000
Multiplier Product

    We'll shift these two as if they were one value. Whenever a bit hits the carry flag, we'll add 11010 (our multiplicand) into the product area. Nothing much will happen at first, since as we shift the two-byte group left, zeros will move into the carry and we won't add a thing. After five shifts, we have:

10100000 00000000

    We still have nothing in our carry flag. But one more long shift, and the high bit will move into the carry:

C 01000000 00000000

    Good! Add the multiplicand into the product, area (using a full two-byte addition), and we'll get:

01000000 00011010

    The next two left-shifts yield the following values:

      10000000 00110100
and C 00000000 01101000

    Aha! The carry bit has been hit again, so we add 11010 into the product area to get:

00000000 10000010

    That's our answer! Correct in both bytes! We know to stop at this point because if we count the shifts we find that we've done eight-exactly the number of bits in the multiplier.

Taking A Bigger Byte
The elegant thing about this kind of multiplication is that the answer is correct over several bytes. For example, if you multiply a one-byte number by another one-byte number, the product may be up to two bytes in length. Our previous example was a simple one: 5 times 26 gives 130, which still fits into one byte. But if we try, say, 48 times 40, we'll need a two-byte area for the answer. Without special comment, let's do it using the same method:

  00101000 00000000
  01010000 00000000
  10100000 00000000
C 01000000 00110000
  10000000 01100000
C 00000000 11110000
  00000001 11100000
  00000011 11000000
  00000111 10000000

    Answer: hex 780, or decimal 1920. Correct in both bytes.
    Let's write the code to multiply a number in the A register with one in the X register and place the result in address $0380 (low) and $0381 (high). We'll use $0382 as storage for the multiplicand.

       STX  $0382  ;multiplicand
       STA  $0381  ;multiplier
       LDA  #$00
       STA  $0380  ;zero to product
       LDX  #$08   ;number of bits
NXBIT  ASL  $0380
       ROL  $0381
       BCC  NOADD
       CLC
       LDA  $0381
       ADC  $0382
       STA  $0381
       LDA  $0380
       ADC  #$00
       STA  $0380
NOADD  DEX
       BNE  NXBIT

    It's elegant, it's efficient, and it easily extends to a greater number of bytes for the multiplier and multiplicand.