• Introduction
• The Implementations
• The Results
• The Algorithms
  • Binary Multiplication (Shift and Add)
  • Modified Shift and Add
  • Tables of Squares
  • Logarithms
  • Four bit multiply
  • Booth's Algorithm
  • Hardware support
  • Repeated addition
• Customising
• How to run the tests

"The search for the ultimate multiply routine seems never-ending." - Brooke W. Boering (December 1980)

This document compares the runtime performance and memory used by a wide variety of general purpose multiplication routines for the 6502 CPU. Over 120 different routines have been exhaustively tested, cycle counted, and the results plotted.

There is no one 'best' routine or algorithm, because there are always trade-offs between speed and memory. By speed, I mean the average, best and worst cases of how many cycles are needed to perform the multiplication. By memory I mean the total number of bytes needed for the code itself and all necessary data tables.

There may be other gains based on the context in which it is being used, e.g. the memory cost can be shared if data tables can be reused by other routines (for example a square root or division routine). Perhaps the multiplicands are more likely to lie in a given range. So it is not possible to recommend a single routine as 'best'. What we can say is that some routines are almost always, or actually always, worse than others. In practice, only a few are worth considering.

The most common routines available are for unsigned numbers, either 8 bit x 8 bit with a 16 bit result, or 16 bit x 16 bit with a 32 bit result. These are the natural focus, however several other routines are listed further down. There is also a section later that discusses how to how to customise the routines, e.g. how to handle signed numbers, adjusting to different bit sizes, etc.

I have tested the following routines:

Specialised multiply routines often find their niche in games. Partial results (a result with fewer bits than expected) are common for fixed point arithmetic. Even approximate results can be used in cases where speed is more important than absolute accuracy.

In the diagrams below, grey dots are the also-rans. They are are beaten for both cycles and memory by the better orange dots.

Take note that the fastest routines vary largely in size, but with very little difference in cycle counts.

There's one trick however: if you are multiplying lots of numbers by the same multiplier then these routines can be optimised further. e.g. The largest (mult14) takes 45.99 cycles on average normally but takes just 27.99 cycles if the multiplier (in A) doesn't change between calls. This is because the first instructions of the routine are setup code based on the multiplier that takes 18 cycles. This only needs to be done once, leaving a faster multiply. This same trick can also be done for a smaller benefit (6 cycles) to mult66, mult27 and mult57.

To see the results of the smaller routines more clearly, here is a zoomed in view of the same results:

All cycle counts and byte counts include the final RTS (1 byte, 6 cycles), but do not include any initial JSR mult (3 bytes, 6 cycles).

To see the results of the smaller routines more clearly, here is a zoomed in view of the same results:

Here are some example signed multiply routines. The signed routines are usually just an unsigned routine with adjustments made before and/or after it. See below for how to adapt an unsigned multiply into a signed multiply routine.

Other miscellaneous multiply routines with something 'specialised' about it e.g. only returning an approximate result, or with different bit depths. A decent variable bit length multiply is available in omult23.a, but for other maths operations, see BBC Micro Machine Code Portfolio by Bruce Smith (1984).

This is the classic algorithm found in all good textbooks, similar to pen and paper 'long multiplication', but in base 2. A friendly introduction is found here. In short, one number is shifted left (doubled) each time around a loop, and the binary bits of the other number are used to determine whether to add this shifted number to a running total.

This is the method used by most programs that need multiplication. It has the advantage that the code is small and it performs reasonably well. Also known as Ancient Egyptian multiplication.

This is a clever variation of the standard shift and add algorithm that reduces the number of shifts required for a 16 bit multiply (and larger). In the standard algorithm each of the 16 loop iterations requires four byte shifts. In this variant each iteration only requires three shifts. This was found by Dr Jefyll in 2012, and is described here. The animated diagram is instructive.

By storing tables of square numbers, we can speed up multiplication. This uses:

$$ab = f(a+b) - f(a-b), where f(x) = \frac{x^2} {4}$$

