Ethiopian multiplication is a method of multiplying integers using only addition, doubling, and halving.


Method:

 Take two numbers to be multiplied and write them down at the top of two columns.
 In the left-hand column repeatedly halve the last number, discarding any remainders, and write the result below the last in the same column, until you write a value of 1.
 In the right-hand column repeatedly double the last number and write the result below. stop when you add a result in the same row as where the left hand column shows 1.
 Examine the table produced and discard any row where the value in the left column is even.
 Sum the values in the right-hand column that remain to produce the result of multiplying the original two numbers together

For example:   17 × 34

       17    34

Halving the first column:

       17    34
        8
        4
        2
        1

Doubling the second column:

       17    34
        8    68
        4   136 
        2   272
        1   544

Strike-out rows whose first cell is even:

       17    34
        8    68 
        4   136 
        2   272 
        1   544

Sum the remaining numbers in the right-hand column:

       17    34
        8    -- 
        4   --- 
        2   --- 
        1   544
           ====
            578

So 17 multiplied by 34, by the Ethiopian method is 578.



Task

The task is to define three named functions/methods/procedures/subroutines:

 one to halve an integer,
 one to double an integer, and
 one to state if an integer is even.


Use these functions to create a function that does Ethiopian multiplication.



References

Ethiopian multiplication explained (BBC Video clip)
A Night Of Numbers - Go Forth And Multiply (Video)
Russian Peasant Multiplication
Programming Praxis: Russian Peasant Multiplication


	org	100h
	jmp	demo
	;;;	HL = BC * DE
	;;;	BC is left column, DE is right column
emul:	lxi	h,0	; HL will be the accumulator
 
ztest:	mov	a,b	; Check if the left column is zero.
	ora	c	; If so, stop.
	rz 
 
halve:	mov	a,b	; Halve BC by rotating it right.
	rar		; We know the carry is zero here because of the ORA.
	mov	b,a	; So rotate the top half first,
	mov	a,c	; Then the bottom half
	rar		; This leaves the old low bit in the carry flag,
	mov	c,a	; so this also lets us do the even/odd test in one go.
 
even:	jnc	$+4	; If no carry, the number is even, so skip (strikethrough)
	dad	d	; But if odd, add the number in the right column
 
double:	xchg		; Doubling DE is a bit easier since you can add
	dad	h	; HL to itself in one go, and XCHG swaps DE and HL 
	xchg
 
	jmp	ztest	; We want to do the whole thing again until BC is zero
 
	;;;	Demo code, print 17 * 34
demo:	lxi	b,17	; Load 17 into BC (left column)
	lxi	d,34	; Load 34 into DE (right column)
	call	emul	; Do the multiplication
 
print:	lxi	b,-10	; Decimal output routine (not very interesting here,
	lxi	d,pbuf	; but without it you can't see the result)
	push	d
digit:	lxi 	d,-1
dloop:	inx	d
	dad	b
	jc	dloop
	mvi	a,58
	add	l
	pop	h
	dcx	h
	mov	m,a
	push 	h
	xchg
	mov	a,h
	ora	l
	jnz	digit
	pop	d
	mvi	c,9
	jmp	5
	db	'*****'
pbuf:	db	'$'