Nice! Yup I imagine the zero checks and clc avoidance in mul8x8 aren’t worth it with uniform random inputs. One day if I have the energy I might try the 32x32 version where avoiding the extra multiply might pay off.

Yeah, I would certainly be very interested to see a full 32x32 version.
EDIT: I ...

Thank you for contributing the implementation pdragon. Very interesting to see a new algorithm being used. I had to convert your 65C02 to plain old 6502 for my test framework, but fortunately I managed to convert without any loss of cycles, and only taking an extra 4 bytes. I switched 2xbra->jmp, an ...

Thanks. It should be possible to account for a skew in the probability of input data, as long as that skew is properly defined. I've not attempted that.

I could imagine (a) the usual algorithms running over all possible inputs, but with each result weighted depending on the size of the inputs. OR ...

I have amended to show the unused bytes.
I've used Y on input for smult11, a variant that saves two cycles by using another 256 byte lookup table.

Great! However, I would suggest
x0 = p_sqr_lo1 ; multiplier, 2 bytes
x1 = p_sqr_lo2
as it seems more logical to me (yes, I did lead you down the wrong path with my mistake).

Done.


I've also done a first pass of a signed 16x16.

Sounds good. I've just included a 8x8 signed multiply that is ...

trick:

x1 = p_sqr_lo

umult16
; set multiplier as x1
lda x1
;sta p_sqr_lo
sta p_sqr_hi
eor #$ff
sta p_neg_sqr_lo
sta p_neg_sqr_hi

; set multiplier as x0
; *x1 is no longer preserved

To easily save 3 cycles and 1 byte zp.

I could also accept Y0 in Y, but that can place restrictions on the ...

I've properly published this now at https://codebase64.org/doku.php?id=base:fastest_multiplication_2023

Note, there's some changes. My post above was missing an important comment (at first?), in any case your version is missing it
; set multiplicand as y0
ldy y0

;x1y0l = low(x1*y0)
;x1y0h ...

Here you go

Very nice Repose! That takes the top spot for the fastest 16 bit multiply. I published your code with cosmetic changes and a couple of minor trivial tweaks: I put the z0-z3 in zero page and replaced "sta z1" with "tay" to return the value in a register instead of memory.

Published as ...

Thanks for the update! I'm a bit worried though, as I did label my routine as updated in 2023, which is true, but only for clarity. My actual 188.1 routine is still not published, so I'm hoping you didn't think my existing 2023 update was the fast one, though I'm glad a more clear version was ...

I've updated the results with repose's improved code.

I do have a suggestion though, I'd like to see the results sorted by time, size ascending, and highlight the optimal ones as yellow like you do in the graphs.
Sadly github's markdown doesn't allow for colour, nor dynamically sorting tables by ...

Excellent! Every time I think "surely that's the limit. Can't get any better than that.", but I always seem to be wrong!

Cool. I did wonder whether starting with loading z1 might be more efficient somehow. In case it needs moving, we learn that quickly, and otherwise we are well placed to immediately compare it with the other candidate. I'm not sure though it would help or hinder overall but the flow at least would ...

Edit: And here's a first pass speed-optimised version - just writing out all the comparisons and swaps that are required, without attempting to share any code between branches.

A slight improvement to gfoot's speedy version: I managed to shave 3 bytes off with the same cycle count as before just ...

This thread totally nerd-sniped me. I decided to go for time efficiency and implement a solution similar to Chromatix's idea of a decision-based algorithm that picks one of 8 cases (2 of which are invalid).
I was tempted to do some self-modifying code magic ( opcodes of "STY/STA/STX zp" and "LDY ...

Ooh I didn't think it could get that small. Very nice.