So using two table lookups, an addition and two subtractions, we can multiply. This is faster than 'shift and add'. The downside is how much memory needed to store the data. For 8 bit multiplication, the amount of data varies depending on the exact implementation, but is either 2k of data (fastest), or 1k (only marginally slower), or 512 bytes (slightly slower again).

An added feature of the 1k and 2k routines particularly is that if many multiplications are being done with one of the inputs unchanging then some setup code can be skipped, for even better performance. For example if a number of points are being rotated by some known angle.

The data tables can be either loaded from storage, or initialised in code.

This is an approximation for multiplication. This uses:

$$log(ab) = log(a) + log(b)$$

By using a log and exponentiation tables, we can multiply using just three table lookups and one addition. This is fast.

However, since we are working with integers and not floating point, this is only an approximation. In particular, when multiplying 8 bit x 8 bit and returning an 8 bit (high byte) result only, this can give a reasonable approximation.

The method is described further here here. It has an implementation we look at next, and compare it with others:

This uses a 256 byte log table and a 511 byte antilog table (total: 767 bytes of data).

Note that its formula for the antilog table $y=2^{(x/f-8)}+.5$ should not have the $+.5$ as this makes the results less accurate. In particular, testing with $+.5$ over all 65536 possible inputs we get the following results:

Error: -5  count: 1
Error: -4  count: 32
Error: -3  count: 262
Error: -2  count: 1086
Error: -1  count: 3934
Error: 0  count: 26871
Error: 1  count: 28384
Error: 2  count: 3937
Error: 3  count: 833
Error: 4  count: 180
Error: 5  count: 16

Root-mean-square deviation: 257.06 (smaller is better)

which is more often wrong than it is right. Without the $+.5$ the code gives more accurate results:

Error: -5  count: 9
Error: -4  count: 93
Error: -3  count: 468
Error: -2  count: 2088
Error: -1  count: 10529
Error: 0  count: 41848
Error: 1  count: 8275
Error: 2  count: 1753
Error: 3  count: 411
Error: 4  count: 61
Error: 5  count: 1

Root-mean-square deviation: 211.64 (smaller is better)

The Master and Second Processor versions of Elite for the BBC Micro also use logarithms for approximating some 8 bit x 8 bit = 8 bit (high byte) multiplications (see here).

The BBC Master and Apple II versions of Elite have identical routines with two log tables and an antilog table (total: 768 bytes of data) for a version that is wrong by no more than six:

Error -6: 10
Error -5: 119
Error -4: 626
Error -3: 2590
Error -2: 7082
Error -1: 20656
Error 0: 34451
Error 1: 2

Root-mean-square deviation: 292.66 (smaller is better)

The Second Processor version of Elite has a more accurate version using an extra antilog table (total: 1024 bytes of data), for a version that is wrong by no more than three:

Error -3: 90
Error -2: 1981
Error -1: 19356
Error 0: 44109

Root-mean-square deviation: 167.60 (smaller is better)

The same log and antilog tables can be used to implement an approximate division.

If division is not needed however, then a table of squares method can be used (total: 512 bytes of data), and assuming (as with log based methods above) only the high byte of the product is required, the code for the low byte can be removed, for a version that is wrong by no more than one:

Error -1: 4707
Error 0: 43681
Error 1: 17148
Root-mean-square deviation: 147.83 (smaller is better)

The table has been biased by '-0.74' by manual experimentation to minimize the root mean square deviation.

Instead of 'binary multiplication' using base 2 (as described above), we use base 16 (hexadecimal). We use a 256 byte table that stores the result of multiplying two 4 bit numbers together.

To get an 8 bit x 8 bit multiply, we think of our two 8 bit numbers as being two pairs of hex digits AB and CD. We multiply each pair of hex digits together using the lookup table, and add them together as shown below. This is the same method as regular pen and paper 'long multiplication':

        AB
       *CD
      ----
        xx      (B*D)+
       xx0      (A*D*16)+
       xx0      (B*C*16)+
      xx00      (A*C*256)

