Greedy algorithm for Egyptian fractions: Difference between revisions

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

Based on the VB.NET sample.<br>

Uses Algol 68G's LONG LONG INT for large integers.

<lang algol68>BEGIN # compute some Egytian fractions #

PR precision 2000 PR # set the number of digits for LONG LOG INT #

PROC gcd = ( LONG LONG INT a, b )LONG LONG INT:

IF b = 0 THEN

IF a < 0 THEN

- a

ELSE

a

FI

ELSE

gcd( b, a MOD b )

FI ; # gcd #

MODE RATIONAL = STRUCT( LONG LONG INT num, den );

MODE LISTOFRATIONAL = STRUCT( RATIONAL element, REF LISTOFRATIONAL next );

REF LISTOFRATIONAL nil list of rational = NIL;

OP TOSTRING = ( INT a )STRING: whole( a, 0 );

OP TOSTRING = ( LONG INT a )STRING: whole( a, 0 );

OP TOSTRING = ( LONG LONG INT a )STRING: whole( a, 0 );

OP TOSTRING = ( RATIONAL a )STRING:

IF den OF a = 1

THEN TOSTRING num OF a

ELSE TOSTRING num OF a + "/" + TOSTRING den OF a

FI ; # TOSTRING #

OP TOSTRING = ( REF LISTOFRATIONAL lr )STRING:

BEGIN

REF LISTOFRATIONAL p := lr;

STRING result := "[";

WHILE p ISNT nil list of rational DO

result +:= TOSTRING element OF p;

IF next OF p IS nil list of rational THEN

p := NIL

ELSE

p := next OF p;

result +:= " + "

FI

OD;

result + "]"

END ; # TOSTRING #

OP CEIL = ( LONG LONG REAL v )LONG LONG INT:

IF LONG LONG INT result := ENTIER v;

ABS v > ABS result

THEN result + 1

ELSE result

FI ; # CEIL #

OP EGYPTIAN = ( RATIONAL rp )REF LISTOFRATIONAL:

IF RATIONAL r := rp;

num OF r = 0 OR num OF r = 1

THEN HEAP LISTOFRATIONAL := ( r, nil list of rational )

ELSE

REF LISTOFRATIONAL result := nil list of rational;

REF LISTOFRATIONAL end result := nil list of rational;

PROC add = ( RATIONAL r )VOID:

IF end result IS nil list of rational THEN

result := HEAP LISTOFRATIONAL := ( r, nil list of rational );

end result := result

ELSE

next OF end result := HEAP LISTOFRATIONAL := ( r, nil list of rational );

end result := next OF end result

FI ; # add #

IF num OF r > den OF r THEN

add( RATIONAL( num OF r OVER den OF r, 1 ) );

r := ( num OF r MOD den OF r, den OF r )

FI;

PROC mod func = ( LONG LONG INT m, n )LONG LONG INT: ( ( m MOD n ) + n ) MOD n;

WHILE num OF r /= 0 DO

LONG LONG INT q = CEIL( den OF r / num OF r );

add( RATIONAL( 1, q ) );

r := RATIONAL( mod func( - ( den OF r ), num OF r ), ( den OF r ) * q )

OD;

result

FI ; # EGYPTIAN #

BEGIN # task test cases #

[]RATIONAL test cases = ( RATIONAL( 43, 48 ), RATIONAL( 5, 121 ), RATIONAL( 2014, 59 ) );

FOR r pos FROM LWB test cases TO UPB test cases DO

print( ( TOSTRING test cases[ r pos ], " -> ", TOSTRING EGYPTIAN test cases[ r pos ], newline ) )

OD;

# find the fractions with the most terms and the largest denominator #

print( ( "For rationals with numerator and denominator in 1..99:", newline ) );

RATIONAL largest denominator := ( 0, 1 );

REF LISTOFRATIONAL max denominator list := nil list of rational;

LONG LONG INT max denominator := 0;

RATIONAL most terms := ( 0, 1 );

REF LISTOFRATIONAL most terms list := nil list of rational;

INT max terms := 0;

FOR num TO 99 DO

FOR den TO 99 DO

RATIONAL r = RATIONAL( num, den );

REF LISTOFRATIONAL e := EGYPTIAN r;

REF LISTOFRATIONAL p := e;

INT terms := 0;

WHILE p ISNT nil list of rational DO

terms +:= 1;

IF den OF element OF p > max denominator THEN

largest denominator := r;

max denominator := den OF element OF p;

max denominator list := e

FI;

p := next OF p

OD;

IF terms > max terms THEN

most terms := r;

max terms := terms;

most terms list := e

FI

OD

OD;

print( ( " ", TOSTRING most terms, " has the most terms: ", TOSTRING max terms, newline

, " ", TOSTRING most terms list, newline

)

);

print( ( " ", TOSTRING largest denominator, " has the largest denominator:", newline

, " ", TOSTRING max denominator list, newline

)

)

END

END</lang>

{{out}}

<pre>

43/48 -> [1/2 + 1/3 + 1/16]

5/121 -> [1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225]

2014/59 -> [34 + 1/8 + 1/95 + 1/14947 + 1/670223480]

For rationals with numerator and denominator in 1..99:

97/53 has the most terms: 9

[1 + 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/697249399186783218655 + 1/1458470173998990524806872692984177836808420]

8/97 has the largest denominator:

[1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665]

</pre>