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:

 Start the construction of a table of two columns: powers_of_2, and doublings; by a first row of a 1 (i.e. 2^0) in the first column and 1 times the divisor in the first row second column.
 Create the second row with columns of 2 (i.e 2^1), and 2 * divisor in order.
 Continue with successive i’th rows of 2^i and 2^i * divisor.
 Stop adding rows, and keep only those rows, where 2^i * divisor is less than or equal to the dividend.
 We now assemble two separate sums that both start as zero, called here answer and accumulator
 Consider each row of the table, in the reverse order of its construction.
 If the current value of the accumulator added to the doublings cell would be less than or equal to the dividend then add it to the accumulator, as well as adding the powers_of_2 cell value to the answer.
 When the first row has been considered as above, then the integer division of dividend by divisor is given by answer.
 (And the remainder is given by the absolute value of accumulator - dividend).


Example: 580 / 34

 Table creation: 



 powers_of_2

 doublings


 1

 34


 2

 68


 4

 136


 8

 272


 16

 544

 Initialization of sums: 



 powers_of_2

 doublings

 answer

 accumulator


 1

 34






 2

 68






 4

 136






 8

 272






 16

 544










 0

 0

 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.



 powers_of_2

 doublings

 answer

 accumulator


 1

 34






 2

 68






 4

 136






 8

 272






 16

 544

 16

 544



 powers_of_2

 doublings

 answer

 accumulator


 1

 34






 2

 68






 4

 136






 8

 272

 16

 544


 16

 544







 powers_of_2

 doublings

 answer

 accumulator


 1

 34






 2

 68






 4

 136

 16

 544


 8

 272






 16

 544







 powers_of_2

 doublings

 answer

 accumulator


 1

 34






 2

 68

 16

 544


 4

 136






 8

 272






 16

 544







 powers_of_2

 doublings

 answer

 accumulator


 1

 34

 17

 578


 2

 68






 4

 136






 8

 272






 16

 544





Answer

So 580 divided by 34 using the Egyptian method is 17 remainder (578 - 580) or 2.



Task

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.

 Functions should be clear interpretations of the algorithm.
 Use the function to divide 580 by 34 and show the answer here, on this page.


Related tasks

   Egyptian fractions


References

   Egyptian Number System


 
 
'---Ported from the c code example to BaCon by bigbass 
 
'==================================================================================
FUNCTION EGYPTIAN_DIVISION(long dividend, long divisor, long remainder) TYPE long 
'==================================================================================
'--- remainder is the third  parameter, pass 0 if you do not need the remainder
 
DECLARE powers[64] TYPE long 
DECLARE doublings[64] TYPE long 
 
	LOCAL i TYPE long
 
	FOR i = 0 TO  63 STEP 1  
		powers[i] = 1 << i
		doublings[i] = divisor << i
		IF (doublings[i] > dividend) THEN
			BREAK
		ENDIF
	NEXT
 
	LOCAL answer TYPE long
	LOCAL accumulator TYPE long
	answer = 0
	accumulator = 0
 
	WHILE i >= 0
		'--- If the current value of the accumulator added to the
		'--- doublings cell would be less than or equal to the
		'--- dividend then add it to the accumulator
		IF (accumulator + doublings[i] <= dividend) THEN
			accumulator = accumulator + doublings[i]
			answer = answer + powers[i]
		ENDIF
		DECR i
	WEND
 
	IF remainder THEN
		remainder = dividend - accumulator
		PRINT dividend ," / ", divisor, " = " , answer ," remainder " , remainder
 
        PRINT "Decoded the answer to a standard fraction"
        PRINT  (remainder + 0.0 )/ (divisor + 0.0) + answer
        PRINT
 
	ELSE 
		PRINT dividend ," / ", divisor , " = " , answer 
	ENDIF
 
	RETURN answer
 
ENDFUNCTION
 
 
	'--- the large number divided by the smaller number 
	'--- the third argument is 1 if you want to have a remainder
	'--- and 0 if you dont want to have a remainder 
 
	EGYPTIAN_DIVISION(580,34,1)
	EGYPTIAN_DIVISION(580,34,0)
 
EGYPTIAN_DIVISION(580,34,1)
 
 
 
 