Fast Multiplication by Martin Arndt
[Up to Source Code Repository]

Fast Multiplication Using Tables
By Martin Arndt, 6 January 2004.

;Fast Multiplication
;
;The idea stems from Stephen Judd.
;You find it in The Fridge and in the C=Hacking magazine:
;
;Let f(x) = x^2 / 4.  Then
;
;       a*b = f(a+b) - f(a-b)
;
;You need 2 tables of squares with 9 bit input size and
;16 bit result size.
;
;You can save the building of the 2th complement
;
;   EOR #$ff
;   CLC
;   ADC #1
;
;by shifting the second table 1 byte down and
;using the 1th complement:
;
;   EOR #$ff
;
;This algorithm is very useful when you want to multiply
;multiple bytes by the same factor. Then you can set the
;zp addresses once and just modify the y register.
;With the same trick you can easily extend this algorithm
;to 16 bit. But if you want to be fast you will need more
;than the 8 zp addresses.


zp1=$20    			;8 bytes zp index addresses
zp2=$22
zp3=$24
zp4=$26

tab1=$4000 			;2 kbytes square tables
tab2=$4200
tab3=$4400
tab4=$4600

    	.org $c000

    	JSR init    ;first build the tables tab1..tab4
                	;and init zp1-zp4

    	LDY #$66    ;factor 1 in y
    	LDA #$12    ;factor 2 in a

    	STA zp1     ;set zp adresses
    	STA zp2
    	EOR #$ff
    	STA zp3
    	STA zp4

    	SEC
    	LDA (zp1),y
    	SBC (zp3),y
    	TAX         ;product lo in x
    	LDA (zp2),y
        SBC (zp4),y ;product hi in a

        RTS

init    LDX #0      ;build square tables
    	STX tab3+$fe
    	STX tab4+$fe
    	LDY #$ff

.loop1  TXA
    	LSR
    	CLC
    	ADC tab3+$fe,x
    	STA tab1,x
    	STA tab3+$ff,x
    	STA tab3,y
    	LDA #0
    	ADC tab4+$fe,x
    	STA tab2,x
    	STA tab4+$ff,x
    	STA tab4,y
    	DEY
    	INX
    	BNE .loop1

.loop2  TXA
    	SEC
    	ROR
    	CLC
    	ADC tab1+$ff,x
    	STA tab1+$100,x
    	LDA #0
    	ADC tab2+$ff,x
    	STA tab2+$100,x
    	INX
    	BNE .loop2

    	LDA #>tab1  ;init zp addresses
    	STA zp1+1
    	LDA #>tab2
    	STA zp2+1
    	LDA #>tab3
    	STA zp3+1
    	LDA #>tab4
    	STA zp4+1

    	RTS