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:

function egyptian_divmod(dividend,divisor)
    local pwrs, dbls = {1}, {divisor}
    while dbls[#dbls] <= dividend do
        table.insert(pwrs, pwrs[#pwrs] * 2)
        table.insert(dbls, pwrs[#pwrs] * divisor)
    end
    local ans, accum = 0, 0

    for i=#pwrs-1,1,-1 do
        if accum + dbls[i] <= dividend then
            accum = accum + dbls[i]
            ans = ans + pwrs[i]
        end
    end

    return ans, math.abs(accum - dividend)
end

local i, j = 580, 34
local d, m = egyptian_divmod(i, j)
print(i.." divided by "..j.." using the Egyptian method is "..d.." remainder "..m)