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 &8000
 
	ld hl,17
	call Halve_Until_1
 
	push bc
	ld hl,34
	call Double_Until_1
	pop bc
 
	call SumOddEntries
	;returns Ethiopian product in IX.
 
	call NewLine
 
	call Primm
	byte "0x",0
 
	push ix
	pop hl
 
	ld a,H
	call ShowHex	
	;Output should be in decimal but hex is easier.
	ld a,L
	call ShowHex
 
	ret
 
 
Halve_Until_1:
	;input: HL = number you wish to halve. HL is unsigned.
	ld de,Column_1
	ld a,1
	ld (Column_1),HL
	inc de
	inc de
loop_HalveUntil_1:
	SRL H
	RR L
	inc b
	push af
		ld a,L
		ld (de),a
		inc de
		ld a,H
		ld (de),a
		inc de
	pop af
	CP L
	jr nz,loop_HalveUntil_1
	;b tracks how many times to double the second factor.
	ret
 
Double_Until_1:
	;doubles second factor B times. B is calculated by Halve_until_1
	ld de,Column_2
	ld (Column_2),HL
	inc de
	inc de
loop_double_until_1:
	SLA L
	RL H
	PUSH AF
		LD A,L
		LD (DE),A
		INC DE
		LD A,H
		LD (DE),A
		INC DE
	POP AF
	DJNZ loop_double_until_1
	ret
 
 
SumOddEntries:
	sla b			;double loop counter, this is also the offset to the "last" entry of
					;each table
	ld h,>Column_1
	ld d,>Column_2	;aligning the tables lets us get away with this.
	ld l,b
	ld e,b
	ld ix,0
loop:
	ld a,(hl)
	rrca	;we only need the result of the odd/even test.
	jr nc,skipEven
	push hl
	push de
		ld a,(de)
		ld L,a
		inc de
		ld a,(de)
		ld H,a
		ex de,hl
		add ix,de
	pop de
	pop hl
skipEven:
	dec de
	dec de
	dec hl
	dec hl
	djnz loop
	ret	;ix should contain the answer
 
 
	align 8		;aligns Column_1 to the nearest 256 byte boundary. This makes offsetting easier.
Column_1:
	ds 16,0
 
	align 8		;aligns Column_2 to the nearest 256 byte boundary. This makes offsetting easier.
Column_2:
	ds 16,0