Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 16:12, 12 December 2023
, 6 months agoAdded link to numberphile video
(Added link to numberphile video) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
Line 41:
;Also see:
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
* Numberphile YouTube video: [https://youtu.be/aVUUbNbQkbQ Egyptian Fractions and the Greedy Algorithm]
<br><br>
Line 459 ⟶ 460:
{{libheader|Boost}}
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<syntaxhighlight lang="cpp">#include <
#include <iostream>
#include <optional>
#include <sstream>
#include <
#include <vector>
typedef boost::multiprecision::cpp_int integer;
struct fraction {
fraction(const integer& n, const integer& d)
: numerator(n), denominator(d) {}
integer numerator;
integer denominator;
};
integer mod(const integer& x, const integer& y) { return ((x % y) + y) % y; }
size_t count_digits(const integer& i) {
Line 489:
os << i;
std::string s = os.str();
if (s.length() > max_digits)
s.replace(max_digits
return s;
}
Line 503 ⟶ 502:
integer x = f.numerator, y = f.denominator;
while (x > 0) {
integer z = (y + x - 1) / x;
result.emplace_back(1, z);
x = mod(-y, x);
Line 524 ⟶ 523:
integer x = f.numerator, y = f.denominator;
if (x > y) {
std::cout << "[" << x / y << "] ";
x = x % y;
}
Line 557 ⟶ 556:
}
}
std::cout
<< "Proper fractions with most terms and largest denominator, limit = "
<< limit << ":\n\n";
std::cout << "Most terms (" << max_terms
<< "): " << max_terms_fraction.value() << " = ";
print_egyptian(max_terms_result);
std::cout << "\nLargest denominator ("
<< " digits): " << max_denominator_fraction.value() << " = ";
print_egyptian(max_denominator_result);
}
Line 1,116 ⟶ 1,119:
{{FormulaeEntry|page=https://formulae.org/?script=examples/Egyptian_fractions}}
'''Solution'''
[[File:Fōrmulæ - Egyptian fractions 01.png]]
'''Test cases part 1'''
[[File:Fōrmulæ - Egyptian fractions 02.png]]
[[File:Fōrmulæ - Egyptian fractions 03.png]]
[[File:Fōrmulæ - Egyptian fractions 04.png]]
[[File:Fōrmulæ - Egyptian fractions 05.png]]
[[File:Fōrmulæ - Egyptian fractions 06.png]]
[[File:Fōrmulæ - Egyptian fractions 07.png]]
'''Test cases part 2'''
[[File:Fōrmulæ - Egyptian fractions 08.png]]
[[File:Fōrmulæ - Egyptian fractions 09.png]]
[[File:Fōrmulæ - Egyptian fractions 10.png]]
[[File:Fōrmulæ - Egyptian fractions 11.png]]
[[File:Fōrmulæ - Egyptian fractions 12.png]]
[[File:Fōrmulæ - Egyptian fractions 13.png]]
[[File:Fōrmulæ - Egyptian fractions 14.png]]
=={{header|Go}}==
Line 2,928 ⟶ 2,965:
largest denominator in the Egyptian fractions is 2847 digits is for 36/457
</pre>
=={{header|RPL}}==
<code>GCD</code> is defined at [[Greatest common divisor#RPL|Greatest common divisor]]
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪
DUP IM LAST RE / CEIL
SWAP RE LAST IM DUP NEG ROT MOD
SWAP 3 PICK *
DUP2 <span style="color:blue">GCD</span> ROT OVER / ROT ROT / R→C
≫ '<span style="color:blue">SPLIT</span>' STO
≪
DUP 3 EXGET SWAP 1 EXGET
'''IF''' DUP2 > '''THEN'''
SWAP OVER MOD LAST / IP SWAP ROT
'''ELSE''' 0 ROT ROT '''END'''
R→C
'''WHILE''' DUP RE '''REPEAT'''
<span style="color:blue">SPLIT</span>
"'1/" ROT →STR + "'" + STR→
ROT SWAP + SWAP
'''END'''
≫ '<span style="color:blue">EGYPF</span>' STO
|
<span style="color:blue">SPLIT</span> ''( (x1,y1) → n1 (x2,y2) ) ''
n1 = ceil(y1/x1)
x2 = mod(-y1,x1)
y2 = n1*y1
simplify x2/y2
<span style="color:blue">EGYPF</span> ''( 'x/y' → 'sum_of_Egyptian_fractions') ''
put x and y in stack
if x > y
first term of sum is x//y and x = mod(x,y)
else first term is 0
convert to complex to ease handling in stack
loop while x<sub>k</sub> ≠ 0
get n<sub>k</sub> and (x<sub>k</sub>, y<sub>k</sub>)
convert n<sub>k</sub> into '1/n<sub>k</sub>'
add '1/n<sub>k</sub>' to the sum
end loop
return sum
|}
'43/48' <span style="color:blue">EGYPF</span>
'5/121' <span style="color:blue">EGYPF</span>
'2014/59' <span style="color:blue">EGYPF</span>
{{out}}
<pre>
3: 'INV(2)+INV(3)+INV(16)'
2: 'INV(25)+INV(757)+INV(763309)+INV(873960180913)+INV(1.52761279564E+24)'
1: '34+INV(8)+INV(95)+INV(14947)+INV(670223480)'
</pre>
In algebraic expressions, RPL automatically replaces <code>1/n</code> by <code>INV(n)</code>
====Quest for the largest number of items for proper fractions 2.99/2..99====
≪ '1/1' 0
2 99 '''FOR''' d 2 d 1 - '''FOR''' n
"'" n →STR + "/" + d →STR + "'" + STR→
DUP <span style="color:blue">EGYPF</span> SIZE → f sf
≪ '''IF''' sf OVER > '''THEN''' DROP2 f sf '''END''' ≫
'''NEXT NEXT''' DROP
≫ '<span style="color:blue">TASK</span>'
{{out}}
<pre>
1: '44/53'
</pre>
Limited precision of basic RPL prevents from searching the largest denominator.
=={{header|Ruby}}==
Line 3,660 ⟶ 3,769:
{{libheader|Wren-big}}
We use the BigRat class in the above module to represent arbitrary size fractions.
<syntaxhighlight lang="
var toEgyptianHelper // recursive
| |||