This algorithm is not the fastest, it's nearly 2 times slower than a regular shift and add.

Aviator for the BBC Micro uses this method (see here).

The classic shift and add algorithm can sometimes end up doing a lot of addition. For instance multiplying by 15 involves four additions since 15 = 1+2+4+8, corresponding to a run of set bits in the multiplier. It would be quicker to multiply by 16 and subtract the original number.

Booth's Algorithm tracks when successive bits of the multiplier change and either adds or subtracts the other number from the total as needed.

Unusually, this method is designed for signed numbers, not unsigned.

This method turns out to be ~2.7 times slower on the 6502 than an equivalent 'shift-and-add' routine, so doesn't seem to be used much in practice. It's used more in designing hardware circuits.

Further explanation of Booth's algorithm here.

Some hardware has multiplication support in silicon. These are likely to be fastest where available. For instance, the SNES CPU with its extended 6502 instruction set has hardware for (1) 'unsigned 8 bit x 8 bit = 16 bit' (set registers, wait 8 cycles, then read results) and (2) 'signed 16 bit x 8 bit = 24 bit' (set registers, wait 16 cycles, then read results).

Some early vector based arcade machines like Tempest and Battlezone were programmed in 6502, with an external processor (Atari's Math Box) to handle the vector maths, including multiplication.

To multiply m*n, just add m, n times. This is stupidly slow for anything that isn't very small in n, so avoid in general. With 8 bit multiply, if I show them with all the others, the graph looks like this:

Only one (mult72, being smallest) is just worthy of an orange dot, in the unlikely scenario that you can afford 16 bytes but not 17:

The booby prize for the slowest multiply goes to mult70 at nearly 2000 cycles average.

So it's better generally to use binary multiplication instead (e.g. mult9 or mult11 are 17 bytes). However, for multiplying by small numbers (between 0 and 24), mult72 is more efficient than mult9.

The most common routines I've found either multiply two 8 bit values to get a 16 bit result, or multiply two 16 bit values to get a 32 bit result.

These are useful, but in practice what you may need is something different, something custom made. For example you may need to multiply a 24 bit number by an 8 bit number, scaling the result down by 256 to get a new 24 bit number.

The shift-and-add method is straightforward to extend to larger the number of bits, since the principles are the same no matter how many bits are used. An m-bit by n-bit multiply needs a result of m+n bits.

It also helps to realise that you can make these routines by building on your favourite standard 8 bit x 8 bit = 16 bit routine.

Just as binary multiplication works in base 2, this works in base 256. Each byte is one digit. For example, to make a 16 x 16 bit multiply:

        AB
       *CD
      ----
        xx      (B*D)+
       xx0      (A*D*256)+
       xx0      (B*C*256)+
      xx00      (A*C*256*256)

Adding the four partial results as shown.

Routines can take input values either from registers or from memory. It can also return results in registers and/or memory.

The 8 bit routines I have presented here will generally use whichever parameter method is fastest.

However, the calling code may want to use registers for the parameters for the multiply for both input and output as this is often most efficient. You may want to adjust the in/out parameters of the routine depending on your usage.

In particular, if on exiting the routine the low byte of the result is in A, then it can be used as the starting point for a subsequent add or subtract, as used when combining to make a larger bit multiply. Sometimes carry is guaranteed clear after the multiply which also helps with optimising a subsequent addition.

These routines mostly use memory locations for in/out parameters, as there are too many values to hold in the registers.

For speed, some routines only provide a partial answer. e.g. it may return only the high byte of the result (as an approximation, often used with fixed point calculations) or the low byte (for multiplying small numbers that don't lead to results larger than one byte).

For example, if a routine wants to multiply a 16 bit number by the sine of an angle this is a problem for an integer routine since the sine of an angle is a floating point number not an integer. By scaling up the fractional value to an integer e.g. N=256*sin(angle), then the integer multiplication by N can happen and the result scaled down by 256. Note also that negative numbers will need special treatment:

Two's complement representation is most commonly used to represent signed numbers. Occasionally routines use a sign-magnitude representation (e.g. omult4.a), but I will assume here the standard two's complement representation is used.

There are two methods of dealing with multiplying signed numbers; one obvious, the other less obvious but faster. The more obvious method is:

1. remember if the sign of the two input numbers differ
2. remove the sign of each input value (abs)
3. do a regular unsigned multiply
4. recall if the signs differ and negate the result if needed

The faster, craftier method is:

1. do a regular unsigned multiply
2. If the first input is negative, subtract the second input from the high byte(s) of the result.
3. If the second input is negative, subtract the first input from the high byte(s) of the result.

This takes less memory and fewer cycles than the more obvious method. See C=Hacking16 for more details.

Caveat: If you are using a shift-and-add (or modified shift-and-add) then a small negative number like -1 will have lots of bits set, meaning lots of adds occur in the unsigned multiply. But it works well for table-of-squares routines.

The code to do this can be optimised to be quite small. For instance smult1.a has:

    ; Step 1: Unsigned multiply
    ;     <do an unsigned multiply here>
    ; Suppose at this point:
    ;     X=one of the original input numbers
    ;     A=high byte of result
    ;     Y=low byte of result

    ; Step 2: apply sign.
    cpx #$80             ; check the sign of one input              2 cycles
    bcc +                ; branch if positive.                      2/3/4
    sbc sm1              ; take off the other input.                3
+
    bit sm1              ; check the sign with of the other input.  3
    bpl +                ; branch if positive.                      2/3/4
    stx temp             ; store the amount to subtract.            4
    sec                  ; prepare carry for subtract.              2
temp = * + 1
    sbc #0               ; subtract (self modifying code).          2
+

Corollary: For an 8 bit x 8 bit multiply where only the low 8 bits of the result are required, there is no difference between the unsigned and signed result, the same answer works for both. For a 16 bit x 16 bit multiply where only the lower 16 bits are required, the same is true.

If not running from ROM, self-modifying code can be used to optimise for speed. The table of squares routines often do this, for example. Implementations that use the shift-and-add algorithm will often add the multiplicand in a single location in the loop. It may be possible to replace these 'adc multiplicand' and 'adc multiplicand+1' instructions with immediate versions 'adc #0' and write the multiplicand into the adc operands directly from the caller code.

If using self-modifying code, putting the code itself in zero page can make it run a little faster, if you have the space!

This can be done, but not very efficiently. Here is an implementation that uses the 'Russian peasant multiplication'. There is discussion of various methods on the 6502.org forum. A multibyte BCD multiply (for numbers up to 255 bytes long!) is in 6502 Assembly Language Routines.

• I use the MOS Technology 6502 CPU Emulator to emulate the 6502.
• I use the Z header only library as it is required by the emulator.
• I use the libpng library to plot the log error images.
• I use matplotlib python library to plot the graphs.
• I use the acme assembler.
• I use clang to compile the C code.
• I use python3 to create the graphs.

• I'm set up for macOS. The 'go' script specifies which tests to execute. Uncomment the test(s) you want to run. Run the 'go' script to execute the tests.
• The 'tests' folder contains a number of 6502 assembly language files ('.a' files) to test.
• The testing is configured by a small associated '.c' file.
• The test results are written to the results/ folder.
• Tests can be executed on multiple threads for speed. Adjust this in the go script: -n<number> on the command line for the tester program specifies the number of threads.
• The 'go_plot' script is used to create the graphs from the results as svg files.

• The assembly language code is assembled into a binary file using the acme assembler.
• The tester C code is compiled (using clang) along with the test parameters '.c' file.
• The 6502 binary is loaded and executed (simulated) multiple times, over all possible inputs (specified by the test's '.c' file).
• Any unexpected results (e.g. due to errors in the algorithm or the test) are reported. The test case that failed is re-run with a full disassembly output to aid debugging.
• The average cycle count is reported and results are output to a json file.

See also my sqrt_test repository for comparing implementations of square root.