Greedy algorithm for Egyptian fractions: Difference between revisions
Content added Content deleted
(add RPL) |
|||
Line 2,928: | Line 2,928: | ||
largest denominator in the Egyptian fractions is 2847 digits is for 36/457 |
largest denominator in the Egyptian fractions is 2847 digits is for 36/457 |
||
</pre> |
</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> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |