How to resolve the algorithm Egyptian division step by step in the ALGOL 68 programming language

Published on 12 May 2024 09:40 PM
#Algol 68

How to resolve the algorithm Egyptian division step by step in the ALGOL 68 programming language

Table of Contents

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:

Step by Step solution about How to resolve the algorithm Egyptian division step by step in the ALGOL 68 programming language

Source code in the algol programming language

BEGIN
    # performs Egyptian division of dividend by divisor, setting quotient and remainder #
    # this uses 32 bit numbers, so a table of 32 powers of 2 should be sufficient       #
    # ( divisors > 2^30 will probably overflow - this is not checked here )             #
    PROC egyptian division = ( INT dividend, divisor, REF INT quotient, remainder )VOID:
         BEGIN
            [ 1 : 32 ]INT powers of 2, doublings;
            # initialise the powers of 2 and doublings tables #
            powers of 2[ 1 ] := 1;
            doublings  [ 1 ] := divisor;
            INT   table pos  := 1;
            WHILE table pos +:= 1;
                  powers of 2[ table pos ] := powers of 2[ table pos - 1 ] * 2;
                  doublings  [ table pos ] := doublings  [ table pos - 1 ] * 2;
                  doublings[ table pos ] <= dividend
            DO
                SKIP
            OD;
            # construct the accumulator and answer #
            INT accumulator := 0, answer := 0;
            WHILE table pos >=1
            DO
                IF ( accumulator + doublings[ table pos ] ) <= dividend
                THEN
                    accumulator +:= doublings  [ table pos ];
                    answer      +:= powers of 2[ table pos ] 
                FI;
                table pos -:= 1
            OD;
            quotient  := answer;
            remainder := ABS ( accumulator - dividend )
        END # egyptian division # ;

    # task test case #
    INT quotient, remainder;
    egyptian division( 580, 34, quotient, remainder );
    print( ( "580 divided by 34 is: ", whole( quotient, 0 ), " remainder: ", whole( remainder, 0 ), newline ) )
END

You may also check:How to resolve the algorithm Integer overflow step by step in the C++ programming language
You may also check:How to resolve the algorithm Binary strings step by step in the zkl programming language
You may also check:How to resolve the algorithm Convert seconds to compound duration step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Sum and product of an array step by step in the LiveCode programming language
You may also check:How to resolve the algorithm Repeat a string step by step in the Amazing Hopper programming language