[CSDb] - User Forums - Fast large multiplies

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Fast large multiplies

2012-06-09 19:45

Repose

Registered: Oct 2010
Posts: 225

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?

... 144 posts hidden. Click here to view all posts....

2021-12-10 16:56

Martin Piper

Registered: Nov 2007
Posts: 722

This thread is an interesting coincidence as I've been thinking about C64 3D again. :)

2021-12-14 10:29

Repose

Registered: Oct 2010
Posts: 225

I wrote an alpha 16x16=32 unsigned, it's 1024 cycles, but if you inline the jsr umult16, it should be 930 cycles. Now I'm exploring not using umult16's at all, but to consider it as a large set of 8bit multiplies; the point is to optimize setting the multiplier (the high bytes of f(x)). I also am playing with the "zip" adds (where I add from right to left then go back to the right, next row), and optimizing register use, basically tax:txa for saving your spot in the beginning column.

The other news is, by using a gray code for the order of operations, I saved a ldy so my umult16 is 195 now.

I have even better ideas; using Knuth's equivalence I can do just 3xumult16.

con't...

2021-12-14 11:33

Repose

Registered: Oct 2010
Posts: 225

Knuth's idea

Given x=x1*256+x0, y=y1*256+y0

 y1 y0
*x1 x0

Calculation       Range
k=(y1-y0)*(x1-x0) +-FE01
l=y1*x1           0-FE01
m=y0*x0           0-FE01
n=l+m-k           0-1FC02

l+m               0-1FC02
l-k or m-k        +-FE01

x*y=l*65536+n*256+m (for 8 bit Xn/Yn)

Example (16x16 bits):
 y1 y0 ->$20 10
*x1 x0    40 30

k=(20-10)*(40-30)=100
l=20*40=800
m=10*30=300
n=800+300-100=a00

llll0000 -> 08000000
 nnnnn00     00a0000
    mmmm        0300
----------------
2010*4030 = 080a0300

x*y=l*4294967296+n*65536+m (for 16 bit Xn/Yn)

example with 16-bit values:
2000 1000
4000 3000
k=1000*1000=0100 0000
l=2000*4000=0800 0000
m=1000*3000=0300 0000
n=00A00 0000

800 0000 0000 0000
     a00 0000 0000
          300 0000
------------------
800 0a00 0300 0000

If multiplies are expensive, this is faster. Estimating 32x32=64;

3x umult16 ~585
adds        ~94
total      ~679

2021-12-14 11:40

Repose

Registered: Oct 2010
Posts: 225

About gray codes, ref.
https://en.wikipedia.org/wiki/Gray_code#Constructing_an_n-bit_G..

The use of gray codes is to minimize setting the multiplier/multiplicand, i.e.

;set multiplier as mier
lda mier ;3
sta p_sqr_lo ;3 (often published as f(x))
sta p_sqr_hi ;3
eor #$ff ;2
sta p_negsqr_lo ;3 (also known as g(x))
sta p_negsqr_hi ;3; 3+3+3+2+3+3 = 17 cycles

and

;set multiplicand
ldy mand ;3

In the following table, order 01 would mean change y first. Across the top are the starting variables; i.e. 00 means start with setting x0 and y0 as m'ier and m'and.

	start                   xy
order	00	01	10	11
xy
01	00	01	10	11
	01	00	11	10
	11	10	01	00
	10	11	00	01

10	00	01	10	11
	10	11	00	01
	11	10	01	00
	01	00	11	10

The gray code sequence can be best understood by following these values in a circle; with a starting point and a direction of clockwise or counter-clockwise:
	01
      00  11
	10

there's two ways to end with the high bytes;
start with x0*y1 and change y first, or
start with x1*y0 and change x first. The reason I want to end with the high bytes is to return them in registers, and these bytes are most useful if you only want 16x16=16.

x0*y0
x0*y1 ;change y first i.e. ldy y1
x1*y1 ;change x with +set_mier x1
x1*y0

x0 y0
x1 y0 ;change x first
x1 y1
x0 y1

x0 y1
x0 y0 ;change y first
x1 y0
x1 y1

x0 y1
x1 y1 ;change x first
x1 y0
x0 y0

x1 y0
x1 y1 ;change y first
x0 y1
x0 y0

x1 y0
x0 y0 ;change x first
x0 y1
x1 y1

x1 y1
x1 y0 ;change y first
x0 y0
x0 y1

x1 y1
x0 y1 ;change x first
x0 y0
x1 y0

This is all assuming you are storing each partial result into a self-mod summing routine to come after, in which case the order of operations of the multiplies doesn't matter. If you were adding the result during the multiples, you couldn't make use of this trick to minimize setting of the m'ier.

2021-12-14 12:27

Repose

Registered: Oct 2010
Posts: 225

Survey of multiply methods/ideas

If I really want to explore every way that could be the fastest, here's a list of ideas:

identity mults
1 - sin(a)*cos(b)=(sin(a+b)+sin(a-b))/2
2 - cos(a)*cos(B)=(cos(a+b)+cos(a-b))/2
3 - sin(a)*sin(b)=(cos(a-b)-cos(a+b))/2
4 - a*b=exp(log(a)+log(b))
5 - a*b = [(a + b)² - (a - b)²]/4
6 - k=(y1-y0)*(x1-x0), l=y1*x1, m=y0*x0, n=l+m-k, x*y=l*65536+n*256+m

Karatsuba mult

y1 y0
x1 x0
-----
z2=x1*y1
z0=x0*y0
z1=(x1+x0)*(y1+y0)-z2-z0

Booth multiply

Booth-2 is (n+1)=3 bits a time, overlapping by 1
which is how many?

