Problem Statement

Egyptian division is a method of dividing integers using addition and doubling that is similar to the algorithm of Ethiopian multiplication Algorithm: Given two numbers where the dividend is to be divided by the divisor:

Example: 580 / 34 Table creation: Initialization of sums: Considering table rows, bottom-up: When a row is considered it is shown crossed out if it is not accumulated, or bold if the row causes summations. So 580 divided by 34 using the Egyptian method is 17 remainder (578 - 580) or 2.

The task is to create a function that does Egyptian division. The function should closely follow the description above in using a list/array of powers of two, and another of doublings.

Let's start with the solution:

divident := 580
divisor := 34

answer := accumulator := 0
obj := []	, div := divisor

while (div < divident)
{
	obj[2**(A_Index-1)] := div				; obj[powers_of_2] := doublings
	div *= 2						; double up
}

while obj.MaxIndex()						; iterate rows "in the reverse order"
{
	if (accumulator + obj[obj.MaxIndex()] <= divident)	; If (accumulator + current doubling) <= dividend 
	{
		accumulator += obj[obj.MaxIndex()]		; add current doubling to the accumulator
		answer += obj.MaxIndex()			; add the powers_of_2 value to the answer.
	}
	obj.pop()						; remove current row
}
MsgBox % divident "/" divisor " = " answer ( divident-accumulator > 0 ? " r" divident-accumulator : "")