# How did integer multiplication work in 8-bit BASIC without CPU support

I've recently been teaching my 11 year old binary multiplication, which is on the UK maths syllabus at secondary school. We have used long multiplication, eg shift and add.

This has made me wonder about the Z80, which didn't have an integer multiply operation.

How was integer multiply performed my Z80 BASIC, eg Locomotive or Sinclair? Was it done by shifting the multiplicand by each bit of the multiplier and adding, or by repeated addition of the larger number? Was it optimised for efficiency or size?

I ask about Z80 for simplicity, but if you know more about 8080 or 6502, I imagine there were similar strategies.

Feel free to post code samples from BASIC languages of the time.

• Shift and add is widely used for multiplication because it is fast and efficient algorithm. Repeated addition can take an excessive amount of time in the case of two big multiplicands. Commented Mar 14, 2020 at 13:25
• It might be important to notice that for (most/all) MS-BASIC integer multiplication was done by turning integers into float first, then multiply and convert back to integer. Commented Mar 14, 2020 at 13:53
• Multiplication is simply repeated addition. The problem with humans using this method is that humans are remarkably slow, and prone to errors when performing the same operation over and over and over. Computers, on the other hand... :-) Commented Mar 15, 2020 at 2:32
• @BobJarvis-ReinstateMonica While computers wouldn't make mistakes performing naive repeated addition, it was way too slow to ever actually be used in any BASIC implementation.
– user722
Commented Mar 15, 2020 at 11:48
• Locomotive BASIC doesn't seem to have an integer multiplication routine. I couldn't find anything in the disassembly apart from float. From Raffzahn's suggestion and some timing tests, it seems to convert to float, multiply, and convert back. Commented Mar 15, 2020 at 17:00

For Spectrum BASIC, the routine for Small Integers (16 bit) can be seen on page 179 of the Complete ZX Spectrum ROM Disassembly, where it loops over the sixteen bits of one operand, shifting them into the carry bit, adding successively doubling values to the result value each time the test passes, and testing for overflow if the result doesn't fit in a small integer.

``````Input
DE  First number (M)
HL  Second number (N)
Output
HL  M*N
HL_HLxDE    30A9    PUSH BC         BC is saved.
30AA    LD B,\$10        It is to be a 16-bit multiplication.
30AC    LD A,H          A holds the high byte.
30AD    LD C,L          C holds the low byte.
30AE    LD HL,\$0000     Initialise the result to zero.
HL_LOOP     30B1    ADD HL,HL       Double the result.
30B2    JR C,HL_END     Jump if overflow.
30B4    RL C            Rotate bit 7 of C into the carry.
30B6    RLA             Rotate the carry bit into bit 0 and bit 7 into the carry flag.
30B7    JR NC,HL_AGAIN  Jump if the carry flag is reset.
30BA    JR C,HL_END     Jump if overflow.
HL_AGAIN    30BC    DJNZ HL_LOOP    Repeat until 16 passes have been made.
HL_END      30BE    POP BC          Restore BC.
30BF    RET             Finished.
``````

For larger floating point numbers (which the result is promoted to if the multiplication result overflows a small integer, or if either operand is already floating point), the full five byte floating point multiplication routine follows on page 180.

• Are you sure? The linked code looks like it works in the other direction , doubling the result each loop and adding the multiplicand each time a bit in the multiplier is set. Commented Mar 14, 2020 at 16:49
• No, I only copied and pasted the code that @user16540 linked to in order to make the answer easier to read. I haven't added any information. Commented Mar 14, 2020 at 21:03
• I was typing pretty rapidly on a phone - I almost certainly misread or made a mistake :) Commented Mar 15, 2020 at 13:30
• Side note: it'd be interesting to see how much faster this code could be were it to be unrolled - it wasn't feasible when ROM space was at a premium, and many BASIC ROMs had at most tens-hundreds of bytes to spare. And then see if the unrolled code could be made even faster using the Karatsuba algorithm. Commented Mar 15, 2020 at 17:16
• @ReinstateMonica: If code doesn't have to behave meaningfully in case of overflow, the main iterated sequence for multiplying H by DE, if L is initialized to zero, may be simplified to eight reps of `add hl,hl / jr nc,*+3 / add hl,de`. Unrolling all eight reps would be 32 bytes, but adding `mov b,2` and `djnz ...` and unrolling 4x would offer much of the speedup, at a cost of 20 bytes. Commented May 5, 2020 at 21:24

Multiplying (and dividing) by powers of 2 has always been trivial and fast even for 8-bit processors like Z80 or 6502, with shifting instructions (commonly arithmetic shift left aka `ASL`).

But those processors didn't have a `MUL` instruction so when it came to non-power of 2 multiplication, it always involved shifting, testing bit and adding shifted result if bit is set, exactly like we do manually in base 10, if I may say.

So in the ROM, when one piece of coded needed to multiply by 2 or 4 or whatever, it used explicit `ASL`, `ROL` or whatever shifting instruction available, even when a generic shift-and-add multiply routine was available.

