Engel expansion: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Raku}}: remove some intermediate variables, slightly more compact) |
|||
Line 93: | Line 93: | ||
0.0+sq2_179-from_engle to_engle sq2_179 |
0.0+sq2_179-from_engle to_engle sq2_179 |
||
9.66281e_196</lang> |
9.66281e_196</lang> |
||
=={{header|Phix}}== |
|||
<!--<lang Phix>(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #7060A8;">mpfr_set_default_precision</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">180</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- see notes</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">toEngel</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">engel</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #004080;">mpfr</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpfr_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">engel</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">70</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #7060A8;">mpfr_si_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpfr_ceil</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">engel</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">mpfr_get_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpfr_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpfr_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">engel</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">fromEngel</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">engel</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">mpfr</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">e</span> <span style="color: #008080;">in</span> <span style="color: #000000;">engel</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #7060A8;">mpfr_set_d</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpfr_si_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpfr_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpfr_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">rats</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> |
|||
<span style="color: #008000;">"3.14159265358979"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"2.71828182845904"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"1.414213562373095"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"7.59375"</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #008000;">"3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823"</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #008000;">"2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743"</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #008000;">"1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387"</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #008000;">"25.628906"</span> |
|||
<span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">rat</span> <span style="color: #008080;">in</span> <span style="color: #000000;">rats</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Rational number : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rat</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">engel</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">toEngel</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rat</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">dix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'.'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rat</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">places</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rat</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">dix</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">engel</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">cp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_get_fixed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fromEngel</span><span style="color: #0000FF;">(</span><span style="color: #000000;">engel</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">places</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">places</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">dix</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">rat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dix</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dix</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">cp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Engel expansion : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">engel</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">)],</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Number of terms : %d, places : %d (%d correct)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">places</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cp</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Back to rational: %s\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</lang>--> |
|||
{{out}} |
|||
I could only get pi accurate to 125 decimal places and root2 to 87, so cut the input strings accordingly, and later |
|||
had to lop another 10 dp off pi to avoid a crash under p2js.<br> |
|||
In fact the 1 digit error on desktop/Phix (below) don't happen in a browser. Increasing the precision helps but only up to a (relatively small) point. <br> |
|||
You may or may not have better luck with completely rewriting this to use mpq (rationals). |
|||
<pre> |
|||
Rational number : 3.14159265358979 |
|||
Engel expansion : 1 1 1 8 8 17 19 300 1991 2768 4442 4830 10560 37132 107315 244141 651042 1953125 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 |
|||
Number of terms : 70, places : 14 (14 correct) |
|||
Back to rational: 3.14159265358979 |
|||
Rational number : 2.71828182845904 |
|||
Engel expansion : 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 82 144 321 2289 9041 21083 474060 887785 976563 1953125 2147483647 2147483647 2147483647 |
|||
Number of terms : 70, places : 14 (14 correct) |
|||
Back to rational: 2.71828182845904 |
|||
Rational number : 1.414213562373095 |
|||
Engel expansion : 1 3 5 5 16 18 78 102 120 144 260 968 18531 46065 63005 65105 78125 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 |
|||
Number of terms : 70, places : 15 (15 correct) |
|||
Back to rational: 1.414213562373095 |
|||
Rational number : 7.59375 |
|||
Engel expansion : 1 1 1 1 1 1 1 2 6 8 |
|||
Number of terms : 10, places : 5 (5 correct) |
|||
Back to rational: 7.59375 |
|||
Rational number : 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823 |
|||
Engel expansion : 1 1 1 8 8 17 19 300 1991 2492 7236 10586 34588 63403 70637 1236467 5417668 5515697 5633167 7458122 9637848 9805775 41840855 58408380 213130873 460586654 1017925067 1626739591 2147483647 2147483647 |
|||
Number of terms : 70, places : 115 (115 correct) |
|||
Back to rational: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823 |
|||
Rational number : 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 |
|||
Engel expansion : 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|||
Number of terms : 70, places : 101 (100 correct) |
|||
Back to rational: 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742 |
|||
Rational number : 1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387 |
|||
Engel expansion : 1 3 5 5 16 18 78 102 120 144 251 363 1402 31169 88630 184655 259252 298770 4196070 38538874 616984563 1975413038 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 |
|||
Number of terms : 70, places : 87 (87 correct) |
|||
Back to rational: 1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387 |
|||
Rational number : 25.628906 |
|||
Engel expansion : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 33 33 35 |
|||
Number of terms : 54, places : 6 (6 correct) |
|||
Back to rational: 25.628906 |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
Revision as of 00:25, 19 August 2022
The Engel expansion of a positive real number x is the unique non-decreasing sequence of positive integers { a1, a2, a3 ... } such that
x = 1 / a1 + 1 / a1a2 + 1 / a1a2a3 ...
In other words, each term is the reciprocal of the cumulative product of the expansion and x is the sum of those terms.
Rational numbers have a finite Engel expansion, while irrational numbers have an infinite Engel expansion.
Tiny amounts of imprecision can cause wild variation from actual values as the (reciprocal) terms grow smaller. It can be quite challenging to maintain precision in later terms.
- Task
- Write routines (functions, procedures, whatever it may be called in your language) to convert a rational number to an Engel expansion representation and from an Engle expansion to a rational number.
- Demonstrate converting some rational numbers to an Engel expansion and back.
Test it with at least the following rational approximations of:
- 𝜋 - 3.14159265358979
- 𝑒 - 2.71828182845904
- √2 - 1.414213562373095
- Stretch
- If your language supports high precision rational numbers, do the same with at least:
- 𝜋 - 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211
- 𝑒 - 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743
- √2 - 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558
There almost definitely will be some imprecision in the later terms. Feel free to limit the display of the expansion to the first 30 terms.
- See also
J
<lang J>to_engle=: {{ r=. i.0 while. y * 30>:#r do. y=. _1+y*{:r=. r, >.%y end. r }}
from_engle=: Template:+/%*/\y</lang>
Task examples:<lang J> to_engle 3.14159265358979 1 1 1 8 8 17 19 300 1991 2767 8641 16313 1628438 7702318 25297938 431350188 765676622 776491263 1739733589 2329473788 6871947674 17179869184
from_engle to_engle 3.14159265358979
3.14159
3.14159265358979-from_engle to_engle 3.14159265358979
0
to_engle 2.71828182845904
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 60 89 126 565 686 1293 7419 13529 59245 65443 133166 225384 655321 656924
from_engle to_engle 2.71828182845904
2.71828
2.71828182845904-from_engle to_engle 2.71828182845904
0
to_engle 1.414213562373095
1 3 5 5 16 18 78 102 120 144 277 286 740 38370 118617 120453 169594 5696244 6316129 10129640 67108864
from_engle to_engle 1.414213562373095
1.41421
1.414213562373095-from_engle to_engle 1.414213562373095
0</lang> (by default, J displays the first six digits of floating point numbers)
Stretch goal (note that we seem to have a problem here with e, presumably because of the limited length of the series):<lang j> pi175=: (%10x^175)*<.@o.10x^175
e101=: +/ %@!@i. 101x sq2_179=: (10x^179)%~<.@%:2*10x^2*179 177j175":pi175
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211
103j101":e101
2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743
180j178":sq2_179
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558
to_engle pi175
1 1 1 8 8 17 19 300 1991 2492 7236 10586 34588 63403 70637 1236467 5417668 5515697 5633167 7458122 9637848 9805775 41840855 58408380 213130873 424342175 2366457522 4109464489 21846713216 27803071890 31804388758
to_engle e101
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
to_engle sq2_179
1 3 5 5 16 18 78 102 120 144 251 363 1402 31169 88630 184655 259252 298770 4196070 38538874 616984563 1975413035 5345718057 27843871197 54516286513 334398528974 445879679626 495957494386 2450869042061 2629541150828 3557465729164
0.0+pi175-from_engle to_engle pi175
8.21074e_177
0.0+e101-from_engle to_engle e101
1.25532e_34
0.0+sq2_179-from_engle to_engle sq2_179
9.66281e_196</lang>
Phix
with javascript_semantics include mpfr.e mpfr_set_default_precision(-180) -- see notes function toEngel(string x) sequence engel = {} mpfr u = mpfr_init(x), a = mpfr_init() while mpfr_cmp_si(u,0)!=0 and length(engel)<70 do mpfr_si_div(a,1,u) mpfr_ceil(a,a) engel &= mpfr_get_si(a) mpfr_mul(u,u,a) mpfr_sub_si(u,u,1) end while return engel end function function fromEngel(sequence engel) mpfr res = mpfr_init(0), prod = mpfr_init(1), r = mpfr_init() for e in engel do mpfr_set_d(r,e) mpfr_si_div(r,1,r) mpfr_mul(prod,prod,r) mpfr_add(res,res,prod) end for return res end function constant rats = { "3.14159265358979", "2.71828182845904", "1.414213562373095", "7.59375", "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823", "2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743", "1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387", "25.628906" } for rat in rats do printf(1,"Rational number : %s\n", rat) sequence engel = toEngel(rat) integer dix = find('.',rat), places = length(rat)-dix, l = length(engel), cp = 0 string s = mpfr_get_fixed(fromEngel(engel), places) for i=1 to places do dix += 1 if rat[dix]!=s[dix] then exit end if cp = i end for printf(1,"Engel expansion : %s\n", join(engel[1..min(l,30)]," ",fmt:="%d")) printf(1,"Number of terms : %d, places : %d (%d correct)\n", {l,places,cp}) printf(1,"Back to rational: %s\n\n", s) end for
- Output:
I could only get pi accurate to 125 decimal places and root2 to 87, so cut the input strings accordingly, and later
had to lop another 10 dp off pi to avoid a crash under p2js.
In fact the 1 digit error on desktop/Phix (below) don't happen in a browser. Increasing the precision helps but only up to a (relatively small) point.
You may or may not have better luck with completely rewriting this to use mpq (rationals).
Rational number : 3.14159265358979 Engel expansion : 1 1 1 8 8 17 19 300 1991 2768 4442 4830 10560 37132 107315 244141 651042 1953125 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 Number of terms : 70, places : 14 (14 correct) Back to rational: 3.14159265358979 Rational number : 2.71828182845904 Engel expansion : 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 82 144 321 2289 9041 21083 474060 887785 976563 1953125 2147483647 2147483647 2147483647 Number of terms : 70, places : 14 (14 correct) Back to rational: 2.71828182845904 Rational number : 1.414213562373095 Engel expansion : 1 3 5 5 16 18 78 102 120 144 260 968 18531 46065 63005 65105 78125 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 Number of terms : 70, places : 15 (15 correct) Back to rational: 1.414213562373095 Rational number : 7.59375 Engel expansion : 1 1 1 1 1 1 1 2 6 8 Number of terms : 10, places : 5 (5 correct) Back to rational: 7.59375 Rational number : 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823 Engel expansion : 1 1 1 8 8 17 19 300 1991 2492 7236 10586 34588 63403 70637 1236467 5417668 5515697 5633167 7458122 9637848 9805775 41840855 58408380 213130873 460586654 1017925067 1626739591 2147483647 2147483647 Number of terms : 70, places : 115 (115 correct) Back to rational: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823 Rational number : 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 Engel expansion : 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Number of terms : 70, places : 101 (100 correct) Back to rational: 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742 Rational number : 1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387 Engel expansion : 1 3 5 5 16 18 78 102 120 144 251 363 1402 31169 88630 184655 259252 298770 4196070 38538874 616984563 1975413038 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 Number of terms : 70, places : 87 (87 correct) Back to rational: 1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387 Rational number : 25.628906 Engel expansion : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 33 33 35 Number of terms : 54, places : 6 (6 correct) Back to rational: 25.628906
Raku
<lang perl6>sub to-engel ($rat is copy) { do while $rat { my $a = ceiling 1 / $rat; $rat = $rat × $a - 1; $a } }
sub from-engel (@expanded) { sum [\×] @expanded.map: { FatRat.new: 1, $_ } }
for # low precision 𝜋, 𝑒, √2 and 1.5 to a power
3.14159265358979, 2.71828182845904, 1.414213562373095, 1.5 ** 5,
# high precision 𝜋, 𝑒, and √2 and 1.5 to a power 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211.FatRat,
2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743.FatRat,
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558.FatRat,
1.5 ** 8 -> $rat { say "Rational number: $rat"; my @expanded = $rat.&to-engel; put "Engel expansion: " ~ @expanded.head(30); say " Converted back: " ~ @expanded.&from-engel; put ;
}</lang>
- Output:
Rational number: 3.14159265358979 Engel expansion: 1 1 1 8 8 17 19 300 1991 2768 4442 4830 10560 37132 107315 244141 651042 1953125 Converted back: 3.14159265358979 Rational number: 2.71828182845904 Engel expansion: 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 82 144 321 2289 9041 21083 474060 887785 976563 1953125 Converted back: 2.71828182845904 Rational number: 1.414213562373095 Engel expansion: 1 3 5 5 16 18 78 102 120 144 260 968 18531 46065 63005 65105 78125 Converted back: 1.414213562373095 Rational number: 7.59375 Engel expansion: 1 1 1 1 1 1 1 2 6 8 Converted back: 7.59375 Rational number: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211 Engel expansion: 1 1 1 8 8 17 19 300 1991 2492 7236 10586 34588 63403 70637 1236467 5417668 5515697 5633167 7458122 9637848 9805775 41840855 58408380 213130873 424342175 2366457522 4109464489 21846713216 27803071890 Converted back: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211 Rational number: 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 Engel expansion: 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Converted back: 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 Rational number: 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558 Engel expansion: 1 3 5 5 16 18 78 102 120 144 251 363 1402 31169 88630 184655 259252 298770 4196070 38538874 616984563 1975413035 5345718057 27843871197 54516286513 334398528974 445879679626 495957494386 2450869042061 2629541150527 Converted back: 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558 Rational number: 25.628906 Engel expansion: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 32 Converted back: 25.628906
Wren
As in the case of the Raku example, I've limited the display of the Engel expansion to a maximum of 30 terms though I've also shown the total number of terms.
However, I've also limited the number of terms accumulated by the 'fromEngel' function to 70 which is just enough to reproduce the high precision rationals in decimal notation. To accumulate all the terms in a reasonable time would require the use of Wren-gmp which I've tried to avoid so the solution will run under Wren-CLI. <lang ecmascript>import "./big" for BigRat import "./fmt" for Fmt
var toEngel = Fn.new { |x|
var engel = [] var u = BigRat.fromDecimal(x) while (true) { var a = u.inverse.ceil engel.add(a.toBigInt) u = u * a - BigRat.one if (u == 0) return engel }
}
var fromEngel = Fn.new { |engel|
var sum = BigRat.zero var prod = BigRat.one for (e in engel) { var r = BigRat.new(e).inverse prod = prod * r sum = sum + prod } return sum
}
var rats = [
"3.14159265358979", "2.71828182845904", "1.414213562373095", "7.59375", "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211", "2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743", "1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558", "25.628906"
] for (rat in rats) {
Fmt.print("Rational number : $s", rat) var dix = rat.indexOf(".") + 1 var places = rat.count - dix var engel = toEngel.call(rat) Fmt.print("Engel expansion : $i", engel.take(30).toList) Fmt.print("Number of terms : $d", engel.count) Fmt.print("Back to rational: $s\n", fromEngel.call(engel.take(70).toList).toDecimal(places))
}</lang>
- Output:
Rational number : 3.14159265358979 Engel expansion : 1 1 1 8 8 17 19 300 1991 2768 4442 4830 10560 37132 107315 244141 651042 1953125 Number of terms : 18 Back to rational: 3.14159265358979 Rational number : 2.71828182845904 Engel expansion : 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 82 144 321 2289 9041 21083 474060 887785 976563 1953125 Number of terms : 27 Back to rational: 2.71828182845904 Rational number : 1.414213562373095 Engel expansion : 1 3 5 5 16 18 78 102 120 144 260 968 18531 46065 63005 65105 78125 Number of terms : 17 Back to rational: 1.414213562373095 Rational number : 7.59375 Engel expansion : 1 1 1 1 1 1 1 2 6 8 Number of terms : 10 Back to rational: 7.59375 Rational number : 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211 Engel expansion : 1 1 1 8 8 17 19 300 1991 2492 7236 10586 34588 63403 70637 1236467 5417668 5515697 5633167 7458122 9637848 9805775 41840855 58408380 213130873 424342175 2366457522 4109464489 21846713216 27803071890 Number of terms : 231 Back to rational: 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211 Rational number : 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 Engel expansion : 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Number of terms : 150 Back to rational: 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642743 Rational number : 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558 Engel expansion : 1 3 5 5 16 18 78 102 120 144 251 363 1402 31169 88630 184655 259252 298770 4196070 38538874 616984563 1975413035 5345718057 27843871197 54516286513 334398528974 445879679626 495957494386 2450869042061 2629541150527 Number of terms : 185 Back to rational: 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927558 Rational number : 25.628906 Engel expansion : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 33 33 35 Number of terms : 34 Back to rational: 25.628906