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


	extern 	printf
	global	main
 
	section	.text
 
halve
	shr	ebx, 1
	ret
 
double
	shl	ebx, 1
	ret
 
iseven
	and	ebx, 1
	cmp	ebx, 0
	ret			; ret preserves flags
 
main
	push	1		; tutor = true
	push	34		; 2nd operand
	push	17		; 1st operand
	call	ethiopicmult
	add	esp, 12
 
	push	eax		; result of 17*34
	push	fmt
	call	printf
	add	esp, 8
 
	ret
 
 
%define plier 8
%define plicand 12
%define tutor 16
 
ethiopicmult
	enter	0, 0
	cmp	dword [ebp + tutor], 0
	je	.notut0
	push	dword [ebp + plicand]
	push	dword [ebp + plier]
	push	preamblefmt
	call	printf
	add	esp, 12
.notut0
 
	xor	eax, eax		; eax -> result
	mov	ecx, [ebp + plier] 	; ecx -> plier
	mov	edx, [ebp + plicand]    ; edx -> plicand
 
.whileloop
	cmp	ecx, 1
	jl	.multend
	cmp	dword [ebp + tutor], 0
	je	.notut1
	call	tutorme
.notut1
	mov	ebx, ecx
	call	iseven
	je	.iseven
	add	eax, edx	; result += plicand
.iseven
	mov	ebx, ecx	; plier >>= 1
	call	halve
	mov	ecx, ebx
 
	mov	ebx, edx	; plicand <<= 1
	call	double
	mov	edx, ebx
 
	jmp	.whileloop
.multend
	leave
	ret
 
 
tutorme
	push	eax
	push	strucktxt
	mov	ebx, ecx
	call	iseven
	je	.nostruck
	mov	dword [esp], kepttxt
.nostruck
	push	edx
	push	ecx
	push	tutorfmt
	call	printf
	add	esp, 4
	pop	ecx
	pop	edx
	add	esp, 4
	pop	eax
	ret
 
	section .data
 
fmt
	db	"%d", 10, 0
preamblefmt
	db	"ethiopic multiplication of %d and %d", 10, 0
tutorfmt
	db	"%4d %6d %s", 10, 0
strucktxt
	db	"struck", 0
kepttxt
	db	"kept", 0