aaa
  bbb
    ccc
      dd_

or 4

nybble mult
use a table of every a*b where a,b are 4-bit numbers.

residue number system
a set of modulo numbers can represent any number
you can add the residues separately without carry.
example of a (3,5) residue number system, supports 0-14:

you can pick better moduli; like 2^k and 2^k-1, like 256 and 255 which are co-prime. It encodes 65280 values.

REU multiply

Address Description
------- -----------
$de00   256 bytes of data (See $dfc0-$dfc3 for more information)
$df7e   write to this location to activate the RAMLink hardware
$df7f   write to this location to deactivate the RAMLink hardware.
$dfa0   lo byte of requested RAMCard memory page
$dfa1   hi byte of requested RAMCard memory page
$dfc0   write to this location to show RL variable RAM at $de00 (default)
$dfc1   write to this location to show RAMCard memory at $de00
$dfc2   write to this location to show the RAM Port device $de00 page at $de00
$dfc0   write to this location to show Pass-Thru Port dev. $de00 page at $de00

;8bit mult, of x*y to z0;z1
rl_page=$de00
rl_sel_ramcard=$dfc1
rl_lo=$dfa0
rl_hi=$dfa1
rl_activate=$df7e
rl_deactivate=$df7f
sta rl_activate;4
stx rl_lo;4
lda #0;2
sta rl_hi;4
sta rl_sel_ramcard;4
lda rl_page,x;5?
sta z0;3
inc rl_hi;is this r/w? 6
lda rl_page,x;5
sta z1;3
sta rl_deactivate;4
rts

total 42

sine mult example
cos(a)*cos(B)=(cos(a+b)+cos(a-b))/2

x	cos(x)
-pi/2	0
0	1
pi/2	0
pi	-1
3pi/2	0
2pi	1

example, .5 * .75
cos-1(.5)=1.0471975511965977461542144610932
cos-1(.75)=0.72273424781341561117837735264133
a+b=1.7699317990100133573325918137345
a-b=0.32446330338318213497583710845183
cos(a+b)=-0.197821961869480000823505899216
cos(a-b)=0.947821961869480000823505899216
cos(a+b)+cos(a-b)=.75
/2=.375

Convolution mult
Lost my notes here - something starting with W... a lot of adds for a few mults.
https://en.wikipedia.org/wiki/Convolution#Fast_convolution_algo..

Neural net multiplication
not much of a gain

direct massive lookup tables
various low-level code optimizations
illegal opcodes
order of operations
branch-tree optimizations (keeping state in the code location, i.e. branch of every possible multiplier etc.)

Applications of multiplication
-fast way to arrange complex multiply
-fast matrix multiply
-using inverse tables to divide

Different types of number systems
-modular arithmetic, Chinese Remainder system
-storing numbers as primes
-keeping numbers as fractions
-2's complement, 1's complement, offset

2021-12-15 09:01

Martin Piper

Registered: Nov 2007
Posts: 722

I've been pondering a hardware multiply...
Write control byte: xy
y = bytes for operand 1
x = bytes for operand 2

Write bytes in MSB for operand 1 then 2.

Then read bytes in MSB order for multiply result.

For example:
Write hex: 21 47 23 01
Read: b5 50 00

2021-12-15 11:59

Repose

Registered: Oct 2010
Posts: 225

Me too, just yesterday!
https://media.digikey.com/pdf/Data%20Sheets/Parallax%20PDFs/uM-..

The uM-FPU is a 32-bit floating point coprocessor that can be easily interfaced with microcontrollers to provide
support for 32-bit IEEE 754 floating point operations and long integer operations. The uM-FPU is easy to
connect using either an I2C or SPI compatible interface.

Which can be connected to the user port. I believe the serial port would work, then it's 16 cycles per byte.

2021-12-15 13:23

Krill

Registered: Apr 2002
Posts: 2980

The only acceptable arithmetics accelerator is the 6502 in the disk drive. =)

2021-12-15 15:18

Martin Piper

Registered: Nov 2007
Posts: 722

Quote: Me too, just yesterday!
https://media.digikey.com/pdf/Data%20Sheets/Parallax%20PDFs/uM-..

The uM-FPU is a 32-bit floating point coprocessor that can be easily interfaced with microcontrollers to provide
support for 32-bit IEEE 754 floating point operations and long integer operations. The uM-FPU is easy to
connect using either an I2C or SPI compatible interface.

Which can be connected to the user port. I believe the serial port would work, then it's 16 cycles per byte.

I was thinking more like a MC68882 :)
But finding something similar operating at 5V, with parallel address/data rather than serial and still in production, is tough.

2021-12-15 19:52

Repose

Registered: Oct 2010
Posts: 225

Some kind of extra SPI to parallel circuit would help. Since the chip I mentioned has 4MHz serial speed, it's fast enough to read a parallel port at full speed.
https://highfieldtales.wordpress.com/2011/12/04/very-fast-spi-t..

In the end, what do we want though? You could make a GPU cart for the c64, which runs it's own 2d/3d graphic engine, where you simply define the objects. The motions, display updates, collisions, could all be handled automatically, all you need to to keep score, play music, run the display mode, and handle joystick. Just like Blue REU, the output could be stuffed directly to display memory using an advanced FLI mode with practically full color. It would be like a brand new game machine in 160x200x16.

Or, it could be an assist, using memory mapped registers as you describe, and leave the c64 more in control.

I think of this a lot - do I even want to buy a c64 ultimate? It's convenient and fun to play demos and games with full power, but I think I still want to do obscure hardware hacks and real assists. For example, I've always wanted to use the CIA to measure variations in 50/60 Hz power line frequency. I want to attach the serial port to an SD card and bit bang the storage.