Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 17:25, 3 August 2019
, 4 years ago→{{header|Phix}}: bigatom -> mpfr
m (→{{header|Phix}}: bigatom -> mpfr) |
|||
Line 1,672:
=={{header|Phix}}==
{{trans|tcl}}
{{libheader|
The sieve copied from Go
<lang Phix>include
function egyptian(integer num, denom)
t = mpz_init()
sequence result = {}
while mpz_cmp_si(n,0)!=
result = append(result,"1/"&mpz_get_str(t))
mpz_neg(d,d)
mpz_mul(d,d,t)
end while
{n,d} = mpz_free({n,d})
return result
end function
Line 1,696 ⟶ 1,699:
prefix = sprintf("[%d] + ",whole)
end if
▲ printf(1,"%d/%d -> %s\n",{num, denom, prefix & join(s," + ")})
end procedure
Line 1,704 ⟶ 1,706:
efrac(5,121)
efrac(2014,59)
integer maxt = 0▼
string maxts = ""▼
integer maxd = 0▼
string maxds = ""▼
▲integer maxt = 0,
▲string maxts = "",
maxda = ""
for r=98 to 998 by 900 do -- (iterates just twice!)
sequence sieve = repeat(repeat(false,r+1),r) -- to eliminate duplicates
Line 1,725 ⟶ 1,727:
maxts &= ", " & term
end if
integer mlen = length(
if mlen>maxd then
maxd = mlen
Line 1,733 ⟶ 1,735:
maxds &= ", " & term
end if
if n
for k=2 to 9999 do
if d*k > r+1 then exit end if
Line 1,742 ⟶ 1,744:
end for
end for
printf(1,"\nfor proper fractions with 1 to %d digits\n",{length(sprint(r))})
printf(1,"Largest number of terms is %d for %s\n",{maxt,maxts})
maxda = maxda[3..$] -- (strip the "1/")
printf(1,"Largest size for denominator is %d digits (%s) for %s\n",{maxd,
end for</lang>
{{out}}
|