Anonymous user
Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 18:48, 20 April 2014
, 10 years ago+ D entry
m (Note about another 8-term find) |
(+ D entry) |
||
Line 26:
;Also see:
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
=={{header|D}}==
Assuming the Python entry is correct, this code is equivalent. This requires the D module of the Arithmetic/Rational task.
{{trans|Python}}
<lang d>import std.stdio, std.bigint, std.algorithm, std.range, std.conv,
arithmetic_rational: Rat = Rational;
Rat[] egyptian(Rat r) pure /*nothrow*/ {
typeof(return) result;
if (r >= 1) {
if (r.denominator == 1)
return [r, Rat(0, 1)];
result = [Rat(r.numerator / r.denominator, 1)];
r -= result[0];
}
static enum mod = (in BigInt m, in BigInt n) pure /*nothrow*/ =>
((m % n) + n) % n;
while (r.numerator != 1) {
immutable q = (r.denominator + r.numerator - 1) / r.numerator;
result ~= Rat(1, q);
r = Rat(mod(-r.denominator, r.numerator), r.denominator * q);
}
result ~= r;
return result;
}
void main() {
foreach (immutable r; [Rat(43, 48), Rat(5, 121), Rat(2014, 59)])
writefln("%s => %(%s %)", r, r.egyptian);
Tuple!(size_t, Rat) lenMax;
Tuple!(BigInt, Rat) denomMax;
foreach (immutable r; iota(1, 100).cartesianProduct(iota(1, 100))
.map!(nd => nd[].Rat).array.sort().uniq) {
immutable e = r.egyptian;
immutable eLen = e.length;
immutable eDenom = e.back.denominator;
if (eLen > lenMax[0])
lenMax = tuple(eLen, r);
if (eDenom > denomMax[0])
denomMax = tuple(eDenom, r);
}
writefln("Term max is %s with %d terms", lenMax[1], lenMax[0]);
immutable dStr = denomMax[0].text;
writefln("Denominator max is %s with %d digits %s...%s",
denomMax[1], dStr.length, dStr[0 .. 5], dStr[$ - 5 .. $]);
}</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
Term max is 97/53 with 9 terms
Denominator max is 8/97 with 150 digits 57950...89665</pre>
=={{header|Perl 6}}==
| |||