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 8-bit operands, 16-bit 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 object-code:

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. *