I have exhaustively tested and compared the performance and memory use of over 60 integer multiplication routines from the internet. (EDIT: Now over 120 routines)

I also explore the algorithms and techniques behind them:

https://github.com/TobyLobster/multiply_test

There was more to say on this subject than I thought when I started, so it was interesting to explore. If there are other good or interesting multiply routines out there let me know!

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Well done TobyLobster - a tour de force!

(All the static parts of 6502.org are mastered on github... in that sense, we all use it. But way to derail an interesting offering...)

That is a lot of very interesting information. One piece of additional data that might be helpful is a 'mean' time in cycles as well as an 'average'.

All the 'shift-and-add' routines I looked at all used an index register to count loops. In that case, it seems to me a fairly simple optimization for the 16x16 multipliers would be to check if the high byte of the multiplier is zero. If so, nothing in it can affect the result, and so the loop counter could be reduced from 16 to 8. It's only a few bytes to check, and any multiplication by less than 256 would benefit. To go further, you could also check the multiplicand and swap if the multiplier was greater than 256 but the multiplicand was less (more code, of course). To go further, you could write 8x8, 8x16 and full 16x16 routines and branch to one of them based on examining the multiplicand and multiplier (more code, of course).

Instead of counting, another way to control the loop is to check if the multiplier has become zero after each iteration. In a 16x16 multiplier, OR-ing the high and low bytes of the multiplier together would terminate as soon as the highest set bit was shifted out. A multiplier of zero or one would terminate after one iteration with no special check required.

Just to be clear, the 'average' figures I give are the arithmetic mean: the sum of all cycle counts divided by the number of counts. The error bars shown in the graphs show this average as the dot between the minimum and maximum cycle counts. Many of the routines have a low variance in the min and max values (bars of small height). Those that don't is usually because they have special case code for handling zero.


Good ideas. I wonder if the time to check for these cases is small enough to get win across all inputs? I'd be interested to see. The OR-ing trick is only done by omult1.a I think, but is it worth it? Certainly if you know in advance you are likely to be multiplying small numbers these will win.

That's how I did it in VTL02. It's very quick if the first term is small or the second term is a large-ish power of two, but probably suffers a bit with random inputs. I won't use tables in VTL02, but I might peek at a few of the smaller routines Toby has to see if they might be more suitable for an unsigned 16x16->16:

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

My bad. I meant to say 'median'. And maybe not the cycle time but what the actual operands are at that point (ie., do they have more than eight bits?).

It's a tricky question, I think, because the distribution of input values will come into it. It may well be that in many applications small multipliers will be found often, but in many others they won't.

Interesting technique to index with '0,X' to allow any zero page variable. If speed is important it may actually be faster to copy those inputs into temporary zp storage to avoid losing a cycle on every access.

Well, I'm already blowing 12 cycles per iteration by not in-lining the add. The VTL02 "IDE" is a balancing act between small size and high performance, with a (not so) slight bias in favor of small size.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

The idea of testing for an 8x16 bit multiply inside a 16x16 bit multiply was implemented back in 1980, in 'Micro - The 6502 Journal' magazine https://archive.org/details/micro-6502- ... 1/mode/2up (they also have a separate 8x8 multiply).

Intuitively it makes sense to shortcut, but it may not be so in practice. Suppose we add a header to an 16x16 multiply routine like this:



That seems simple enough, but throughout the full 16-bit range of operands will add 30,081,548,288 cycles (2^24 * 8 branch taken + (2^32 -2^24) * 7 branch not taken) to the overall execution time. On the other hand, it will only save 5,100,273,664 or so cycles overall (2^24 * (8 * 38)), depending on how long a 16x16 do-nothing loop takes. So a net slowdown.

Half measures may not do. Rather than try to optimize one loop, it may be best to split into multiple loops, as the article suggests.

I added the Micro magazine listing that I linked to above into my tests including its branch to 8x16 multiply (mult48). It's not very competitive these days, coming in at 707 cycles average, but should be representative of a typical shift-and-add.

If I remove the supposed 'shortcut' to the 8x16 routine it comes in slightly faster at 703 cycles average (mult49). So the supposed shortcut is actually slightly counterproductive if all inputs are equally likely (as we suspected). However, if in the context of a hypothetical use case the 'acl/h' input number of this routine is limited to < 32768 (i.e. top bit clear) then the shortcut gives a minor improvement. The smaller the top of the range the better the improvement:



This is for unsigned numbers. (Negative numbers will have the top bit set, so don't get a benefit if the unsigned multiply is used before adjusting for signedness).
So a shortcut can be useful if one of the inputs has a smaller range.

I've added some more good routines to the page, mostly 16 bit.