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


A	IS	17
B	IS	34
 
pliar	IS 	$255		% designating main registers 
pliand	GREG
acc	GREG
str	IS	pliar		% reuse reg $255 for printing
 
	LOC	Data_Segment
	GREG	@
BUF	OCTA	#3030303030303030 % reserve a buffer that is big enough to hold
	OCTA	#3030303030303030 % a max (signed) 64 bit integer:
	OCTA	#3030300a00000000 %   2^63 - 1 = 9223372036854775807
				  % string is terminated with NL, 0
 
	LOC	#1000		% locate program at address
	GREG	@
halve	SR	pliar,pliar,1
	GO	$127,$127,0
 
double	SL	pliand,pliand,1	
	GO	$127,$127,0
 
odd	DIV	$77,pliar,2
	GET	$78,rR
	GO	$127,$127,0

				% Main is the entry point of the program
Main 	SET	pliar,A		% initialize registers for calculation
	SET	pliand,B
	SET	acc,0
1H	GO	$127,odd
	BZ	$78,2F		% if pliar is even skip incr. acc with pliand
	ADD	acc,acc,pliand	% 
2H	GO	$127,halve	% halve pliar
	GO	$127,double	% and double pliand
	PBNZ	pliar,1B	% repeat from 1H while pliar > 0
// result: acc = 17 x 34
// next: print result --> stdout
// $0 is a temp register
	LDA	str,BUF+19	% points after the end of the string 
2H	SUB	str,str,1	% update buffer pointer
	DIV	acc,acc,10	% do a divide and mod
	GET	$0,rR		% get digit from special purpose reg. rR
				% containing the remainder of the division
	INCL	$0,'0'		% convert to ascii
	STBU	$0,str		% place digit in buffer
	PBNZ	acc,2B		% next
				% 'str' points to the start of the result
	TRAP	0,Fputs,StdOut	% output answer to stdout
	TRAP	0,Halt,0	% exit