19

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.

  • 9
    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. – Martin Maly Mar 14 at 13:25
  • 4
    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. – Raffzahn Mar 14 at 13:53
  • 3
    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... :-) – Bob Jarvis - Reinstate Monica Mar 15 at 2:32
  • 6
    @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. – Ross Ridge Mar 15 at 11:48
  • 3
    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. – scruss Mar 15 at 17:00
18

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.

| improve this answer | |
  • 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. – Mark Williams Mar 14 at 16:49
  • 5
    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. – Mark Williams Mar 14 at 21:03
  • 2
    I was typing pretty rapidly on a phone - I almost certainly misread or made a mistake :) – user16540 Mar 15 at 13:30
  • 1
    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. – Unslander Monica Mar 15 at 17:16
  • 2
    @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. – supercat May 5 at 21:24
16

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.

| improve this answer | |
  • 3
    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. – Guntram Blohm Mar 16 at 9:52
10

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.

| improve this answer | |
2

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;
}
| improve this answer | |
  • Thanks for the routines, but that's kind of obvious. I was more interested in the actual assembly routines in BASIC and how it might be optimised for speed and size. – Mark Williams Sep 30 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.