Greedy algorithm for Egyptian fractions: Difference between revisions
Content added Content deleted
(Add Factor example) |
|||
Line 138: | Line 138: | ||
Term max is 97/53 with 9 terms |
Term max is 97/53 with 9 terms |
||
Denominator max is 8/97 with 150 digits 57950...89665</pre> |
Denominator max is 8/97 with 150 digits 57950...89665</pre> |
||
=={{header|Factor}}== |
|||
<lang factor>USING: backtrack formatting fry kernel locals make math |
|||
math.functions math.ranges sequences ; |
|||
IN: rosetta-code.egyptian-fractions |
|||
: >improper ( r -- str ) >fraction "%d/%d" sprintf ; |
|||
: improper ( x y -- a b ) [ /i ] [ [ rem ] [ nip ] 2bi / ] 2bi ; |
|||
:: proper ( x y -- a b ) |
|||
y x / ceiling :> d1 1 d1 / y neg x rem y d1 * / ; |
|||
: expand ( a -- b c ) |
|||
>fraction 2dup > [ improper ] [ proper ] if ; |
|||
: egyptian-fractions ( x -- seq ) |
|||
[ [ expand [ , ] dip dup 0 = not ] loop drop ] { } make ; |
|||
: part1 ( -- ) |
|||
43/48 5/121 2014/59 [ |
|||
[ >improper ] [ egyptian-fractions ] bi |
|||
"%s => %[%u, %]\n" printf |
|||
] tri@ ; |
|||
: all-longest ( seq -- seq ) |
|||
dup longest length '[ length _ = ] filter ; |
|||
: (largest-denominator) ( seq -- n ) |
|||
[ denominator ] map supremum ; |
|||
: most-terms ( seq -- ) |
|||
all-longest [ [ sum ] map ] [ first length ] bi |
|||
"most terms: %[%u, %] => %d\n" printf ; |
|||
: largest-denominator ( seq -- ) |
|||
[ (largest-denominator) ] supremum-by |
|||
[ sum ] [ (largest-denominator) ] bi |
|||
"largest denominator: %u => %d\n" printf ; |
|||
: part2 ( -- ) |
|||
[ |
|||
99 [1,b] amb-lazy dup [1,b] amb-lazy swap / |
|||
egyptian-fractions |
|||
] bag-of [ most-terms ] [ largest-denominator ] bi ; |
|||
: egyptian-fractions-demo ( -- ) part1 part2 ; |
|||
MAIN: egyptian-fractions-demo</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 } |
|||
most terms: { 44/53, 8/97 } => 8 |
|||
largest denominator: 8/97 => 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665 |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |