8-bit Multiply: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
(Removal of syntax highlighter)
(fixing typo in code: "Mult" is actually "Factor")
Line 18: Line 18:
lda Res2
lda Res2
clc
clc
adc Mult
adc Factor
sta Res2 ;If so add number to result
sta Res2 ;If so add number to result
pla
pla

Revision as of 05:40, 12 October 2017

The following code multiplies two 8-bit integers (range 0...255) and outputs a 16-bit result using only real calculation, no lockup table so the size of the code is very small.

;8-bit multiply
;by Bregalad
;Enter with A,Y, numbers to multiply
;Output with YA = 16-bit result (X is unchanged)
Multiply
	sty Factor	;Store input factor
	ldy #$00
	sty Res
	sty Res2	;Clear result
	ldy #$08	;Number of shifts needed

-	lsr A		;Shift right input number
	bcc +		;Check if bit is set
	pha
	lda Res2
	clc
	adc Factor
	sta Res2	;If so add number to result
	pla
+	lsr Res2	;Shift result right
	ror Res
	dey
	bne -
	lda Res
	ldy Res2
	rts

Russian Peasant Algorithm

This is the Russian peasant algorithm which was suggested by Bob Rost in his NES Development class PDFs. With 8 bit values the maximum number of iterations would be 7. Try to have value2ptr point to the lesser of the two values to reduce iterations.

; Multiply two bytes in memory using Russian peasant algorithm
; by frantik


; Accepts: value1ptr and value2ptr, pointers to bytes in memory
;   value2ptr should point to the lesser of the two values 
;   for increased efficiency
; Uses: $00, $01, $02 for temporary variables
; Returns: 16 bit value in $00 and $01

.macro multiply value1ptr, value2ptr

ret  = $00			; return value
temp = $02			; temp storage

	lda #$00		; clear temporary variables
	sta ret
	sta ret+1
	sta temp
	jmp start:

-loop:
	asl value1ptr		; double first value
	rol temp		; using 16bit precision
	lsr value2ptr		; halve second vale
start:
	lda value2ptr		;
	and #01			; is new 2nd value an odd number?
	beq -loop:		; 
	clc			; if so, add new 1st value to running total
	lda ret			;
	adc value1ptr		;
	sta ret			;
	lda ret+1		;
	adc temp		;
	sta ret+1		;
	lda value2ptr		;
	cmp #01			; is 2nd value 1?  if so, we're done
	bne -loop:		; otherwise, loop
.endm