"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:
| Source code | Bits | Method | From |
|---|---|---|---|
| smult1.a | 8x8=16 (signed) | tables of squares | Jackasser at codebase64 (2015) |
| smult2.a | 8x8=16 (signed) | Booth's algorithm | Marcus Thill (2017) |
| smult3.a | 16x16=32 (signed) | tables of squares | Jackasser at codebase64 (2015) |
| smult4.a | 8x8=16 (signed) | shift and add | Neil Parker (2005) |
| smult5.a | 8x8=16 (signed) | shift and add | mult9 converted to signed multiply by TobyLobster (2022) |
| smult6.a | 8x8=16 (signed) | shift and add | EDN magazine (5th Sept 1979), article by Arch D Robison |
| smult7.a | 8x8=16 (signed) | tables of squares | Oswald/Resource at codebase64 (2015) |
| smult8.a | 8x8=16 (signed) | tables of squares | mult65 converted to signed multiply by TobyLobster (2022) |
| smult9.a | 16x16=32 (signed) | modified shift and add | Dr Jefyll (2012) with modifications by TobyLobster (2023) |
| smult10.a | 8x8=16 (signed) | tables of squares | Piotr Fusik in the short lived Polish Atari disk magazine Syzygy, issue 6 (1999), see English version here |
| smult11.a | 8x8=16 (signed) | tables of squares | variant of Piotr Fusik in Syzygy 6 (1999) |
| smult12.a | 16x16=32 (signed) | tables of squares | Similar to smult3, but using the faster mult86 unsigned multiply routine as a base |
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.
| Source code | Bits | Method | From |
|---|---|---|---|
| omult1.a | 16x16=16 (partial result,low 16 bits only) | shift and add | Programming the 65816 by David Eyes (1986) |
| omult2.a | 8x8=8 (partial result, low byte only) | shift and add | The BBC Micro Compendium by Jeremy Ruston (1983), also Nightshade (1985) at $6121 |
| omult3.a | 8x8=8 (partial result, high byte only) | shift and add | Elite for the BBC Micro (1984) |
| omult4.a | 24x8=32 (sign-magnitude numbers) | shift and add | Elite for the BBC Micro (1984) |
| omult5.a | 16x16=16 (approximate 2 high bytes only) | shift and add | The Sentinel for the BBC Micro (1988) |
| omult6.a | 16x16=16 (low 16 bit result, or carry set if overflow occurs) | shift and add | The Commodore 64 BASIC/KERNAL ROM at $b357 and Applesoft II BASIC at $e2b8 |
| omult7.a | 8x8=8 (partial result, approx high byte) | log and exp tables | Elite, BBC Master version (1986) and APPLE II Elite (1985) |
| omult8.a | 8x8=8 (partial result, approx high byte) | log and exp tables | Elite, Second Processor version (1985) |
| omult9.a | 8x8=8 (partial result, approx high byte) | log and exp tables | from articles by Gunnar 'Krill' Ruthenburg / Plush in the German GO64! magazine (2000), via codebase64 |
| omult10.a | 16x32=32 (partial result,low 32 bits only) | shift and add | BBC BASIC ROM integer multiply code (1981) |
| omult11.a | 8x8=8 (partial result, high byte only) | tables of squares | mult13 reduced to return high byte only by TobyLobster (2023) |
| omult12.a | 8x8=8 (partial result, low byte only) | shift and add | Gateway to Apshai, for the Atari 8-bit family (1983) |
| omult13.a | 16x8=16 (partial result, div 128) | shift and add | Stellar 7, for the Apple II (1983) |
| omult14.a | 16x16=16 (partial result,low 16 bits only) | shift and add | FastBasic BASIC interpreter for the Atari 8-bit computers (2017) |
| omult15.a | 16x16=16 (partial result,low 16 bits only) | modified shift and add | Dr Jefyll (2012) with modifications by TobyLobster (2023) |
| omult16.a | 16x16=16 (partial result,low 16 bits only) | tables of squares | BBC BASIC ROM multidimensional array access code (1981) |
| omult17.a | 16x8=16 (partial result,low 16 bits only) | shift and add | How to program microcomputers by William T Barden (1977) |
| omult18.a | mxn=n+m (variable size multiply) | shift and add | Microcomputing magazine (June 1981) article by Leo J Scanlon |
| omult19.a | 24x24=48 | shift and add | Graphics Extension ROM by Acornsoft (1985) at $beb5 |
| omult20.a | 32x32=64 | shift and add | 6502.org based on 6502 Software Design by Leo J Scanlon (1980), expanded by Greg (1999) |
| omult21.a | 24x24=48 | modified shift and add | Dr Jefyll (2012) with modifications and expanded to 24 bit by TobyLobster (2023) |
| omult22.a | 32x32=64 | modified shift and add | Dr Jefyll (2012) with modifications and expanded to 32 bit by TobyLobster (2023) |
| omult23.a | mxn=n+m (variable size multiply) | modified shift and add | Dr Jefyll (2012) with modifications and generalised to mxn by TobyLobster (2023) |
| omult24.a | 24x24=24 | shift and add | Neils at codebase64 (2018) |
| omult25.a | 3x8=8 (partial result, high 8 bits only) | shift and add | Starship Command at $1e69 (1983) |
| omult26.a | 8x8=8 (partial result, high 8 bits only) | shift and add | Starship Command at $0fc3 (1983) |
| omult27.a | 16x8=16 (partial result, high 16 bits only) | shift and add | Starship Command at $0fa8 and $10be (1983) |
| omult28.a | 24x8=24 (partial result, high 24 bits only) | shift and add | Starship Command at $1095 (1983) |
| omult29.a | 16x8=16 (partial result, low 16 bits only) | shift and add | Splitting the Atom (The Acorn Recommended Advanced User Guide) by J.R. Stevenson and John C. Rockett (early 1980s) |
| omult30.a | 24x8=24 (partial result, high 24 bits only) | shift and add | TobyLobster (2023) |
| omult31.a | 24x8=24 (partial result, high 24 bits only) | tables of squares | TobyLobster (2023) |
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).
| Source code | Average Cycles | Memory (bytes) | My Changes |
|---|---|---|---|
| mult5.a | 92.01 | 834 | |
| mult6.a | 137.21 | 620 | |
| mult7.a | 133.53 | 36 | with slight change to swap output parameters |
| mult8.a | 153.45 | 29 | |
| mult9.a | 162.00 | 17 | |
| mult10.a | 221.08 | 27 | |
| mult11.a | 162.00 | 17 | |
| mult12.a | 108.64 | 71 | slightly tweaked |
| mult13.a | 54.00 | 1075 | |
| mult14.a | 45.99 | 2077 | |
| mult16.a | 67.48 | 574 | |
| mult17.a | 150.47 | 28 | tweaked to handle X=0 on input |
| mult18.a | 111.62 | 73 | tweaked to handle X=0 on input and unrolled |
| mult19.a | 185.00 | 18 | |
| mult20.a | 244.00 | 27 | bug fixed |
| mult21.a | 150.00 | 18 | |
| mult22.a | 74.48 | 562 | |
| mult23.a | 153.00 | 21 | |
| mult24.a | 110.63 | 70 | slightly tweaked |
| mult25.a | 243.00 | 28 | bug fixed, tweaked parameter passing |
| mult26.a | 278.14 | 47 | bug fixed |
| mult27.a | 51.49 | 1316 | slightly tweaked |
| mult28.a | 130.00 | 27 | tweaked |
| mult29.a | 120.00 | 43 | tweaked |
| mult30.a | 114.00 | 74 | tweaked |
| mult32.a | 117.14 | 592 | |
| mult34.a | 280.00 | 36 | |
| mult35.a | 188.00 | 20 | |
| mult37.a | 278.00 | 35 | |
| mult38.a | 97.00 | 1345 | |
| mult39.a | 107.00 | 69 | tweaked slightly |
| mult40.a | 278.00 | 35 | |
| mult43.a | 208.90 | 26 | |
| mult44.a | 109.00 | 69 | |
| mult47.a | 175.00 | 20 | |
| mult57.a | 48.49 | 1058 | |
| mult65.a | 47.49 | 1061 | |
| mult66.a | 45.49 | 1580 | 🥇 fastest |
| mult68.a | 188.00 | 20 | at label 'noadd' use 'ror' not 'lsr' as seen in some editions of the book |
| mult70.a | 1987.11 | 31 | |
| mult71.a | 1572.91 | 41 | |
| mult72.a | 1544.56 | 16 | 🥇 smallest |
| mult73.a | 1174.08 | 28 | |
| mult75.a | 205.90 | 24 | bugs fixed |
| mult76.a | 185.00 | 18 | |
| mult77.a | 288.00 | 43 | |
| mult78.a | 188.00 | 20 | fixed misleading variable names |
| mult79.a | 399.00 | 39 | |
| mult80.a | 110.00 | 325 | |
| mult81.a | 199.00 | 26 | |
| mult82.a | 67.24 | 827 | |
| mult83.a | 56.00 | 1079 | |
| mult84.a | 253.92 | 1199 | |
| mult87.a | 174.00 | 630 |
To see the results of the smaller routines more clearly, here is a zoomed in view of the same results:
| Source | Average Cycles | Memory (bytes) | My Changes |
|---|---|---|---|
| mult1.a | 751.00 | 38 | |
| mult2.a | 578.00 | 33 | 🥇 smallest. (optimised slightly from original) |
| mult3.a | 711.00 | 36 | |
| mult4.a | 567.00 | 137 | I use mult39 from Revs and combine to make 16x16 |
| mult15.a | 204.60 | 2180 | |
| mult31.a | 238.07 | 2219 | |
| mult33.a | 609.86 | 1276 | with test code removed, and tables page aligned. Stores numbers in MSB order |
| mult36.a | 957.01 | 55 | |
| mult41.a | 350.00 | 1149 | I use mult13 and combine to make 16x16 |
| mult42.a | 403.83 | 647 | I use mult16 and combine to make 16x16 |
| mult45.a | 695.00 | 38 | optimised slightly |
| mult46.a | 655.00 | 40 | |
| mult48.a | 707.11 | 69 | |
| mult49.a | 703.00 | 43 | version of mult48 with 8x16 multiply 'shortcut' removed |
| mult50.a | 534.00 | 55 | unrolled mult2 |
| mult51.a | 524.00 | 69 | unrolled mult2 |
| mult52.a | 519.00 | 75 | unrolled mult2 |
| mult53.a | 514.00 | 95 | unrolled mult2 |
| mult54.a | 497.00 | 192 | unrolled mult2 |
| mult55.a | 483.50 | 344 | fully unrolled mult2 |
| mult56.a | 259.96 | 1210 | I use mult27 and combine to make 16x16 |
| mult58.a | 365.03 | 772 | I use mult16 and combine to make 16x16 |
| mult59.a | 553.99 | 67 | |
| mult60.a | 527.00 | 39 | mult59 but I use fixed zero page addresses, remove 'decrement to avoid clc' |
| mult61.a | 482.00 | 57 | ...then unrolled the outer loop |
| mult62.a | 442.00 | 93 | ...then unrolled the two inner loops once |
| mult63.a | 422.00 | 165 | ...then unrolled the two inner loops twice |
| mult64.a | 386.00 | 279 | ...then unrolled the two inner loops fully, and optimise register use |
| mult67.a | 633.00 | 37 | |
| mult69.a | 946.52 | 65 | |
| mult74.a | 1358.00 | 86 | bug fixed |
| mult85.a | 540.50 | 38 | |
| mult86.a | 187.07 | 2170 | 🥇 fastest |
| mult88.a | 1231.00 | 36 | |
| mult89.a | 492.95 | 175 | I tweaked for speed and size |
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.
| Source | Average cycles | Memory (bytes) | Notes |
|---|---|---|---|
| smult1.a | 62.99 | 2095 | 8 x 8 bit signed multiply (16 bit result), tweaked for size and speed (based on mult14.a) |
| smult2.a | 329.67 | 49 | 8 x 8 bit signed multiply (16 bit result), Booth's Algorithm, bug fixed and optimised |
| smult3.a | 277.57 | 2253 | 16 x 16 bit signed multiply (32 bit result), tweaked slightly (based on mult31.a) |
| smult4.a | 242.52 | 67 | 8 x 8 bit signed multiply (16 bit result) based on the unsigned mult19 |
| smult5.a | 180.50 | 35 | 8 x 8 bit signed multiply (16 bit result) based on the unsigned mult9 |
| smult6.a | 158.00 | 39 | 8 x 8 bit signed multiply (16 bit result) |
| smult7.a | 88.50 | 1400 | 8 x 8 bit signed multiply (16 bit result) with bug fix |
| smult8.a | 62.99 | 1068 | 8 x 8 bit signed multiply (16 bit result) based on the unsigned mult65 |
| smult9.a | 570.00 | 81 | 16 x 16 bit signed multiply (32 bit result) based on the unsigned mult60 |
| smult10.a | 53.99 | 2079 | 8 x 8 bit signed multiply (16 bit result) |
| smult11.a | 51.99 | 2334 | 8 x 8 bit signed multiply (16 bit result) |
| smult12.a | 234.57 | 2210 | 16 x 16 bit signed multiply (32 bit result), tweaked slightly (based on mult86.a) |
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).
| Source | Average cycles | Memory (bytes) | Notes |
|---|---|---|---|
| omult1.a | 649.00 | 33 | 16 x 16 bit unsigned multiply, ONLY low 16 bit result |
| omult2.a | 145.00 | 16 | 8 x 8 bit unsigned multiply, ONLY low 8 bit result |
| omult3.a | 128.00 | 24 | 8 x 8 bit unsigned multiply, ONLY high 8 bit result |
| omult4.a | 686.88 | 70 | 24 x 8 bit sign-magnitude multiply, 32 bit result |
| omult5.a | 492.96 | 196 | 16 x 16 bit signed/sign-magnitude multiply, 16 bit signed approximate result |
| omult6.a | 153.46 | 38 | 16 x 16 bit unsigned multiply, ONLY low 16 bit result (or carry set on overflow) |
| omult7.a | 46.72 | 802 | 8 x 8 bit unsigned multiply, 8 bit high byte approximate result |
| omult8.a | 49.20 | 1075 | 8 x 8 bit unsigned multiply, 8 bit high byte approximate result |
| omult9.a | 22.97 | 780 | 8 x 8 bit unsigned multiply, 8 bit high byte approximate result |
| omult10.a | 909.00 | 50 | 16 x 32 bit unsigned multiply, 32 bit low bytes result |
| omult11.a | 43.00 | 547 | 8 x 8 bit unsigned multiply, ONLY approximate high 8 bit result |
| omult12.a | 181.04 | 27 | 8 x 8 bit unsigned multiply, ONLY low 8 bit result |
| omult13.a | 202.01 | 179 | 16 signed x 8 bit sign-magnitude, 16 bit result, div 128 |
| omult14.a | 575.00 | 43 | 16 x 16 bit unsigned multiply, ONLY low 16 bit result |
| omult15.a | 390.00 | 47 | 16 x 16 bit unsigned multiply, ONLY low 16 bit result |
| omult16.a | 223.69 | 33 | 16 x 16 bit unsigned multiply, ONLY low 16 bit result (or carry set on overflow) |
| omult17.a | 267.00 | 34 | 16 x 8 bit unsigned multiply, ONLY low 16 bit result |
| omult18.a | 2036.00 | 76 | variable m x n byte unsigned multiply (all 16 bit x 16 bit multiplies tested) |
| omult19.a | 2169.00 | 48 | 24 x 24 bit unsigned multiply, 48 bit result (tested over millions of random inputs, and all 16 bit inputs) |
| omult20.a | 2741.00 | 66 | 32 x 32 bit unsigned multiply, 64 bit result (tested over millions of random inputs, and all 16 bit inputs) |
| omult21.a | 1014.00 | 49 | 24 x 24 bit unsigned multiply, 48 bit result (tested over millions of random inputs, and all 16 bit inputs) |
| omult22.a | 1653.00 | 59 | 32 x 32 bit unsigned multiply, 64 bit result (tested over millions of random inputs, and all 16 bit inputs) |
| omult23.a | 1381.00 | 76 | variable m x n byte unsigned multiply (all 16 bit x 16 bit multiplies tested) |
| omult24.a | 1356.94 | 61 | 24 x 24 bit unsigned multiply, ONLY low 24 bit result (tested over millions of random inputs, and all 16 bit inputs) |
| omult25.a | 60.00 | 16 | 3 x 8 bit unsigned multiply, ONLY high 8 bit result |
| omult26.a | 145.00 | 16 | 8 x 8 bit unsigned multiply, ONLY high 8 bit result |
| omult27.a | 444.00 | 22 | 16 x 8 bit unsigned multiply, ONLY high 16 bit result |
| omult28.a | 897.00 | 24 | 24 x 8 bit unsigned multiply, ONLY high 24 bit result |
| omult29.a | 267.00 | 34 | 16 x 8 bit unsigned multiply, ONLY low 16 bit result |
| omult30.a | 310.00 | 40 | 24 x 8 bit unsigned multiply, ONLY high 24 bit result |
| omult31.a | 168.90 | 2162 | 24 x 8 bit unsigned multiply, ONLY high 24 bit result |
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:
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:
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:
GO64! magazine articles (omult9.a)
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
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
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)
Elite, Master version (omult7.a)
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)
Elite, Second Processor version (omult8.a)
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)
Alternative: a table-of-squares approximation (omult11.a)
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:
- remember if the sign of the two input numbers differ
- remove the sign of each input value (abs)
- do a regular unsigned multiply
- recall if the signs differ and negate the result if needed
The faster, craftier method is:
- do a regular unsigned multiply
- If the first input is negative, subtract the second input from the high byte(s) of the result.
- 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.