I'm fairly sure I've read this before - here or over on the retrocomputing forum, but can't for the life of my find a recent thread on it (pointers welcome!)

However this site pops up from time to time:

http://www.txbobsc.com/aal/1986/aal8603.html

and in it there is possibly the fastest unsigned 8x8 multiply routine for the 6502. I decided to implement it in my Ruby system to see how it compares to my existing code... Especially when used to implement a 32x32 multiply as is used inside my BCPL system which is a 32-bit bytecode VM.

The good news is that it's faster than my native 32x32 multiply, the bad news is that it's slower than my "hardware arithmetic accelerator" which is an ATmega which is effectively an 8-bit CPU which also runs at 16Mhz. The advantage the ATmega has is that it has an on-board single cycle 8x8 multiply instruction. However it's only just faster due mostly to the latency of the calls between the 6502/816 side and the ATmega side, so while an interesting exercise, I'm yet again reminded of Knuth's Premature Optimisation quote.

The code below is in my BCPL VM minus the entry and exit stuff and handling signed numbers - regA and regQ are 32-bits wide located in zero/direct page, regW is 64-bits wide, again in zero page. It implements what's essentially a long multiplication of the bytes, adding them into regW at each step which was previously zeroed. It only needs to do enough to produce a 32-bit result.

Inlining the calls to mul8 will save a JSR/RTS, but again, Knuth is tapping my shoulder as there's only 10 calls, so that would save (6+6) * 10 = 120 cycles... Hmm. Well, might be worth it but at the expense of a lot more code space...

There is no doubt this is faster, so if you need an 8x8 (or more) multiply then this is it. My initial 65816 code for 32x32 mul takes just over 2000 cycles...

Also on that site is code for an 816 ('802) but it's going to be very much slower (at least I think it will be - I'll test it at some point). My own thought are that if I have enough RAM (needs 128KB) I can implement a lookup table which would enable me to do an 8x8 multiply in 16-bit mode with 2 simple lookups and none of the arithmetic needed to handle the table of squares / 4. I will give that a go when I upgrade my Ruby816 board to 1MB of RAM, but with 512KB it's a bit tight to take half it's RAM and leave enough to run the BCPL compiler in.




I've attached my versions of the code on the page above:

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Nice! It was only a few weeks ago that I was looking for a comment someone had made, about this algorithm I think, to the effect that although the index registers are only 8 bits, you can wangle a 9 bit addition because the low byte of the base address is another 8 bits, and by using both you get a sort of 9 bit lookup.

But I wasn't able to find that discussion!

This was a recent mention of the quarter-square method, although I'm sure there must be previous mentions on this forum too.

What's awkward of course is that there could have been a series of algorithms, each one described at the time as the fastest, but overall only one of them retains the title.

For a table driven approach, is there any chance that looking up 4x4 results could be worthwhile? (Nibble extraction can be done by table, of course. But reassembling partial products might be a tangle.)

Ah, I think that's the relatively recent one I was thinking of, thanks.



I'll give it some thought, but my concern is the shifting involved...

... thinking out loud, enter with the 4-bit args in A and X as before... store X in zp, shift A up 4 places, OR in the stored X, transfer to X, load from 256 byte table indexed by X and you have the result of the 4x4 multiply. ... then do the long multiply and add to get a 32x32 multiply which involves 8+7+...1 steps = 36 steps where the key part is isolating the nibble and that's either 4 shifts or a table lookup then the call then, as you said; reassembling the partial products...

I'll ponder more over the weekend!

Cheers,

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

_________________
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?

Thanks, but I have a macro assembler that has a repeat function, so tables like this are trivial. e.g. from the source code I posted:



but for anything much bigger calculating it at boot time is faster than loading it from disk (No ROM)

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

The thought of going that route is completely foreign to me, unless I had a hard real-time requirement that gave me no other choice but to starve. On the other hand, I will eagerly spend many hours in pursuit of a handful of bytes to save, so ... I'm somehow reminded of the Jack Sprat poem, but I decline to offer any opinion on which of us is "Jack".

_________________
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)

Yep, you can save bytes, or save microseconds... sometimes, just sometimes, you can save both!

"Lean" can denote either using a reduced number of clock cycles or fewer bytes of machine code.

My philosophy a bit of the opposite of yours.

I have had only a few times where I had to make code smaller to fit an available space, so I tend to code leaning toward speed though I rarely take the extreme end of the time vs space tradeoff as in this multiplication discussion.

I never had to build "big" programs for an 8-bit (64K address space) platform.

I started Windows programming toward the end of the real-mode era. The best machines at the time were something like a 16 MHz 386. Because the architecture of Windows provided for the loading of segments of code on demand, the emphasis was still more toward speed.

Many developers today are accustomed to using two separate environments, one to build the code and another one to run it. I have no desire to build something like a compiler which runs natively on an 8-bit machine. Shoehorning code is not my idea of fun.

However, working on P-code for several weeks has given me an appreciation of how much more compact interpreted code is compared to native machine code. I have come to consider the value of an ability to mix native and interpreted code within one program for an 8-bit platform.

Microsoft C compilers in the early 90s had the ability to generate either interpreted or native code and the run-time environment managed the interface between the two. Early versions of Microsoft Word were built using this technology until the widespread adoption of protected-mode Windows obsoleted the need. It never JIT the interpreted code to native; machines at the time were considered to be too slow to do that. Developers had to choose between the two when programs were built.

I will have to look at doing something like this for multiplying two bignums using partial products instead of the traditional shift and add approach.

I hope that's "worst case". I whipped up a little unsigned 32 x 32 -> 32 routine that spends 41 ticks for 0 * j, 79 or 104 ticks for i * 0, ~2332 ticks for 4294967295 * 4294967295, and typically something closer to 1000 ticks. But I don't have an '816 to test it.

[edit: corrected estimates for tick counts]

_________________
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)

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

I think S_LONG is supposed to be 4 here, however that's good and compact code there.

It's fractionally faster than my original long multiplication code @ 13.311 secs. vs. 13.380 for my version with the loop unrolled, or 14.183 seconds for the loop unrolled 31 times. My version is based on code from: http://nparker.llx.com/a2/mult.html

With my accelerated 8x8 multiplier, the same benchmark (another Mandelbrot using scaled integers written in BCPL) is 11.099 seconds.

If I offload the multiply to the ATmega then it's 10.985 seconds.

Will try MikeB's code when I get time.

Cheers,

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

I knew something was fishy about my cycle counts ... the 16-bit shift and rotate instructions are seven cycles for DP, not five, so my estimates were low. @BDD: that's a nifty little subroutine, but it comes at a speed cost, like so many nifty little subroutines often do.

_________________
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)

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

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