Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 22:27, 14 November 2018
, 5 years agoAdd Factor example
(Add Factor example) |
|||
Line 138:
Term max is 97/53 with 9 terms
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}}==
{{libheader|GMP}}
| |||