Re: OT: primitive mult/div algorithms Message #9 Posted by Gerson W. Barbosa on 26 May 2012, 6:02 p.m., in response to message #1 by Egan Ford
While not the fastest multiplication algorithm around, Russian peasant multiplication is interesting and easy to implement. Once I used it for arbitrary length integer multiplication on the Z80 microprocessor. The following is a simple 8bit operands, 16bit result Z80 program:
org $c000 ; sorry, no comments.
ld hl,0
ld c,$ff
ld de,$ff
loop: ld a,c
cp 0
ret z
and 1
jr z,loop0
add hl,de
loop0: srl c
sla e
rl d
jr loop
The equivalent 6502 code below is somewhat lengthy, but someone not so rusty at 6502 assembly language programming as I am might be able to make it shorter:
* = $0300
LDA $0340
STA *$00
LDA $0341
STA *$01
LDA #$00
STA *$02
STA *$03
STA *$04
LOOP LDA *$00
BEQ END
AND #$01
BEQ LOOP0
CLC
LDA $01
ADC *$03
STA *$03
LDA $02
ADC *$04
STA *$04
LOOP0 LSR *$00
ASL *$01
ROL *$02
JMP LOOP
END RTS
This can be assembled at http://www.masswerk.at/6502/assembler.html, giving the following objectcode:
AD 40 03 85 00 AD 41 03
85 01 A9 00 85 02 85 03
85 04 A5 00 F0 1C 29 01
F0 0F 18 AD 01 00 65 03
85 03 AD 02 00 65 04 85
04 46 00 06 01 26 02 4C
12 03 60
As I didn't find an online hex to dec convert that would convert all bytes at once, I did it on Emu71:
10 DESTROY ALL
20 FOR I=1 TO 51
30 READ B$
40 PRINT HTD(B$);
50 NEXT I
60 DATA AD, 40, 03, 85, 00, AD, 41, 03, 85, 01, A9, 00, 85, 02, 85, 03, 85
70 DATA 04, A5, 00, F0, 1C, 29, 01, F0, 0F, 18, AD, 01, 00, 65, 03, 85, 03
80 DATA AD, 02, 00, 65, 04, 85, 04, 46, 00, 06, 01, 26, 02, 4C, 12, 03, 60
The AppleWin emulator can be used to test this and other algorithms:
10 HOME : PRINT "ENTER A,B"
20 FOR I = 768 TO 818
30 READ BT: POKE I,BT
40 NEXT I
50 INPUT A,B: POKE 832,A: POKE
833,B
60 CALL 768: PRINT "A * B = "; PEEK
(3) + 256 * PEEK (4)
70 DATA 173,64,3,133,0,173,65,
3,133,1,169,0,133,2,133,3,13
3
80 DATA 4,165,0,240,28,41,1,24
0,15,24,173,1,0,101,3,133,3
90 DATA 173,2,0,101,4,133,4,70
,0,6,1,38,2,76,18,3,96
RUN
ENTER A,B
?217,253
A * B = 54901
]
Gerson.
Edited: 26 May 2012, 6:07 p.m.
