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:

USING: assocs combinators formatting kernel make math sequences ;
IN: rosetta-code.egyptian-division

: table ( dividend divisor -- table )
    [ [ 2dup >= ] [ dup , 2 * ] while ] { } make 2nip
    dup length <iota> [ 2^ ] map zip <reversed> ;

: accum ( a b dividend -- c )
    [ 2dup [ first ] bi@ + ] dip < [ [ + ] 2map ] [ drop ] if ;

: ediv ( dividend divisor -- quotient remainder )
    {
        [ table ]
        [ 2drop { 0 0 } ]
        [ drop [ accum ] curry reduce first2 swap ]
        [ drop - abs ] 
    } 2cleave ;

580 34 ediv "580 divided by 34 is %d remainder %d\n" printf