Sometimes when the number to multiply with was known, a special routine was used, like in the oric atmos ROM, when the ROM needed to multiply by 40 which is the number of bytes per row.

``````F731    A0 00       LDY #\$00         This routine multiplies the
F733    8C 63 02    STY \$0263        content of the accumulator by
F736    8D 64 02    STA \$0264        #28 (40). Y holds the high
F739    0A          ASL A            byte of the result. The page
F73A    2E 63 02    ROL \$0263        2 locations store temporary
F73D    0A          ASL A            results.
F73E    2E 63 02    ROL \$0263
F741    18          CLC
F742    6D 64 02    ADC \$0264        The result is calculated by
F745    90 03       BCC \$F74A        adding 4 x A to A and then
F747    EE 63 02    INC \$0263        double the result.
F74A    0A          ASL A
F74B    2E 63 02    ROL \$0263
F74E    0A          ASL A
F74F    2E 63 02    ROL \$0263
F752    0A          ASL A
F753    2E 63 02    ROL \$0263
F756    AC 63 02    LDY \$0263
F759    60          RTS
``````

For other cases, it used the generic multiply routine. As you see, multiplying by a known number such as 40 is already a long, time consuming routine. The generic integer routine takes even more cycles.

Games didn't call ROM multiply directly but often defined their own when they needed it, with the same principle. L'Aigle d'Or (1984) has one for instance. When I converted the game to C, I "optimized" it by using multiplication. You can see the C & asm equivalent below

C version: performs (0x70)*(0x71), returns result in r.a,r.y

``````  label_multiply_3E00:
{
int a=m[0x70];
int b=m[0x71];
int c=a*b;
r.a = c >> 8;
r.y = c & 0xFF;
rts;
}
``````

original asm 6502 code, same interface, returns result in A, Y

``````   lda #0
sta 0x72
ldx #8
label_0x3E06:
lsr 0x71
bcc  0x3E0D
clc   ; clear carry
label_0x3E0D:
ror A
ror 0x72
dex
bne label_0x3E06
sta 0x73
ldy 0x72
rts
``````

A 8/16 bit developper (I think it was Simon Phipps) once said how much he was relieved when working on 16 bit processors because of the multiply and divide native instructions.

To be perfectly honest and transparent, I didn't find the generic integer multiply routine in the Oric ROM and I'm not going to find it since it probably only exists as floating point (that one can be found). This follow-up question Is integer arithmetic really slower than float with (early) MS-BASIC? is the reason for that final edit.

• Fun fact - even as late as ~ 1995, when the i386 had a MUL instruction, the watcom C compiler produced the same kind of shift/add sequences for multiplication with constants as that was much faster than the, quite slow at that time, processor MUL. Commented Mar 16, 2020 at 9:52

The most common way to do a general multiplication is the "shift and add" method, where for each bit set in the multiplier you add the multiplicand to the high portion of the result and then shift the result right. Thus, the lowest order bit of the multiplier, if set, contributes 1× the multiplicand to the result after the result has been fully shifted right, the next bit of the multiplier contributes 2× the multiplicand (if set), and so on.

Lance Leventhal's 6502 Assembly Language Subroutines includes, on page 236, a 16-bit multiply routine that does this. Probably the most important thing to understand while reading this is that on the 6502 the `ROR` (rotate right) instruction shifts the lowest-order bit into the carry flag, and the carry flag into the highest order bit. Thus, the `BCC` (branch on carry clear) instruction determines whether the multiplier bit currently being processed requires the multiplicand to be added to the result.

The routine is also perhaps a bit overly clever in that as it shifts the 16-bit multiplier out, it shifts the low order bits of the result into the same memory locations.

There are specific optimizations to this algorithm that are frequently used. One is to examine both the multiplier and the multiplicand, reverse the two if the multiplicand's higest set bit is lower than the multiplier's, and then not loop through all the bits but only up to the highest set one.

Another, specifically for multiplication by ten, is to shift once to multiply by two, store a copy, shift twice more to continue to a multiplication by eight, and then add the two results together. An example in 6502 assembly for 8-bit values is given here and should be very clear to read; a more complex example for arbitrary-precision values (up to 255 bytes) is here. (Check the comments above the routine to understand the parameters.) This idea can be appropriately modified for other multiplications by a known constant.

Just for completeness, these two C functions demonstrate that you actually only need your CPU to implement logic operations (AND, OR, XOR, SHIFT) and one kind of test: test if a given number is equal or different to zero, in order to implement integer addition and multiplication. All these operations are very easy to implement in hardware.

NOTE: I assume that `sizeof(unsigned int)` is 4

``````unsigned int add32 (unsigned int a, unsigned int b)
{
unsigned int res, carry = 0;

res = a;
do
{
carry = (res & b)<<1;
res ^= b;
b = carry;
} while (carry != 0);
return res;
}

unsigned int mult32 (unsigned int a, unsigned int b)
{
unsigned int res = 0;
while (b != 0)
{
if (b & 1)