| |
Repose
Registered: Oct 2010
Posts: 227 |
Fast large multiplies
I've discovered some interesting optimizations for multiplying large numbers, if the multiply routine time depends on the bits of the mulitplier. Usually if there's a 1 bit in the multiplier, with a standard shift and add routine, there's a "bit" more time or that bit.
The method uses several ways of transforming the input to have less 1 bits. Normally, if every value appears equally, you average half 1 bits. In my case, that becomes the worst case, and there's about a quarter 1 bits. This can speed up any routine, even the one that happens to be in rom, by using pre- and post- processing of results. The improvement is about 20%.
Another speedup is optimizing the same multiplier applied to multiple multiplicands. This saves a little in processing the multiplier bits once. This can save another 15%.
Using the square table method will be faster but use a lot of data and a lot of code.
Would anyone be interested in this?
|
|
... 145 posts hidden. Click here to view all posts....
|
| |
Repose
Registered: Oct 2010
Posts: 227 |
A diagram of the calculations:
y1 y0
x x1 x0
--------
x0y0h x0y0l
x0y1h x0y1l
x1y0h x1y0l
x1y1h x1y1l
-----------------------
z3 z2 z1 z0
A listing of the macros is quite long, as a lot of effort went into parsing the arguments the way I'm using them, plus some other features in my libary. Requires the latest C64 Studio 7.5, as there were a number of features I had added. Here is one of them:
!macro mult8_set_mier_snippet .mier {
;set multiplier as mier
;mier can be m/A
;requires .p_.sqr* and .p_.neg.sqr* pointers,
;(mathlib.p_sqr_lo, mathlib.p_neg_sqr_lo, mathlib.p_sqr_hi, mathlib.p_neg_sqr_hi)
;uses these macros from mathlib_util_macros.asm:
;reset_cycles, add_cycles_const
!if .mier = "X" or .mier = "Y" {
!error "multlib: mult8_snippet: mier must be m/A, not ", .mier
}
+reset_cycles
!if .mier != "A" {
lda .mier
!if .mier<$100 {
+add_cycles_const 3
} else {
+add_cycles_const 4
}
}
sta mathlib.p_sqr_lo ;3
sta mathlib.p_sqr_hi ;3
eor #$ff ;2
sta mathlib.p_neg_sqr_lo ;3
sta mathlib.p_neg_sqr_hi ;3; 3+3+3+2+3+3 = 17 cycles
+add_cycles_const 14
}
Here is the order of multiplies I used:
mier = x1
(x1) * y0 -> x1y0l, x1y0h
(x1) * y1 -> x1y1l, z3
mier = x0
(x0) * (y1) -> x0y1l, X
(x0) * y0 -> z0, A
|
| |
Frantic
Registered: Mar 2003
Posts: 1661 |
Very good! |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1423 |
Nice work, Repose!
Going to have to take another run at this one of these days.. |
| |
Repose
Registered: Oct 2010
Posts: 227 |
I can now support my claim with some confidence that I have achieved a world record for a published 16x16=32 unsigned mult.
Even my old routine has won out of 120 routines tested independently.
Take a look at the entry mult15.a here:
https://github.com/TobyLobster/multiply_test#the-results
This was a thrilling moment for me :)
But in general, its interesting to read about the various approaches, and to be fair, if you need a smaller routine, there's better choices. |
| |
Raistlin
Registered: Mar 2007
Posts: 757 |
Very nice write up, Repose! |
| |
Frantic
Registered: Mar 2003
Posts: 1661 |
Quote: I can now support my claim with some confidence that I have achieved a world record for a published 16x16=32 unsigned mult.
Even my old routine has won out of 120 routines tested independently.
Take a look at the entry mult15.a here:
https://github.com/TobyLobster/multiply_test#the-results
This was a thrilling moment for me :)
But in general, its interesting to read about the various approaches, and to be fair, if you need a smaller routine, there's better choices.
Congratulations! I totally get that it must have been thrilling. :D |
| |
Krill
Registered: Apr 2002
Posts: 3083 |
Quoting ReposeThe time is 188.1 cycles, averaged over all possible inputs. Pretty impressive. :)
It seems that most of the required memory of about 2 KB is spent by tables (which are generated), not so much the code itself, right?
If so, i guess this 16x16=32 routine could come in quite handy for something like https://github.com/exoticorn/upkr which still doesn't seem to have a C-64/plain 6502 unpacker (while 6502 unpackers using hardware-accelerated mul exist). |
| |
Repose
Registered: Oct 2010
Posts: 227 |
The code seems to be 120 bytes and the tables are 2044 bytes. I think I need to add some 30 more to create the tables. |
| |
JackAsser
Registered: Jun 2002
Posts: 2038 |
Very very nice write up @Repose! |
| |
Repose
Registered: Oct 2010
Posts: 227 |
Bruh! You were my hero before I started this :) You held the record before me, and still we are both way ahead of most posts and published books. Respects :) |
| Previous - 1 | ... | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 - Next |
