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


option explicit
 
class List
	private theList
	private nOccupiable
	private nTop
 
	sub class_initialize
		nTop = 0
		nOccupiable = 100
		redim theList( nOccupiable )
	end sub
 
	public sub store( x )
		if nTop >= nOccupiable then
			nOccupiable = nOccupiable + 100
			redim preserve theList( nOccupiable )
		end if
		theList( nTop ) = x
		nTop = nTop + 1
	end sub
 
	public function recall( n )
		if n >= 0 and n <= nOccupiable then
			recall = theList( n )
		else
			err.raise vbObjectError + 1000,,"Recall bounds error"
		end if
	end function
 
	public sub replace( n, x )
		if n >= 0 and n <= nOccupiable then
			theList( n )  = x
		else
			err.raise vbObjectError + 1001,,"Replace bounds error"
		end if
	end sub
 
	public property get listCount
		listCount = nTop
	end property
 
end class
 
function halve( n )
	halve = int( n / 2 )
end function
 
function twice( n )
	twice = int( n * 2 )
end function
 
function iseven( n )
	iseven = ( ( n mod 2 ) = 0 )
end function
 
 
function multiply( n1, n2 )
	dim LL
	set LL = new List
 
	dim RR
	set RR = new List
 
	LL.store n1
	RR.store n2
 
	do while n1 <> 1
		n1 = halve( n1 )
		LL.store n1
		n2 = twice( n2 )
		RR.store n2
	loop
 
	dim i
	for i = 0 to LL.listCount
		if iseven( LL.recall( i ) ) then
			RR.replace i, 0
		end if
	next
 
	dim total
	total = 0
	for i = 0 to RR.listCount
		total = total + RR.recall( i )
	next
 
	multiply = total
end function
 