Basic idea is the same as detailed in Fast 6502 Multiplication:
ab = [(a + b)² - (a - b)²]/4
But substitute:
m = a/2;
n = b/2;
Then:
ab = (m + n)² - (m - n)² + c
"c" is a correction factor - details below.
Advantages:
- Lookup tables fit in 2 × 256 bytes total, so less memory.
- Lookup tables are squares that are not multiplied or divided by anything, so can be reused more easily in other functions.
Disadvantages:
- Must correct for odd "a" and/or odd "b" as follows:
If a is odd, then c = b
If b is odd, then c = a
If a and b are both odd, then c = a + b - 1
Average case is 127 cycles, with a low of 104 and a high of 151.
Code follows. Compatible with the 6502 emulator at http://skilldrick.github.io/easy6502/.
; multiplies var_a by var_b
; result stored in var_r and var_s
; code is compatible with http://skilldrick.github.io/easy6502/
* = $80
var_a:
DCB 0
var_b:
DCB 0
var_m:
DCB 0
var_n:
DCB 0
var_r:
DCB 0
var_s:
DCB 0
* = $600
LDA #15
STA var_a
LDA #16
STA var_b
JSR multiply
BRK
multiply:
;if a & b are odd, r = -1, else r = 0
LDA var_a
AND var_b
AND #1
BEQ _1
LDA #255
_1:
STA var_r
STA var_s
;m = a / 2
LDA var_a
LSR A
STA var_m
BCC _2
;a is odd, r += b
CLC
LDA var_r
ADC var_b
STA var_r
LDA var_s
ADC #0
STA var_s
_2:
;n = b / 2
LDA var_b
LSR A
STA var_n
BCC _3
;b is odd, r += a
CLC
LDA var_r
ADC var_a
STA var_r
LDA var_s
ADC #0
STA var_s
_3:
;normalize so that m >= n
LDA var_m
CMP var_n
BCS _4
;n > m, swap m and n
TAY
LDA var_n
STA var_m
STY var_n
_4:
;r += (m + n)^2
CLC
LDA var_m
ADC var_n
TAY
LDA var_r
ADC sqr_lo,Y
STA var_r
LDA var_s
ADC sqr_hi,Y
STA var_s
;r -= (m - n)^2
SEC
LDA var_m
SBC var_n
TAY
LDA var_r
SBC sqr_lo,Y
STA var_r
LDA var_s
SBC sqr_hi,Y
STA var_s
;done!
RTS
sqr_lo:
DCB 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225
DCB 0, 33, 68, 105, 144, 185, 228, 17, 64, 113, 164, 217, 16, 73, 132, 193
DCB 0, 65, 132, 201, 16, 89, 164, 241, 64, 145, 228, 57, 144, 233, 68, 161
DCB 0, 97, 196, 41, 144, 249, 100, 209, 64, 177, 36, 153, 16, 137, 4, 129
DCB 0, 129, 4, 137, 16, 153, 36, 177, 64, 209, 100, 249, 144, 41, 196, 97
DCB 0, 161, 68, 233, 144, 57, 228, 145, 64, 241, 164, 89, 16, 201, 132, 65
DCB 0, 193, 132, 73, 16, 217, 164, 113, 64, 17, 228, 185, 144, 105, 68, 33
DCB 0, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1
DCB 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225
DCB 0, 33, 68, 105, 144, 185, 228, 17, 64, 113, 164, 217, 16, 73, 132, 193
DCB 0, 65, 132, 201, 16, 89, 164, 241, 64, 145, 228, 57, 144, 233, 68, 161
DCB 0, 97, 196, 41, 144, 249, 100, 209, 64, 177, 36, 153, 16, 137, 4, 129
DCB 0, 129, 4, 137, 16, 153, 36, 177, 64, 209, 100, 249, 144, 41, 196, 97
DCB 0, 161, 68, 233, 144, 57, 228, 145, 64, 241, 164, 89, 16, 201, 132, 65
DCB 0, 193, 132, 73, 16, 217, 164, 113, 64, 17, 228, 185, 144, 105, 68, 33
DCB 0, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1
sqr_hi:
DCB 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
DCB 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3
DCB 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8
DCB 9, 9, 9, 10, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15
DCB 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 23, 23, 24
DCB 25, 25, 26, 26, 27, 28, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35
DCB 36, 36, 37, 38, 39, 39, 40, 41, 42, 43, 43, 44, 45, 46, 47, 48
DCB 49, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63
DCB 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79
DCB 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 95, 96, 97, 98
DCB 100, 101, 102, 103, 105, 106, 107, 108, 110, 111, 112, 114, 115, 116, 118, 119
DCB 121, 122, 123, 125, 126, 127, 129, 130, 132, 133, 135, 136, 138, 139, 141, 142
DCB 144, 145, 147, 148, 150, 151, 153, 154, 156, 157, 159, 160, 162, 164, 165, 167
DCB 169, 170, 172, 173, 175, 177, 178, 180, 182, 183, 185, 187, 189, 190, 192, 194
DCB 196, 197, 199, 201, 203, 204, 206, 208, 210, 212, 213, 215, 217, 219, 221, 223
DCB 225, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254