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

Question

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.

Answer 1

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.
            30B9    ADD HL,DE       Otherwise add DE in once.
            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.

Answer 2

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
   adc  0x70
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.

Answer 3

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.

Answer 4

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)
            res = add32 (res, a);
        a <<= 1;
        b >>= 1;
    }
    return res;
}