Greedy algorithm for Egyptian fractions: Difference between revisions

=={{header|Nim}}==

{{trans|Go}}

{{libheader|bignum}}

<lang Nim>import strformat, strutils

import bignum

let

Zero = newInt(0)

One = newInt(1)

#---------------------------------------------------------------------------------------------------

proc toEgyptianrecursive(rat: Rat; fracs: seq[Rat]): seq[Rat] =

if rat.isZero: return fracs

let iquo = cdiv(rat.denom, rat.num)

let rquo = newRat(1, iquo)

result = fracs & rquo

let num2 = cmod(-rat.denom, rat.num)

if num2 < Zero:

num2 += rat.num

let denom2 = rat.denom * iquo

let f = newRat(num2, denom2)

if f.num == One:

result.add(f)

else:

result = f.toEgyptianrecursive(result)

#---------------------------------------------------------------------------------------------------

proc toEgyptian(rat: Rat): seq[Rat] =

if rat.num.isZero: return @[rat]

if abs(rat.num) >= rat.denom:

let iquo = rat.num div rat.denom

let rquo = newRat(iquo, 1)

let rrem = rat - rquo

result = rrem.toEgyptianrecursive(@[rquo])

else:

result = rat.toEgyptianrecursive(@[])

#———————————————————————————————————————————————————————————————————————————————————————————————————

for frac in [newRat(43, 48), newRat(5, 121), newRat(2014, 59)]:

let list = frac.toEgyptian()

if list[0].denom == One:

let first = fmt"[{list[0].num}]"

let rest = list[1..^1].join(" + ")

echo fmt"{frac} -> {first} + {rest}"

else:

let all = list.join(" + ")

echo fmt"{frac} -> {all}"

for r in [98, 998]:

if r == 98:

echo "\nFor proper fractions with 1 or 2 digits:"

else:

echo "\nFor proper fractions with 1, 2 or 3 digits:"

var maxSize = 0

var maxSizeFracs: seq[Rat]

var maxDen = Zero

var maxDenFracs: seq[Rat]

var sieve = newSeq[seq[bool]](r + 1) # To eliminate duplicates.

for item in sieve.mitems: item.setLen(r + 2)

for i in 1..r:

for j in (i + 1)..(r + 1):

if sieve[i][j]: continue

let f = newRat(i, j)

let list = f.toEgyptian()

let listSize = list.len

if listSize > maxSize:

maxSize = listSize

maxSizeFracs.setLen(0)

maxSizeFracs.add(f)

elif listSize == maxSize:

maxSizeFracs.add(f)

let listDen = list[^1].denom()

if listDen > maxDen:

maxDen = listDen

maxDenFracs.setLen(0)

maxDenFracs.add(f)

elif listDen == maxDen:

maxDenFracs.add(f)

if i < r div 2:

var k = 2

while j * k <= r + 1:

sieve[i * k][j * k] = true

inc k

echo fmt" largest number of items = {maxSize}"

echo fmt" fraction(s) with this number : {maxSizeFracs.join("", "")}"

let md = $maxDen

echo fmt" largest denominator = {md.len} digits, {md[0..19]}...{md[^20..^1]}"

echo fmt" fraction(s) with this denominator : {maxDenFracs.join("", "")}"</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 proper fractions with 1 or 2 digits:

largest number of items = 8

fraction(s) with this number : 8/97, 44/53

largest denominator = 150 digits, 57950458706754280171...62011424993909789665

fraction(s) with this denominator : 8/97

For proper fractions with 1, 2 or 3 digits:

largest number of items = 13

fraction(s) with this number : 529/914, 641/796

largest denominator = 2847 digits, 83901882683345018663...38431266995525592705

fraction(s) with this denominator : 36/457, 529/914</pre>