Jim Butterfieild Associate Editor

Multiplication

Part 2

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:

- Set the product area (z) to zero.
- Examine the highest bit of the multiplier (y).
- If the bit is 1, add the multiplicand (x) into the product (z).
- If the multiplier (y) has no more bits, quit.
- Shift the product (z) left one bit.
- Examine the next highest bit of the multiplier, and go to step 3.

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

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

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.