Continued fraction/Arithmetic/G(matrix ng, continued fraction n): Difference between revisions
Alextretyak (talk | contribs) (Added 11l) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 45: | Line 45: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">T NG |
||
Int a1, a, b1, b |
Int a1, a, b1, b |
||
F (a1, a, b1, b) |
F (a1, a, b1, b) |
||
Line 97: | Line 97: | ||
I op.done() |
I op.done() |
||
L.break |
L.break |
||
print()</ |
print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 108: | Line 108: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
Uses ContinuedFraction and r2cf from [[Continued_fraction/Arithmetic/Construct_from_rational_number#C++]] |
Uses ContinuedFraction and r2cf from [[Continued_fraction/Arithmetic/Construct_from_rational_number#C++]] |
||
< |
<syntaxhighlight lang="cpp">/* Interface for all matrixNG classes |
||
Nigel Galloway, February 10th., 2013. |
Nigel Galloway, February 10th., 2013. |
||
*/ |
*/ |
||
Line 155: | Line 155: | ||
return ng->haveTerm; |
return ng->haveTerm; |
||
} |
} |
||
};</ |
};</syntaxhighlight> |
||
===Testing=== |
===Testing=== |
||
====[1;5,2] + 1/2==== |
====[1;5,2] + 1/2==== |
||
< |
<syntaxhighlight lang="cpp">int main() { |
||
NG_4 a1(2,1,0,2); |
NG_4 a1(2,1,0,2); |
||
r2cf n1(13,11); |
r2cf n1(13,11); |
||
Line 164: | Line 164: | ||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 170: | Line 170: | ||
</pre> |
</pre> |
||
====[3;7] * 7/22==== |
====[3;7] * 7/22==== |
||
< |
<syntaxhighlight lang="cpp">int main() { |
||
NG_4 a2(7,0,0,22); |
NG_4 a2(7,0,0,22); |
||
r2cf n2(22,7); |
r2cf n2(22,7); |
||
Line 176: | Line 176: | ||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 182: | Line 182: | ||
</pre> |
</pre> |
||
====[3;7] + 1/22==== |
====[3;7] + 1/22==== |
||
< |
<syntaxhighlight lang="cpp">int main() { |
||
NG_4 a3(2,1,0,2); |
NG_4 a3(2,1,0,2); |
||
r2cf n3(22,7); |
r2cf n3(22,7); |
||
Line 188: | Line 188: | ||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 194: | Line 194: | ||
</pre> |
</pre> |
||
====[3;7] divided by 4==== |
====[3;7] divided by 4==== |
||
< |
<syntaxhighlight lang="cpp">int main() { |
||
NG_4 a4(1,0,0,4); |
NG_4 a4(1,0,0,4); |
||
r2cf n4(22,7); |
r2cf n4(22,7); |
||
Line 200: | Line 200: | ||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 207: | Line 207: | ||
====<math>\frac{1}{\sqrt{2}}</math>==== |
====<math>\frac{1}{\sqrt{2}}</math>==== |
||
First I generate <math>\frac{1}{\sqrt{2}}</math> as a continued fraction, then I obtain an approximate value using r2cf for comparison. |
First I generate <math>\frac{1}{\sqrt{2}}</math> as a continued fraction, then I obtain an approximate value using r2cf for comparison. |
||
< |
<syntaxhighlight lang="cpp">int main() { |
||
NG_4 a5(0,1,1,0); |
NG_4 a5(0,1,1,0); |
||
SQRT2 n5; |
SQRT2 n5; |
||
Line 216: | Line 216: | ||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 224: | Line 224: | ||
====<math>\frac{1 + \sqrt{2}}{2}</math>==== |
====<math>\frac{1 + \sqrt{2}}{2}</math>==== |
||
First I generate <math>\frac{1 + \sqrt{2}}{2}</math> as a continued fraction, then I obtain an approximate value using r2cf for comparison. |
First I generate <math>\frac{1 + \sqrt{2}}{2}</math> as a continued fraction, then I obtain an approximate value using r2cf for comparison. |
||
< |
<syntaxhighlight lang="cpp">int main() { |
||
int i = 0; |
int i = 0; |
||
NG_4 a6(1,1,0,2); |
NG_4 a6(1,1,0,2); |
||
Line 233: | Line 233: | ||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 246: | Line 246: | ||
File <code>ng4.go</code>: |
File <code>ng4.go</code>: |
||
< |
<syntaxhighlight lang="go">package cf |
||
// A 2×2 matix: |
// A 2×2 matix: |
||
Line 329: | Line 329: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
File <code>ng4_test.go</code>: |
File <code>ng4_test.go</code>: |
||
< |
<syntaxhighlight lang="go">package cf |
||
import ( |
import ( |
||
Line 366: | Line 366: | ||
// 1/√2 = [0; 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...] |
// 1/√2 = [0; 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...] |
||
// (1+√2)/2 = [1; 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, ...] |
// (1+√2)/2 = [1; 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, ...] |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 382: | Line 382: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang="j">ng4cf=: 4 : 0 |
||
cf=. 1000{.!._ y |
cf=. 1000{.!._ y |
||
ng=. x |
ng=. x |
||
Line 400: | Line 400: | ||
end. |
end. |
||
r |
r |
||
)</ |
)</syntaxhighlight> |
||
Notes: |
Notes: |
||
Line 412: | Line 412: | ||
Some arbitrary continued fractions and their floating point representations |
Some arbitrary continued fractions and their floating point representations |
||
< |
<syntaxhighlight lang="j"> arbs=:(,1);(,3);?~&.>3+i.10 |
||
":@>arbs |
":@>arbs |
||
1 |
1 |
||
Line 427: | Line 427: | ||
1 7 3 4 5 8 9 10 6 11 0 2 |
1 7 3 4 5 8 9 10 6 11 0 2 |
||
(+%)/@>arbs |
(+%)/@>arbs |
||
1 3 1 0.444444 4.44444 0.431925 2.16238 7.19368 8.46335 13.1583 0.109719 1.13682</ |
1 3 1 0.444444 4.44444 0.431925 2.16238 7.19368 8.46335 13.1583 0.109719 1.13682</syntaxhighlight> |
||
Some NG based cf functions, verifying their behavior against our test set: |
Some NG based cf functions, verifying their behavior against our test set: |
||
< |
<syntaxhighlight lang="j"> plus1r2=: (2 1,:0 2)&ng4cf |
||
(plus1r2 each -&((+%)/@>) ]) arbs |
(plus1r2 each -&((+%)/@>) ]) arbs |
||
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5</ |
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5</syntaxhighlight> |
||
For every one of our arbitrary continued fractions, the 2 1,:0 2 NG matrix gives us a new continued fraction whose rational value is the original rational value + 1r2. |
For every one of our arbitrary continued fractions, the 2 1,:0 2 NG matrix gives us a new continued fraction whose rational value is the original rational value + 1r2. |
||
< |
<syntaxhighlight lang="j"> times7r22=: (7 0,:0 22)&ng4cf |
||
(times7r22 each %&((+%)/@>) ]) arbs |
(times7r22 each %&((+%)/@>) ]) arbs |
||
0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 |
0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 |
||
(times7r22 each %&((+%)/@x:@>) ]) arbs |
(times7r22 each %&((+%)/@x:@>) ]) arbs |
||
7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22</ |
7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22</syntaxhighlight> |
||
For every one of our arbitrary continued fractions, the 7 0,:0 22 NG matrix gives us a new continued fraction whose rational value is 7r22 times the original rational value. |
For every one of our arbitrary continued fractions, the 7 0,:0 22 NG matrix gives us a new continued fraction whose rational value is 7r22 times the original rational value. |
||
< |
<syntaxhighlight lang="j"> times1r4=:(1 0,:0 4)&ng4cf |
||
(times1r4 each %&((+%)/@>) ]) arbs |
(times1r4 each %&((+%)/@>) ]) arbs |
||
0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25</ |
0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25</syntaxhighlight> |
||
It seems like a diagonal matrix has the effect of multiplying the numerator by the upper left element and the denominator by the lower right element. And our first experiment suggests that an upper right element in NG with a 0 for the bottom left will add the top right divided by bottom right to our continued fraction. |
It seems like a diagonal matrix has the effect of multiplying the numerator by the upper left element and the denominator by the lower right element. And our first experiment suggests that an upper right element in NG with a 0 for the bottom left will add the top right divided by bottom right to our continued fraction. |
||
< |
<syntaxhighlight lang="j"> reciprocal=:(0 1,:1 0)&ng4cf |
||
(reciprocal each *&((+%)/@>) ]) arbs |
(reciprocal each *&((+%)/@>) ]) arbs |
||
1 1 1 1 1 1 1 1 1 1 1 1</ |
1 1 1 1 1 1 1 1 1 1 1 1</syntaxhighlight> |
||
Looks like we can also divide by our continued fraction... |
Looks like we can also divide by our continued fraction... |
||
< |
<syntaxhighlight lang="j"> plus1r2times1r2=: (1 1,:0 2)&ng4cf |
||
(plus1r2times1r2 each (= 0.5+0.5*])&((+%)/@>) ]) arbs |
(plus1r2times1r2 each (= 0.5+0.5*])&((+%)/@>) ]) arbs |
||
1 1 1 1 1 1 1 1 1 1 1 1</ |
1 1 1 1 1 1 1 1 1 1 1 1</syntaxhighlight> |
||
We can add and multiply using a single "ng4" operation. |
We can add and multiply using a single "ng4" operation. |
||
Line 466: | Line 466: | ||
'''<code>1r2 + 13r11</code>''' |
'''<code>1r2 + 13r11</code>''' |
||
< |
<syntaxhighlight lang="j"> (+%)/1 5 2 |
||
1.18182 |
1.18182 |
||
plus1r2 1 5 2 |
plus1r2 1 5 2 |
||
1 1 2 7 |
1 1 2 7 |
||
(+%)/plus1r2 1 5 2 |
(+%)/plus1r2 1 5 2 |
||
1.68182</ |
1.68182</syntaxhighlight> |
||
'''<code>7r22 * 22r7</code>''' |
'''<code>7r22 * 22r7</code>''' |
||
< |
<syntaxhighlight lang="j"> (+%)/3 7x |
||
22r7 |
22r7 |
||
times7r22 3 7x |
times7r22 3 7x |
||
1</ |
1</syntaxhighlight> |
||
'''<code>1r2 + 22r7</code>''' |
'''<code>1r2 + 22r7</code>''' |
||
< |
<syntaxhighlight lang="j"> plus1r2 3 7x |
||
3 1 1 1 4 |
3 1 1 1 4 |
||
(+%)/plus1r2 3 7x |
(+%)/plus1r2 3 7x |
||
3.64286 |
3.64286 |
||
(+%)/x:plus1r2 3 7x |
(+%)/x:plus1r2 3 7x |
||
51r14</ |
51r14</syntaxhighlight> |
||
'''<code>1r4 * 22r7</code>''' |
'''<code>1r4 * 22r7</code>''' |
||
< |
<syntaxhighlight lang="j"> times1r4 3 7x |
||
0 1 3 1 2 |
0 1 3 1 2 |
||
(+%)/x:times1r4 3 7x |
(+%)/x:times1r4 3 7x |
||
11r14</ |
11r14</syntaxhighlight> |
||
<math>\frac{1}{\sqrt{2}}</math> |
<math>\frac{1}{\sqrt{2}}</math> |
||
< |
<syntaxhighlight lang="j"> reciprocal 1,999$2 |
||
0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
||
(+%)/1,999$2 |
(+%)/1,999$2 |
||
1.41421 |
1.41421 |
||
(+%)/reciprocal 1,999$2 |
(+%)/reciprocal 1,999$2 |
||
0.707107</ |
0.707107</syntaxhighlight> |
||
<math>\frac{1 + \sqrt{2}}{2}</math> |
<math>\frac{1 + \sqrt{2}}{2}</math> |
||
< |
<syntaxhighlight lang="j"> plus1r2times1r2 1,999$2 |
||
1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 ... |
1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 ... |
||
(+%)/plus1r2times1r2 1,999$2 |
(+%)/plus1r2times1r2 1,999$2 |
||
1.20711</ |
1.20711</syntaxhighlight> |
||
<math>\frac{1 + \frac{1}{\sqrt{2}}}{2}</math> |
<math>\frac{1 + \frac{1}{\sqrt{2}}}{2}</math> |
||
< |
<syntaxhighlight lang="j"> plus1r2times1r2 0 1,999$2 |
||
0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 ... |
0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 ... |
||
(+%)/plus1r2times1r2 0 1,999$2 |
(+%)/plus1r2times1r2 0 1,999$2 |
||
0.853553</ |
0.853553</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="julia">function r2cf(n1::Integer, n2::Integer) |
||
ret = Int[] |
ret = Int[] |
||
while n2 != 0 |
while n2 != 0 |
||
Line 586: | Line 586: | ||
testng() |
testng() |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
[1;5,2] + 1/2 -> [1, 1, 2, 7] |
[1;5,2] + 1/2 -> [1, 1, 2, 7] |
||
Line 596: | Line 596: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
This is based on the Python entry but has been expanded to deal with the '√2' calculations: |
This is based on the Python entry but has been expanded to deal with the '√2' calculations: |
||
< |
<syntaxhighlight lang="scala">// version 1.1.3 |
||
// compile with -Xcoroutines=enable flag from command line |
// compile with -Xcoroutines=enable flag from command line |
||
Line 719: | Line 719: | ||
println("$str -> ${d2cf(d).take(20).joinToString(" ")}") |
println("$str -> ${d2cf(d).take(20).joinToString(" ")}") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 739: | Line 739: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="nim">import math, rationals, strformat |
||
type |
type |
||
Line 838: | Line 838: | ||
stdout.write &"{str} →" |
stdout.write &"{str} →" |
||
for n in d2cf(d): stdout.write " ", n |
for n in d2cf(d): stdout.write " ", n |
||
echo()</ |
echo()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 858: | Line 858: | ||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
Self-contained. The supporting cast of r2cf(), cf2s(), cf2r() and d2cf() ended up being more code than the task itself. |
Self-contained. The supporting cast of r2cf(), cf2s(), cf2r() and d2cf() ended up being more code than the task itself. |
||
< |
<syntaxhighlight lang="phix">requires("0.8.2") |
||
class baby_matrix |
class baby_matrix |
||
Line 1,001: | Line 1,001: | ||
printf(1,"%s -> %s --> %s\n",{str,cf2s(res),cf2r(res)}) |
printf(1,"%s -> %s --> %s\n",{str,cf2s(res),cf2r(res)}) |
||
printf(1," direct: %s ==> %.15f\n",{d2cf(eres,length(res)),eres}) |
printf(1," direct: %s ==> %.15f\n",{d2cf(eres,length(res)),eres}) |
||
end for</ |
end for</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,028: | Line 1,028: | ||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
===Python: NG=== |
===Python: NG=== |
||
< |
<syntaxhighlight lang="python">class NG: |
||
def __init__(self, a1, a, b1, b): |
def __init__(self, a1, a, b1, b): |
||
self.a1, self.a, self.b1, self.b = a1, a, b1, b |
self.a1, self.a, self.b1, self.b = a1, a, b1, b |
||
Line 1,054: | Line 1,054: | ||
@property |
@property |
||
def done(self): |
def done(self): |
||
return self.b == 0 and self.b1 == 0</ |
return self.b == 0 and self.b1 == 0</syntaxhighlight> |
||
===Python: Testing=== |
===Python: Testing=== |
||
Uses '''r2cf''' method from [[Continued fraction/Arithmetic/Construct from rational number#Python|here]]. |
Uses '''r2cf''' method from [[Continued fraction/Arithmetic/Construct from rational number#Python|here]]. |
||
< |
<syntaxhighlight lang="python">data = [["[1;5,2] + 1/2", [2,1,0,2], [13,11]], |
||
["[3;7] + 1/2", [2,1,0,2], [22, 7]], |
["[3;7] + 1/2", [2,1,0,2], [22, 7]], |
||
["[3;7] divided by 4", [1,0,0,4], [22, 7]]] |
["[3;7] divided by 4", [1,0,0,4], [22, 7]]] |
||
Line 1,070: | Line 1,070: | ||
print( " %r" % op.egress_done, end='' ) |
print( " %r" % op.egress_done, end='' ) |
||
if op.done: break |
if op.done: break |
||
print()</ |
print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1;5,2] + 1/2 -> 1 1 2 7 |
<pre>[1;5,2] + 1/2 -> 1 1 2 7 |
||
Line 1,079: | Line 1,079: | ||
{{trans|Python}} {{trans|C++}} |
{{trans|Python}} {{trans|C++}} |
||
Main part of the NG-baby matrices. They are implemented as mutable structs. |
Main part of the NG-baby matrices. They are implemented as mutable structs. |
||
< |
<syntaxhighlight lang="racket">#lang racket/base |
||
(struct ng (a1 a b1 b) #:transparent #:mutable) |
(struct ng (a1 a b1 b) #:transparent #:mutable) |
||
Line 1,116: | Line 1,116: | ||
(define (ng-done? v) |
(define (ng-done? v) |
||
(and (zero? (ng-b v)) (zero? (ng-b1 v))))</ |
(and (zero? (ng-b v)) (zero? (ng-b1 v))))</syntaxhighlight> |
||
Auxiliary functions to create producers of well known continued fractions. The function rational->cf is copied from [[Continued fraction/Arithmetic/Construct from rational number#Racket|r2cf task]]. |
Auxiliary functions to create producers of well known continued fractions. The function rational->cf is copied from [[Continued fraction/Arithmetic/Construct from rational number#Racket|r2cf task]]. |
||
< |
<syntaxhighlight lang="racket">(define ((rational->cf n d)) |
||
(and (not (zero? d)) |
(and (not (zero? d)) |
||
(let-values ([(q r) (quotient/remainder n d)]) |
(let-values ([(q r) (quotient/remainder n d)]) |
||
Line 1,133: | Line 1,133: | ||
(set! first? #f) |
(set! first? #f) |
||
1) |
1) |
||
2)))</ |
2)))</syntaxhighlight> |
||
The function combine-ng-cf->cf combines a ng-matrix and a cf- producer and creates a cf-producer. The cf-producers can represent infinitely long continued fractions. The function cf-showln shows the first coefficients of a continued fraction represented in a cf-producer. |
The function combine-ng-cf->cf combines a ng-matrix and a cf- producer and creates a cf-producer. The cf-producers can represent infinitely long continued fractions. The function cf-showln shows the first coefficients of a continued fraction represented in a cf-producer. |
||
< |
<syntaxhighlight lang="racket">(define (combine-ng-cf->cf ng cf) |
||
(define empty-producer? #f) |
(define empty-producer? #f) |
||
(lambda () |
(lambda () |
||
Line 1,161: | Line 1,161: | ||
(when (cf) |
(when (cf) |
||
(printf " ...")) |
(printf " ...")) |
||
(printf "~n"))</ |
(printf "~n"))</syntaxhighlight> |
||
Some test |
Some test |
||
< |
<syntaxhighlight lang="racket">(display "[1;5,2] + 1/2 ->") |
||
(cf-showln (combine-ng-cf->cf (ng 2 1 0 2) (rational->cf 13 11)) 20) |
(cf-showln (combine-ng-cf->cf (ng 2 1 0 2) (rational->cf 13 11)) 20) |
||
Line 1,180: | Line 1,180: | ||
(display "(1+sqrt(2))/2 ->") |
(display "(1+sqrt(2))/2 ->") |
||
(cf-showln (combine-ng-cf->cf (ng 1 1 0 2) (sqrt2->cf)) 20)</ |
(cf-showln (combine-ng-cf->cf (ng 1 1 0 2) (sqrt2->cf)) 20)</syntaxhighlight> |
||
'''Sample output:''' |
'''Sample output:''' |
||
Line 1,194: | Line 1,194: | ||
{{works with|Rakudo|2020.08.1}} |
{{works with|Rakudo|2020.08.1}} |
||
All the important stuff takes place in the NG object. Everything else is helper subs for testing and display. The NG object is capable of working with infinitely long continued fractions, but displaying them can be problematic. You can pass in a limit to the apply method to get a fixed maximum number of terms though. See the last example: 100 terms from the infinite cf (1+√2)/2 and its Rational representation. |
All the important stuff takes place in the NG object. Everything else is helper subs for testing and display. The NG object is capable of working with infinitely long continued fractions, but displaying them can be problematic. You can pass in a limit to the apply method to get a fixed maximum number of terms though. See the last example: 100 terms from the infinite cf (1+√2)/2 and its Rational representation. |
||
<lang |
<syntaxhighlight lang="raku" line>class NG { |
||
has ( $!a1, $!a, $!b1, $!b ); |
has ( $!a1, $!a, $!b1, $!b ); |
||
submethod BUILD ( :$!a1, :$!a, :$!b1, :$!b ) { } |
submethod BUILD ( :$!a1, :$!a, :$!b1, :$!b ) { } |
||
Line 1,269: | Line 1,269: | ||
say @continued-fraction.&ppcf.comb(/ . ** 1..80/).join("\n"); |
say @continued-fraction.&ppcf.comb(/ . ** 1..80/).join("\n"); |
||
say @continued-fraction.&cf2r.&pprat; |
say @continued-fraction.&cf2r.&pprat; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,292: | Line 1,292: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
===NG=== |
===NG=== |
||
< |
<syntaxhighlight lang="ruby"># I define a class to implement baby NG |
||
class NG |
class NG |
||
def initialize(a1, a, b1, b) |
def initialize(a1, a, b1, b) |
||
Line 1,319: | Line 1,319: | ||
@b == 0 and @b1 == 0 |
@b == 0 and @b1 == 0 |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
===Testing=== |
===Testing=== |
||
Uses '''r2cf''' method from [[Continued fraction/Arithmetic/Construct from rational number#Ruby|here]]. |
Uses '''r2cf''' method from [[Continued fraction/Arithmetic/Construct from rational number#Ruby|here]]. |
||
< |
<syntaxhighlight lang="ruby">data = [["[1;5,2] + 1/2", [2,1,0,2], [13,11]], |
||
["[3;7] + 1/2", [2,1,0,2], [22, 7]], |
["[3;7] + 1/2", [2,1,0,2], [22, 7]], |
||
["[3;7] divided by 4", [1,0,0,4], [22, 7]]] |
["[3;7] divided by 4", [1,0,0,4], [22, 7]]] |
||
Line 1,335: | Line 1,335: | ||
print " #{op.egress_done}" until op.done? |
print " #{op.egress_done}" until op.done? |
||
puts |
puts |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,347: | Line 1,347: | ||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="tcl"># The single-operand version of the NG operator, using our little generator framework |
||
oo::class create NG1 { |
oo::class create NG1 { |
||
superclass Generator |
superclass Generator |
||
Line 1,396: | Line 1,396: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
< |
<syntaxhighlight lang="tcl"># The square root of 2 as a continued fraction in the framework |
||
oo::class create Root2 { |
oo::class create Root2 { |
||
superclass Generator |
superclass Generator |
||
Line 1,426: | Line 1,426: | ||
set op [[NG1 new 1 1 0 2] operand [Root2 new]] |
set op [[NG1 new 1 1 0 2] operand [Root2 new]] |
||
printcf "(1+\u221a2)/2" $op 20 |
printcf "(1+\u221a2)/2" $op 20 |
||
printcf "approx val" [R2CF new 24142136 20000000]</ |
printcf "approx val" [R2CF new 24142136 20000000]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,441: | Line 1,441: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
{{libheader|Wren-dynamic}} |
{{libheader|Wren-dynamic}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/dynamic" for Tuple |
||
var CFData = Tuple.create("Tuple", ["str", "ng", "r", "gen"]) |
var CFData = Tuple.create("Tuple", ["str", "ng", "r", "gen"]) |
||
Line 1,571: | Line 1,571: | ||
} |
} |
||
System.print("%(p[0]) -> %(seq.join(" "))") |
System.print("%(p[0]) -> %(seq.join(" "))") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,591: | Line 1,591: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="zkl">class NG{ |
||
fcn init(_a1,_a, _b1,_b){ var a1=_a1,a=_a, b1=_b1,b=_b; } |
fcn init(_a1,_a, _b1,_b){ var a1=_a1,a=_a, b1=_b1,b=_b; } |
||
var [proxy] done =fcn{ b==0 and b1==0 }; |
var [proxy] done =fcn{ b==0 and b1==0 }; |
||
Line 1,610: | Line 1,610: | ||
egress() |
egress() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl"> // from task: Continued fraction/Arithmetic/Construct from rational number |
||
fcn r2cf(nom,dnom){ // -->Walker (iterator) |
fcn r2cf(nom,dnom){ // -->Walker (iterator) |
||
Walker.tweak(fcn(_,state){ |
Walker.tweak(fcn(_,state){ |
||
Line 1,620: | Line 1,620: | ||
n |
n |
||
}.fp1(List(nom,dnom))) |
}.fp1(List(nom,dnom))) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">data:=T(T("[1;5,2] + 1/2", T(2,1,0,2), T(13,11)), |
||
T("[3;7] + 1/2", T(2,1,0,2), T(22, 7)), |
T("[3;7] + 1/2", T(2,1,0,2), T(22, 7)), |
||
T("[3;7] divided by 4", T(1,0,0,4), T(22, 7))); |
T("[3;7] divided by 4", T(1,0,0,4), T(22, 7))); |
||
Line 1,633: | Line 1,633: | ||
do{ print(" ",op.egress_done()) }while(not op.done); |
do{ print(" ",op.egress_done()) }while(not op.done); |
||
println(); |
println(); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 22:10, 26 August 2022
This task investigates mathmatical operations that can be performed on a single continued fraction. This requires only a baby version of NG:
I may perform perform the following operations:
- Input the next term of N1
- Output a term of the continued fraction resulting from the operation.
I output a term if the integer parts of and are equal. Otherwise I input a term from N. If I need a term from N but N has no more terms I inject .
When I input a term t my internal state: is transposed thus
When I output a term t my internal state: is transposed thus
When I need a term t but there are no more my internal state: is transposed thus
I am done when b1 and b are zero.
Demonstrate your solution by calculating:
- [1;5,2] + 1/2
- [3;7] + 1/2
- [3;7] divided by 4
Using a generator for (e.g., from Continued fraction) calculate . You are now at the starting line for using Continued Fractions to implement Arithmetic-geometric mean without ulps and epsilons.
The first step in implementing Arithmetic-geometric mean is to calculate do this now to cross the starting line and begin the race.
11l
T NG
Int a1, a, b1, b
F (a1, a, b1, b)
.a1 = a1
.a = a
.b1 = b1
.b = b
F ingress(n)
(.a, .a1) = (.a1, .a + .a1 * n)
(.b, .b1) = (.b1, .b + .b1 * n)
F needterm()
R (.b == 0 | .b1 == 0) | !(.a I/ .b == .a1 I/ .b1)
F egress()
V n = .a I/ .b
(.a, .b) = (.b, .a - .b * n)
(.a1, .b1) = (.b1, .a1 - .b1 * n)
R n
F egress_done()
I .needterm()
(.a, .b) = (.a1, .b1)
R .egress()
F done()
R .b == 0 & .b1 == 0
F r2cf(=n1, =n2)
[Int] r
L n2 != 0
(n1, V t1_n2) = (n2, divmod(n1, n2))
n2 = t1_n2[1]
r [+]= t1_n2[0]
R r
V data = [(‘[1;5,2] + 1/2’, 2,1,0,2, (13, 11)),
(‘[3;7] + 1/2’, 2,1,0,2, (22, 7)),
(‘[3;7] divided by 4’, 1,0,0,4, (22, 7))]
L(string, a1, a, b1, b, r) data
print(‘#<20->’.format(string), end' ‘’)
V op = NG(a1, a, b1, b)
L(n) r2cf(r[0], r[1])
I !op.needterm()
print(‘ ’op.egress(), end' ‘’)
op.ingress(n)
L
print(‘ ’op.egress_done(), end' ‘’)
I op.done()
L.break
print()
- Output:
[1;5,2] + 1/2 -> 1 1 2 7 [3;7] + 1/2 -> 3 1 1 1 4 [3;7] divided by 4 -> 0 1 3 1 2
C++
Uses ContinuedFraction and r2cf from Continued_fraction/Arithmetic/Construct_from_rational_number#C++
/* Interface for all matrixNG classes
Nigel Galloway, February 10th., 2013.
*/
class matrixNG {
private:
virtual void consumeTerm(){}
virtual void consumeTerm(int n){}
virtual const bool needTerm(){}
protected: int cfn = 0, thisTerm;
bool haveTerm = false;
friend class NG;
};
/* Implement the babyNG matrix
Nigel Galloway, February 10th., 2013.
*/
class NG_4 : public matrixNG {
private: int a1, a, b1, b, t;
const bool needTerm() {
if (b1==0 and b==0) return false;
if (b1==0 or b==0) return true; else thisTerm = a/b;
if (thisTerm==(int)(a1/b1)){
t=a; a=b; b=t-b*thisTerm; t=a1; a1=b1; b1=t-b1*thisTerm;
haveTerm=true; return false;
}
return true;
}
void consumeTerm(){a=a1; b=b1;}
void consumeTerm(int n){t=a; a=a1; a1=t+a1*n; t=b; b=b1; b1=t+b1*n;}
public:
NG_4(int a1, int a, int b1, int b): a1(a1), a(a), b1(b1), b(b){}
};
/* Implement a Continued Fraction which returns the result of an arithmetic operation on
1 or more Continued Fractions (Currently 1 or 2).
Nigel Galloway, February 10th., 2013.
*/
class NG : public ContinuedFraction {
private:
matrixNG* ng;
ContinuedFraction* n[2];
public:
NG(NG_4* ng, ContinuedFraction* n1): ng(ng){n[0] = n1;}
NG(NG_8* ng, ContinuedFraction* n1, ContinuedFraction* n2): ng(ng){n[0] = n1; n[1] = n2;}
const int nextTerm() {ng->haveTerm = false; return ng->thisTerm;}
const bool moreTerms(){
while(ng->needTerm()) if(n[ng->cfn]->moreTerms()) ng->consumeTerm(n[ng->cfn]->nextTerm()); else ng->consumeTerm();
return ng->haveTerm;
}
};
Testing
[1;5,2] + 1/2
int main() {
NG_4 a1(2,1,0,2);
r2cf n1(13,11);
for(NG n(&a1, &n1); n.moreTerms(); std::cout << n.nextTerm() << " ");
std::cout << std::endl;
return 0;
}
- Output:
1 1 2 7
[3;7] * 7/22
int main() {
NG_4 a2(7,0,0,22);
r2cf n2(22,7);
for(NG n(&a2, &n2); n.moreTerms(); std::cout << n.nextTerm() << " ");
std::cout << std::endl;
return 0;
}
- Output:
1
[3;7] + 1/22
int main() {
NG_4 a3(2,1,0,2);
r2cf n3(22,7);
for(NG n(&a3, &n3); n.moreTerms(); std::cout << n.nextTerm() << " ");
std::cout << std::endl;
return 0;
}
- Output:
3 1 1 1 4
[3;7] divided by 4
int main() {
NG_4 a4(1,0,0,4);
r2cf n4(22,7);
for(NG n(&a4, &n4); n.moreTerms(); std::cout << n.nextTerm() << " ");
std::cout << std::endl;
return 0;
}
- Output:
0 1 3 1 2
First I generate as a continued fraction, then I obtain an approximate value using r2cf for comparison.
int main() {
NG_4 a5(0,1,1,0);
SQRT2 n5;
int i = 0;
for(NG n(&a5, &n5); n.moreTerms() and i++ < 20; std::cout << n.nextTerm() << " ");
std::cout << "..." << std::endl;
for(r2cf cf(10000000, 14142136); cf.moreTerms(); std::cout << cf.nextTerm() << " ");
std::cout << std::endl;
return 0;
}
- Output:
0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... 0 1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2
First I generate as a continued fraction, then I obtain an approximate value using r2cf for comparison.
int main() {
int i = 0;
NG_4 a6(1,1,0,2);
SQRT2 n6;
for(NG n(&a6, &n6); n.moreTerms() and i++ < 20; std::cout << n.nextTerm() << " ");
std::cout << "..." << std::endl;
for(r2cf cf(24142136, 20000000); cf.moreTerms(); std::cout << cf.nextTerm() << " ");
std::cout << std::endl;
return 0;
}
- Output:
1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 ... 1 4 1 4 1 4 1 4 1 4 3 2 1 9 5
Go
Adding to the existing package from the
Continued_fraction/Arithmetic/Construct_from_rational_number#Go
task, re-uses cf.go
and rat.go
as given in that task.
File ng4.go
:
package cf
// A 2×2 matix:
// [ a₁ a ]
// [ b₁ b ]
//
// which when "applied" to a continued fraction representing x
// gives a new continued fraction z such that:
//
// a₁ * x + a
// z = ----------
// b₁ * x + b
//
// Examples:
// NG4{0, 1, 0, 4}.ApplyTo(x) gives 0*x + 1/4 -> 1/4 = [0; 4]
// NG4{0, 1, 1, 0}.ApplyTo(x) gives 1/x
// NG4{1, 1, 0, 2}.ApplyTo(x) gives (x+1)/2
//
// Note that several operations (e.g. addition and division)
// can be efficiently done with a single matrix application.
// However, each matrix application may require
// several calculations for each outputed term.
type NG4 struct {
A1, A int64
B1, B int64
}
func (ng NG4) needsIngest() bool {
if ng.isDone() {
panic("b₁==b==0")
}
return ng.B1 == 0 || ng.B == 0 || ng.A1/ng.B1 != ng.A/ng.B
}
func (ng NG4) isDone() bool {
return ng.B1 == 0 && ng.B == 0
}
func (ng *NG4) ingest(t int64) {
// [ a₁ a ] becomes [ a + a₁×t a₁ ]
// [ b₁ b ] [ b + b₁×t b₁ ]
ng.A1, ng.A, ng.B1, ng.B =
ng.A+ng.A1*t, ng.A1,
ng.B+ng.B1*t, ng.B1
}
func (ng *NG4) ingestInfinite() {
// [ a₁ a ] becomes [ a₁ a₁ ]
// [ b₁ b ] [ b₁ b₁ ]
ng.A, ng.B = ng.A1, ng.B1
}
func (ng *NG4) egest(t int64) {
// [ a₁ a ] becomes [ b₁ b ]
// [ b₁ b ] [ a₁ - b₁×t a - b×t ]
ng.A1, ng.A, ng.B1, ng.B =
ng.B1, ng.B,
ng.A1-ng.B1*t, ng.A-ng.B*t
}
// ApplyTo "applies" the matrix `ng` to the continued fraction `cf`,
// returning the resulting continued fraction.
func (ng NG4) ApplyTo(cf ContinuedFraction) ContinuedFraction {
return func() NextFn {
next := cf()
done := false
return func() (int64, bool) {
if done {
return 0, false
}
for ng.needsIngest() {
if t, ok := next(); ok {
ng.ingest(t)
} else {
ng.ingestInfinite()
}
}
t := ng.A1 / ng.B1
ng.egest(t)
done = ng.isDone()
return t, true
}
}
}
File ng4_test.go
:
package cf
import (
"fmt"
"reflect"
"testing"
)
func Example_NG4() {
cases := [...]struct {
r Rat
ng NG4
}{
{Rat{13, 11}, NG4{2, 1, 0, 2}},
{Rat{22, 7}, NG4{2, 1, 0, 2}},
{Rat{22, 7}, NG4{1, 0, 0, 4}},
}
for _, tc := range cases {
cf := tc.r.AsContinuedFraction()
fmt.Printf("%5s = %-9s with %v gives %v\n", tc.r, cf.String(), tc.ng,
tc.ng.ApplyTo(cf),
)
}
invSqrt2 := NG4{0, 1, 1, 0}.ApplyTo(Sqrt2)
fmt.Println(" 1/√2 =", invSqrt2)
result := NG4{1, 1, 0, 2}.ApplyTo(Sqrt2)
fmt.Println("(1+√2)/2 =", result)
// Output:
// 13/11 = [1; 5, 2] with {2 1 0 2} gives [1; 1, 2, 7]
// 22/7 = [3; 7] with {2 1 0 2} gives [3; 1, 1, 1, 4]
// 22/7 = [3; 7] with {1 0 0 4} gives [0; 1, 3, 1, 2]
// 1/√2 = [0; 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...]
// (1+√2)/2 = [1; 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, ...]
}
- Output:
13/11 = [1; 5, 2] with {2 1 0 2} gives [1; 1, 2, 7] 22/7 = [3; 7] with {2 1 0 2} gives [3; 1, 1, 1, 4] 22/7 = [3; 7] with {1 0 0 4} gives [0; 1, 3, 1, 2] 1/√2 = [0; 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...] (1+√2)/2 = [1; 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, ...]
J
Note that the continued fraction representation used here differs from those implemented in the Continued_fraction fraction task. In that task, we alternated a and b values. Here, we only work with a values -- b is implicitly always 1
.
Implementation:
ng4cf=: 4 : 0
cf=. 1000{.!._ y
ng=. x
r=.i. ndx=.0
while. +./0~:{:ng do.
if.=/<.%/ng do.
r=.r, t=.{.<.%/ng
ng=. t (|.@] - ]*0,[) ng
else.
if. _=t=.ndx{cf do.
ng=. ng+/ .*2 2$1 1 0 0
else.
ng=. ng+/ .*2 2$t,1 1 0
end.
if. (#cf)=ndx=. ndx+1 do. r return. end.
end.
end.
r
)
Notes:
- we arbitrarily stop processing continued fractions after 1000 elements. That's more than enough precision for most purposes.
- we can convert a continued fraction to a rational number using
(+%)/
though if we want the full represented precision we should instead use(+%)/@x:
(which is slower).
- we can convert a rational number to a continued fraction using
1 1 {."1@}. ({: , (0 , {:) #: {.)^:(*@{:)^:a:
but also this expects a numerator,denominator pair so if you have only a single number use,&1
to give it a denominator. This works equally well with floating point and arbitrary precision numbers.
Some arbitrary continued fractions and their floating point representations
arbs=:(,1);(,3);?~&.>3+i.10
":@>arbs
1
3
1 2 0
0 2 3 1
1 0 3 2 4
0 2 3 5 1 4
2 5 0 1 6 3 4
7 5 6 3 0 4 1 2
7 0 1 2 6 3 8 4 5
8 0 5 6 3 7 4 9 1 2
0 9 8 1 3 10 2 5 6 7 4
1 7 3 4 5 8 9 10 6 11 0 2
(+%)/@>arbs
1 3 1 0.444444 4.44444 0.431925 2.16238 7.19368 8.46335 13.1583 0.109719 1.13682
Some NG based cf functions, verifying their behavior against our test set:
plus1r2=: (2 1,:0 2)&ng4cf
(plus1r2 each -&((+%)/@>) ]) arbs
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5
For every one of our arbitrary continued fractions, the 2 1,:0 2 NG matrix gives us a new continued fraction whose rational value is the original rational value + 1r2.
times7r22=: (7 0,:0 22)&ng4cf
(times7r22 each %&((+%)/@>) ]) arbs
0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182 0.318182
(times7r22 each %&((+%)/@x:@>) ]) arbs
7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22 7r22
For every one of our arbitrary continued fractions, the 7 0,:0 22 NG matrix gives us a new continued fraction whose rational value is 7r22 times the original rational value.
times1r4=:(1 0,:0 4)&ng4cf
(times1r4 each %&((+%)/@>) ]) arbs
0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25
It seems like a diagonal matrix has the effect of multiplying the numerator by the upper left element and the denominator by the lower right element. And our first experiment suggests that an upper right element in NG with a 0 for the bottom left will add the top right divided by bottom right to our continued fraction.
reciprocal=:(0 1,:1 0)&ng4cf
(reciprocal each *&((+%)/@>) ]) arbs
1 1 1 1 1 1 1 1 1 1 1 1
Looks like we can also divide by our continued fraction...
plus1r2times1r2=: (1 1,:0 2)&ng4cf
(plus1r2times1r2 each (= 0.5+0.5*])&((+%)/@>) ]) arbs
1 1 1 1 1 1 1 1 1 1 1 1
We can add and multiply using a single "ng4" operation.
Task examples:
1r2 + 13r11
(+%)/1 5 2
1.18182
plus1r2 1 5 2
1 1 2 7
(+%)/plus1r2 1 5 2
1.68182
7r22 * 22r7
(+%)/3 7x
22r7
times7r22 3 7x
1
1r2 + 22r7
plus1r2 3 7x
3 1 1 1 4
(+%)/plus1r2 3 7x
3.64286
(+%)/x:plus1r2 3 7x
51r14
1r4 * 22r7
times1r4 3 7x
0 1 3 1 2
(+%)/x:times1r4 3 7x
11r14
reciprocal 1,999$2
0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
(+%)/1,999$2
1.41421
(+%)/reciprocal 1,999$2
0.707107
plus1r2times1r2 1,999$2
1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 ...
(+%)/plus1r2times1r2 1,999$2
1.20711
plus1r2times1r2 0 1,999$2
0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 ...
(+%)/plus1r2times1r2 0 1,999$2
0.853553
Julia
function r2cf(n1::Integer, n2::Integer)
ret = Int[]
while n2 != 0
n1, (t1, n2) = n2, divrem(n1, n2)
push!(ret, t1)
end
ret
end
r2cf(r::Rational) = r2cf(numerator(r), denominator(r))
function r2cf(n1, n2, maxiter=20)
ret = Int[]
while n2 != 0 && maxiter > 0
n1, (t1, n2) = n2, divrem(n1, n2)
push!(ret, t1)
maxiter -= 1
end
ret
end
mutable struct NG
a1::Int
a::Int
b1::Int
b::Int
end
function ingress(ng, n)
ng.a, ng.a1= ng.a1, ng.a + ng.a1 * n
ng.b, ng.b1 = ng.b1, ng.b + ng.b1 * n
end
needterm(ng) = ng.b == 0 || ng.b1 == 0 || !(ng.a // ng.b == ng.a1 // ng.b1)
function egress(ng)
n = ng.a // ng.b
ng.a, ng.b = ng.b, ng.a - ng.b * n
ng.a1, ng.b1 = ng.b1, ng.a1 - ng.b1 * n
r2cf(n)
end
egress_done(ng) = (if needterm(ng) ng.a, ng.b = ng.a1, ng.b1 end; egress(ng))
done(ng) = ng.b == 0 && ng.b1 == 0
function testng()
data = [["[1;5,2] + 1/2", [2,1,0,2], [13,11]],
["[3;7] + 1/2", [2,1,0,2], [22, 7]],
["[3;7] divided by 4", [1,0,0,4], [22, 7]],
["[1;1] divided by sqrt(2)", [0,1,1,0], [1,sqrt(2)]]]
for d in data
str, ng, r = d[1], NG(d[2]...), d[3]
print(rpad(str, 25), "->")
for n in r2cf(r...)
if !needterm(ng)
print(" $(egress(ng))")
end
ingress(ng, n)
end
while true
print(" $(egress_done(ng))")
if done(ng)
println()
break
end
end
end
end
testng()
- Output:
[1;5,2] + 1/2 -> [1, 1, 2, 7] [3;7] + 1/2 -> [3, 1, 1, 1, 4] [3;7] divided by 4 -> [0, 1, 3, 1, 2] [1;1] divided by sqrt(2) -> [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Kotlin
This is based on the Python entry but has been expanded to deal with the '√2' calculations:
// version 1.1.3
// compile with -Xcoroutines=enable flag from command line
import kotlin.coroutines.experimental.*
typealias CFGenerator = (Pair<Int, Int>) -> Sequence<Int>
data class CFData(
val str: String,
val ng: IntArray,
val r: Pair<Int,Int>,
val gen: CFGenerator
)
fun r2cf(frac: Pair<Int, Int>) =
buildSequence {
var num = frac.first
var den = frac.second
while (Math.abs(den) != 0) {
val div = num / den
val rem = num % den
num = den
den = rem
yield(div)
}
}
fun d2cf(d: Double) =
buildSequence {
var dd = d
while (true) {
val div = Math.floor(dd)
val rem = dd - div
yield(div.toInt())
if (rem == 0.0) break
dd = 1.0 / rem
}
}
@Suppress("UNUSED_PARAMETER")
fun root2(dummy: Pair<Int, Int>) =
buildSequence {
yield(1)
while (true) yield(2)
}
@Suppress("UNUSED_PARAMETER")
fun recipRoot2(dummy: Pair<Int, Int>) =
buildSequence {
yield(0)
yield(1)
while (true) yield(2)
}
class NG(var a1: Int, var a: Int, var b1: Int, var b: Int) {
fun ingress(n: Int) {
var t = a
a = a1
a1 = t + a1 * n
t = b
b = b1
b1 = t + b1 * n
}
fun egress(): Int {
val n = a / b
var t = a
a = b
b = t - b * n
t = a1
a1 = b1
b1 = t - b1 * n
return n
}
val needTerm get() = (b == 0 || b1 == 0) || ((a / b) != (a1 / b1))
val egressDone: Int
get() {
if (needTerm) {
a = a1
b = b1
}
return egress()
}
val done get() = b == 0 && b1 == 0
}
fun main(args: Array<String>) {
val data = listOf(
CFData("[1;5,2] + 1/2 ", intArrayOf(2, 1, 0, 2), 13 to 11, ::r2cf),
CFData("[3;7] + 1/2 ", intArrayOf(2, 1, 0, 2), 22 to 7, ::r2cf),
CFData("[3;7] divided by 4 ", intArrayOf(1, 0, 0, 4), 22 to 7, ::r2cf),
CFData("sqrt(2) ", intArrayOf(0, 1, 1, 0), 0 to 0, ::recipRoot2),
CFData("1 / sqrt(2) ", intArrayOf(0, 1, 1, 0), 0 to 0, ::root2),
CFData("(1 + sqrt(2)) / 2 ", intArrayOf(1, 1, 0, 2), 0 to 0, ::root2),
CFData("(1 + 1 / sqrt(2)) / 2", intArrayOf(1, 1, 0, 2), 0 to 0, ::recipRoot2)
)
println("Produced by NG class:")
for ((str, ng, r, gen) in data) {
print("$str -> ")
val (a1, a, b1, b) = ng
val op = NG(a1, a, b1, b)
for (n in gen(r).take(20)) {
if (!op.needTerm) print(" ${op.egress()} ")
op.ingress(n)
}
while (true) {
print(" ${op.egressDone} ")
if (op.done) break
}
println()
}
println("\nProduced by direct calculation:")
val data2 = listOf(
Pair("(1 + sqrt(2)) / 2 ", (1 + Math.sqrt(2.0)) / 2),
Pair("(1 + 1 / sqrt(2)) / 2", (1 + 1 / Math.sqrt(2.0)) / 2)
)
for ((str, d) in data2) {
println("$str -> ${d2cf(d).take(20).joinToString(" ")}")
}
}
- Output:
Produced by NG class: [1;5,2] + 1/2 -> 1 1 2 7 [3;7] + 1/2 -> 3 1 1 1 4 [3;7] divided by 4 -> 0 1 3 1 2 sqrt(2) -> 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 / sqrt(2) -> 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 (1 + sqrt(2)) / 2 -> 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 (1 + 1 / sqrt(2)) / 2 -> 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 Produced by direct calculation: (1 + sqrt(2)) / 2 -> 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 (1 + 1 / sqrt(2)) / 2 -> 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1
Nim
import math, rationals, strformat
type
Rat = Rational[int]
Ng = tuple[a1, a, b1, b: int]
const NS = 1 // 1 # Non significant value.
iterator r2cf(rat: Rat): int {.closure.} =
var
num = rat.num
den = rat.den
for count in 1..20:
let d = num div den
num = num mod den
swap num, den
yield d
if den == 0: break
iterator d2cf(f: float): int {.closure.} =
var f = f
for count in 1..20:
let d = floor(f)
let r = f - d
yield int(d)
if r == 0: break
f = 1 / r
iterator root2(dummy: Rat): int {.closure.} =
yield 1
for count in 1..20: yield 2
iterator recipRoot2(rat: Rat): int {.closure.} =
yield 0
yield 1
for count in 1..20: yield 2
func ingress(ng: var Ng; n: int) =
ng.a += ng.a1 * n
swap ng.a, ng.a1
ng.b += ng.b1 * n
swap ng.b, ng.b1
func egress(ng: var Ng): int =
let n = ng.a div ng.b
ng.a -= ng.b * n
swap ng.a, ng.b
ng.a1 -= ng.b1 * n
swap ng.a1, ng.b1
result = n
func needTerm(ng: Ng): bool = ng.b == 0 or ng.b1 == 0 or (ng.a // ng.b != ng.a1 // ng.b1)
func egressDone(ng: var Ng): int =
if ng.needTerm:
ng.a = ng.a1
ng.b = ng.b1
result = ng.egress()
func done(ng: Ng): bool = ng.b == 0 or ng.b1 == 0
when isMainModule:
let data = [("[1;5,2] + 1/2 ", (2, 1, 0, 2), 13 // 11, r2cf),
("[3;7] + 1/2 ", (2, 1, 0, 2), 22 // 7, r2cf),
("[3;7] divided by 4 ", (1, 0, 0, 4), 22 // 7, r2cf),
("sqrt(2) ", (0, 1, 1, 0), NS, recipRoot2),
("1 / sqrt(2) ", (0, 1, 1, 0), NS, root2),
("(1 + sqrt(2)) / 2 ", (1, 1, 0, 2), NS, root2),
("(1 + 1 / sqrt(2)) / 2", (1, 1, 0, 2), NS, recipRoot2)]
echo "Produced by NG object:"
for (str, ng, r, gen) in data:
stdout.write &"{str} → "
var op = ng
for n in gen(r):
if not op.needTerm: stdout.write &" {op.egress()} "
op.ingress(n)
while true:
stdout.write &" {op.egressDone} "
if op.done: break
echo()
echo "\nProduced by direct calculation:"
let data2 = [("(1 + sqrt(2)) / 2 ", (1 + sqrt(2.0)) / 2),
("(1 + 1 / sqrt(2)) / 2", (1 + 1 / sqrt(2.0)) / 2)]
for (str, d) in data2:
stdout.write &"{str} →"
for n in d2cf(d): stdout.write " ", n
echo()
- Output:
Produced by NG object: [1;5,2] + 1/2 → 1 1 2 7 [3;7] + 1/2 → 3 1 1 1 4 [3;7] divided by 4 → 0 1 3 1 2 sqrt(2) → 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 / sqrt(2) → 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 (1 + sqrt(2)) / 2 → 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 (1 + 1 / sqrt(2)) / 2 → 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 Produced by direct calculation: (1 + sqrt(2)) / 2 → 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 (1 + 1 / sqrt(2)) / 2 → 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1
Phix
Self-contained. The supporting cast of r2cf(), cf2s(), cf2r() and d2cf() ended up being more code than the task itself.
requires("0.8.2")
class baby_matrix
integer a1, a, b1, b
--
-- used by apply_baby_matrix to yield (a1*cf+a)/(b1*cf+b)
--
-- examples: (a1 a b1 b) => above, simplified:
-- ======== = = = =
-- {2, 1, 0, 2} => (2*cf+1)/2, aka cf+1/2
-- {1, 0, 0, 4} => cf/4
-- {1, 0, 0, 1} => cf/1, aka cf
-- {0, 1, 1, 0} => 1/cf
-- {1, 1, 0, 2} => (cf+1)/2
--
function need_term()
return b==0 or b1==0 or ((a/b)!=(a1/b1))
end function
function next_term()
integer n = floor(a/b)
{a1,a,b1,b} = {b1,b,a1-b1*n,a-b*n}
return n
end function
procedure in_term(object n={})
if integer(n) then
{a1,a,b,b1} = {a+a1*n,a1,b1,b+b1*n}
else
{a,b} = {a1,b1}
end if
end procedure
function done()
return b=0 and b1=0
end function
end class
function apply_baby_matrix(sequence m, cf)
--
-- for m of integer {a1,a,b1,b}, return (a1*cf+a)/(b1*cf+b):
--
baby_matrix bm = new(m)
sequence res = {}
for i=1 to length(cf) do
if not bm.need_term() then
res &= bm.next_term()
end if
bm.in_term(cf[i])
end for
while true do
if bm.need_term() then
bm.in_term()
end if
res &= bm.next_term()
if bm.done() then exit end if
end while
return res
end function
function r2cf(sequence rat, integer count=20)
sequence s = {}
atom {num,den} = rat
while den!=0 and length(s)<count do
s &= trunc(num/den)
{num,den} = {den,num-s[$]*den}
end while
return s
end function
function root2(integer count=20)
return {1}&repeat(2,count-1)
end function
function recip_root2(integer count=20)
return {0,1}&repeat(2,count-2)
end function
function cf2s(sequence cf)
sequence s = join(apply(cf,sprint),",") -- eg "1,5,2"
return "["&substitute(s,",",";",1)&"]" -- => "[1;5,2]"
end function
include mpfr.e
function cf2r(sequence cf)
mpq res = mpq_init(), -- 0/1
cfn = mpq_init()
for n=length(cf) to 1 by -1 do
mpq_set_si(cfn,cf[n])
mpq_add(res,res,cfn)
if n=1 then exit end if
mpq_inv(res,res)
end for
mpz num = mpz_init(),
den = mpz_init()
mpq_get_num(num,res)
mpq_get_den(den,res)
mpfr x = mpfr_init()
mpfr_set_q(x,res)
string xs = mpfr_sprintf("%.15Rf",x),
ns = mpz_get_str(num),
ds = mpz_get_str(den),
s = sprintf("%s (%s/%s)",{xs,ns,ds})
return s
end function
function d2cf(atom d, integer count=20)
string res = "["
integer sep = ';'
while count do
atom div = floor(d),
rem = d - div
res &= sprintf("%d%c",{div,sep})
if rem==0 then exit end if
d = 1/rem
count -= 1
sep = ','
end while
res[$] = ']'
return res
end function
constant tests = {
{"[1;5,2] + 1/2 ", {2, 1, 0, 2}, r2cf({13,11}), 37/22},
{"[3;7] + 1/2 ", {2, 1, 0, 2}, r2cf({22, 7}), 3+1/7+1/2},
{"[3;7] / 4 ", {1, 0, 0, 4}, r2cf({22, 7}), (3+1/7)/4},
{"sqrt(2) ", {1, 0, 0, 1}, root2(), sqrt(2)},
{"sqrt(2) (inv) ", {0, 1, 1, 0}, recip_root2(), 1/(1/sqrt(2))},
{"1/sqrt(2) ", {1, 0, 0, 1}, recip_root2(), 1/sqrt(2)},
{"1/sqrt(2) (inv)", {0, 1, 1, 0}, root2(), 1/sqrt(2)},
{"(1+sqrt(2))/2 ", {1, 1, 0, 2}, root2(), (1+sqrt(2))/2},
{"(1+1/sqrt(2))/2", {1, 1, 0, 2}, recip_root2(), (1+1/sqrt(2))/2}}
for i=1 to length(tests) do
{string str, sequence bm, sequence cf, atom eres} = tests[i]
sequence res = apply_baby_matrix(bm, cf)
printf(1,"%s -> %s --> %s\n",{str,cf2s(res),cf2r(res)})
printf(1," direct: %s ==> %.15f\n",{d2cf(eres,length(res)),eres})
end for
- Output:
[1;5,2] + 1/2 -> [1;1,2,7] --> 1.681818181818182 (37/22) direct: [1;1,2,6] ==> 1.681818181818182 [3;7] + 1/2 -> [3;1,1,1,4] --> 3.642857142857143 (51/14) direct: [3;1,1,1,3] ==> 3.642857142857143 [3;7] / 4 -> [0;1,3,1,2] --> 0.785714285714286 (11/14) direct: [0;1,3,1,2] ==> 0.785714285714286 sqrt(2) -> [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] --> 1.414213562373096 (22619537/15994428) direct: [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] ==> 1.414213562373095 sqrt(2) (inv) -> [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] --> 1.414213562373087 (9369319/6625109) direct: [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] ==> 1.414213562373095 1/sqrt(2) -> [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] --> 0.707106781186552 (6625109/9369319) direct: [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] ==> 0.707106781186547 1/sqrt(2) (inv) -> [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] --> 0.707106781186547 (15994428/22619537) direct: [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] ==> 0.707106781186547 (1+sqrt(2))/2 -> [1;4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4] --> 1.207106781186548 (38613965/31988856) direct: [1;4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4] ==> 1.207106781186547 (1+1/sqrt(2))/2 -> [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,5] --> 0.853553390593276 (7997214/9369319) direct: [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4] ==> 0.853553390593274
The last digits of direct in the first two tests match on 64-bit, ie ,7] and ,4], plus 6/7/8 end in 548.
Python
Python: NG
class NG:
def __init__(self, a1, a, b1, b):
self.a1, self.a, self.b1, self.b = a1, a, b1, b
def ingress(self, n):
self.a, self.a1 = self.a1, self.a + self.a1 * n
self.b, self.b1 = self.b1, self.b + self.b1 * n
@property
def needterm(self):
return (self.b == 0 or self.b1 == 0) or not self.a//self.b == self.a1//self.b1
@property
def egress(self):
n = self.a // self.b
self.a, self.b = self.b, self.a - self.b * n
self.a1, self.b1 = self.b1, self.a1 - self.b1 * n
return n
@property
def egress_done(self):
if self.needterm: self.a, self.b = self.a1, self.b1
return self.egress
@property
def done(self):
return self.b == 0 and self.b1 == 0
Python: Testing
Uses r2cf method from here.
data = [["[1;5,2] + 1/2", [2,1,0,2], [13,11]],
["[3;7] + 1/2", [2,1,0,2], [22, 7]],
["[3;7] divided by 4", [1,0,0,4], [22, 7]]]
for string, ng, r in data:
print( "%-20s->" % string, end='' )
op = NG(*ng)
for n in r2cf(*r):
if not op.needterm: print( " %r" % op.egress, end='' )
op.ingress(n)
while True:
print( " %r" % op.egress_done, end='' )
if op.done: break
print()
- Output:
[1;5,2] + 1/2 -> 1 1 2 7 [3;7] + 1/2 -> 3 1 1 1 4 [3;7] divided by 4 -> 0 1 3 1 2
Racket
Main part of the NG-baby matrices. They are implemented as mutable structs.
#lang racket/base
(struct ng (a1 a b1 b) #:transparent #:mutable)
(define (ng-ingress! v t)
(define a (ng-a v))
(define a1 (ng-a1 v))
(define b (ng-b v))
(define b1 (ng-b1 v))
(set-ng-a! v a1)
(set-ng-a1! v (+ a (* a1 t)))
(set-ng-b! v b1)
(set-ng-b1! v (+ b (* b1 t))))
(define (ng-needterm? v)
(or (zero? (ng-b v))
(zero? (ng-b1 v))
(not (= (quotient (ng-a v) (ng-b v)) (quotient (ng-a1 v) (ng-b1 v))))))
(define (ng-egress! v)
(define t (quotient (ng-a v) (ng-b v)))
(define a (ng-a v))
(define a1 (ng-a1 v))
(define b (ng-b v))
(define b1 (ng-b1 v))
(set-ng-a! v b)
(set-ng-a1! v b1)
(set-ng-b! v (- a (* b t)))
(set-ng-b1! v (- a1 (* b1 t)))
t)
(define (ng-infty! v)
(when (ng-needterm? v)
(set-ng-a! v (ng-a1 v))
(set-ng-b! v (ng-b1 v))))
(define (ng-done? v)
(and (zero? (ng-b v)) (zero? (ng-b1 v))))
Auxiliary functions to create producers of well known continued fractions. The function rational->cf is copied from r2cf task.
(define ((rational->cf n d))
(and (not (zero? d))
(let-values ([(q r) (quotient/remainder n d)])
(set! n d)
(set! d r)
q)))
(define (sqrt2->cf)
(define first? #t)
(lambda ()
(if first?
(begin
(set! first? #f)
1)
2)))
The function combine-ng-cf->cf combines a ng-matrix and a cf- producer and creates a cf-producer. The cf-producers can represent infinitely long continued fractions. The function cf-showln shows the first coefficients of a continued fraction represented in a cf-producer.
(define (combine-ng-cf->cf ng cf)
(define empty-producer? #f)
(lambda ()
(let loop ()
(cond
[(not empty-producer?) (define t (cf))
(cond
[t (ng-ingress! ng t)
(if (ng-needterm? ng)
(loop)
(ng-egress! ng))]
[else (set! empty-producer? #t)
(loop)])]
[(ng-done? ng) #f]
[(ng-needterm? ng) (ng-infty! ng)
(loop)]
[else (ng-egress! ng)]))))
(define (cf-showln cf n)
(for ([i (in-range n)])
(define val (cf))
(when val
(printf " ~a" val)))
(when (cf)
(printf " ..."))
(printf "~n"))
Some test
(display "[1;5,2] + 1/2 ->")
(cf-showln (combine-ng-cf->cf (ng 2 1 0 2) (rational->cf 13 11)) 20)
(display "[3;7] + 1/2 ->")
(cf-showln (combine-ng-cf->cf (ng 2 1 0 2) (rational->cf 22 7)) 20)
(display "[3;7] / 4 ->")
(cf-showln (combine-ng-cf->cf (ng 1 0 0 4) (rational->cf 22 7)) 20)
(display "sqrt(2)/2 ->")
(cf-showln (combine-ng-cf->cf (ng 1 0 0 2) (sqrt2->cf)) 20)
(display "1/sqrt(2) ->")
(cf-showln (combine-ng-cf->cf (ng 0 1 1 0) (sqrt2->cf)) 20)
(display "(1+sqrt(2))/2 ->")
(cf-showln (combine-ng-cf->cf (ng 1 1 0 2) (sqrt2->cf)) 20)
Sample output:
[1;5,2] + 1/2 -> 1 1 2 7 [3;7] + 1/2 -> 3 1 1 1 4 [3;7] / 4 -> 0 1 3 1 2 sqrt(2)/2 -> 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... 1/sqrt(2) -> 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... (1+sqrt(2))/2 -> 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 ...
Raku
(formerly Perl 6)
All the important stuff takes place in the NG object. Everything else is helper subs for testing and display. The NG object is capable of working with infinitely long continued fractions, but displaying them can be problematic. You can pass in a limit to the apply method to get a fixed maximum number of terms though. See the last example: 100 terms from the infinite cf (1+√2)/2 and its Rational representation.
class NG {
has ( $!a1, $!a, $!b1, $!b );
submethod BUILD ( :$!a1, :$!a, :$!b1, :$!b ) { }
# Public methods
method new( $a1, $a, $b1, $b ) { self.bless( :$a1, :$a, :$b1, :$b ) }
method apply(@cf, :$limit = Inf) {
(gather {
map { take self!extract unless self!needterm; self!inject($_) }, @cf;
take self!drain until self!done;
})[ ^ $limit ]
}
# Private methods
method !inject ($n) {
sub xform($n, $x, $y) { $x, $n * $x + $y }
( $!a, $!a1 ) = xform( $n, $!a1, $!a );
( $!b, $!b1 ) = xform( $n, $!b1, $!b );
}
method !extract {
sub xform($n, $x, $y) { $y, $x - $y * $n }
my $n = $!a div $!b;
($!a, $!b ) = xform( $n, $!a, $!b );
($!a1, $!b1) = xform( $n, $!a1, $!b1 );
$n
}
method !drain { $!a = $!a1, $!b = $!b1 if self!needterm; self!extract }
method !needterm { so [||] !$!b, !$!b1, $!a/$!b != $!a1/$!b1 }
method !done { not [||] $!b, $!b1 }
}
sub r2cf(Rat $x is copy) { # Rational to continued fraction
gather loop {
$x -= take $x.floor;
last if !$x;
$x = 1 / $x;
}
}
sub cf2r(@a) { # continued fraction to Rational
my $x = @a[* - 1]; # Use FatRats for arbitrary precision
$x = ( @a[$_- 1] + 1 / $x ).FatRat for reverse 1 ..^ @a;
$x
}
sub ppcf(@cf) { # format continued fraction for pretty printing
"[{ @cf.join(',').subst(',',';') }]"
}
sub pprat($a) { # format Rational for pretty printing
# Use FatRats for arbitrary precision
$a.FatRat.denominator == 1 ?? $a !! $a.FatRat.nude.join('/')
}
sub test_NG ($rat, @ng, $op) {
my @cf = $rat.Rat(1e-18).&r2cf;
my @op = NG.new( |@ng ).apply( @cf );
say $rat.raku, ' as a cf: ', @cf.&ppcf, " $op = ",
@op.&ppcf, "\tor ", @op.&cf2r.&pprat, "\n";
}
# Testing
test_NG(|$_) for (
[ 13/11, [<2 1 0 2>], '+ 1/2 ' ],
[ 22/7, [<2 1 0 2>], '+ 1/2 ' ],
[ 22/7, [<1 0 0 4>], '/ 4 ' ],
[ 22/7, [<7 0 0 22>], '* 7/22 ' ],
[ 2**.5, [<1 1 0 2>], "\n(1+√2)/2 (approximately)" ]
);
say '100 terms of (1+√2)/2 as a continued fraction and as a rational value:';
my @continued-fraction = NG.new( 1,1,0,2 ).apply( (lazy flat 1, 2 xx * ), limit => 100 );
say @continued-fraction.&ppcf.comb(/ . ** 1..80/).join("\n");
say @continued-fraction.&cf2r.&pprat;
- Output:
<13/11> as a cf: [1;5,2] + 1/2 = [1;1,2,7] or 37/22 <22/7> as a cf: [3;7] + 1/2 = [3;1,1,1,4] or 51/14 <22/7> as a cf: [3;7] / 4 = [0;1,3,1,2] or 11/14 <22/7> as a cf: [3;7] * 7/22 = [1] or 1 1.4142135623731e0 as a cf: [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] (1+√2)/2 (approximately) = [1;4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4] or 225058681/186444716 100 terms of (1+√2)/2 and its rational value [1;4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4 ,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4 ,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4] 161733217200188571081311986634082331709/133984184101103275326877813426364627544
Ruby
NG
# I define a class to implement baby NG
class NG
def initialize(a1, a, b1, b)
@a1, @a, @b1, @b = a1, a, b1, b
end
def ingress(n)
@a, @a1 = @a1, @a + @a1 * n
@b, @b1 = @b1, @b + @b1 * n
end
def needterm?
return true if @b == 0 or @b1 == 0
return true unless @a/@b == @a1/@b1
false
end
def egress
n = @a / @b
@a, @b = @b, @a - @b * n
@a1, @b1 = @b1, @a1 - @b1 * n
n
end
def egress_done
@a, @b = @a1, @b1 if needterm?
egress
end
def done?
@b == 0 and @b1 == 0
end
end
Testing
Uses r2cf method from here.
data = [["[1;5,2] + 1/2", [2,1,0,2], [13,11]],
["[3;7] + 1/2", [2,1,0,2], [22, 7]],
["[3;7] divided by 4", [1,0,0,4], [22, 7]]]
data.each do |str, ng, r|
printf "%-20s->", str
op = NG.new(*ng)
r2cf(*r) do |n|
print " #{op.egress}" unless op.needterm?
op.ingress(n)
end
print " #{op.egress_done}" until op.done?
puts
end
- Output:
[1;5,2] + 1/2 -> 1 1 2 7 [3;7] + 1/2 -> 3 1 1 1 4 [3;7] divided by 4 -> 0 1 3 1 2
Tcl
This uses the Generator
class, R2CF
class and printcf
procedure from the r2cf task.
# The single-operand version of the NG operator, using our little generator framework
oo::class create NG1 {
superclass Generator
variable a1 a b1 b cf
constructor args {
next
lassign $args a1 a b1 b
}
method Ingress n {
lassign [list [expr {$a + $a1*$n}] $a1 [expr {$b + $b1*$n}] $b1] \
a1 a b1 b
}
method NeedTerm? {} {
expr {$b1 == 0 || $b == 0 || $a/$b != $a1/$b1}
}
method Egress {} {
set n [expr {$a/$b}]
lassign [list $b1 $b [expr {$a1 - $b1*$n}] [expr {$a - $b*$n}]] \
a1 a b1 b
return $n
}
method EgressDone {} {
if {[my NeedTerm?]} {
set a $a1
set b $b1
}
tailcall my Egress
}
method Done? {} {
expr {$b1 == 0 && $b == 0}
}
method operand {N} {
set cf $N
return [self]
}
method Produce {} {
while 1 {
set n [$cf]
if {![my NeedTerm?]} {
yield [my Egress]
}
my Ingress $n
}
while {![my Done?]} {
yield [my EgressDone]
}
}
}
Demonstrating:
# The square root of 2 as a continued fraction in the framework
oo::class create Root2 {
superclass Generator
method apply {} {
yield 1
while {[self] ne ""} {
yield 2
}
}
}
set op [[NG1 new 2 1 0 2] operand [R2CF new 13/11]]
printcf "\[1;5,2\] + 1/2" $op
set op [[NG1 new 7 0 0 22] operand [R2CF new 22/7]]
printcf "\[3;7\] * 7/22" $op
set op [[NG1 new 2 1 0 2] operand [R2CF new 22/7]]
printcf "\[3;7\] + 1/2" $op
set op [[NG1 new 1 0 0 4] operand [R2CF new 22/7]]
printcf "\[3;7\] / 4" $op
set op [[NG1 new 0 1 1 0] operand [Root2 new]]
printcf "1/\u221a2" $op 20
set op [[NG1 new 1 1 0 2] operand [Root2 new]]
printcf "(1+\u221a2)/2" $op 20
printcf "approx val" [R2CF new 24142136 20000000]
- Output:
[1;5,2] + 1/2 -> 1,1,2,7 [3;7] * 7/22 -> 1 [3;7] + 1/2 -> 3,1,1,1,4 [3;7] / 4 -> 0,1,3,1,2 1/√2 -> 0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,… (1+√2)/2 -> 1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,… approx val -> 1,4,1,4,1,4,1,4,1,4,3,2,1,9,5
Wren
import "/dynamic" for Tuple
var CFData = Tuple.create("Tuple", ["str", "ng", "r", "gen"])
var r2cf = Fn.new { |frac|
var num = frac[0]
var den = frac[1]
while (den.abs != 0) {
var div = (num/den).truncate
var rem = num % den
num = den
den = rem
Fiber.yield(div)
}
}
var d2cf = Fn.new { |d|
while (true) {
var div = d.floor
var rem = d - div
Fiber.yield(div)
if (rem == 0) break
d = 1 / rem
}
}
var root2 = Fn.new {
Fiber.yield(1)
while (true) Fiber.yield(2)
}
var recipRoot2 = Fn.new {
Fiber.yield(0)
Fiber.yield(1)
while (true) Fiber.yield(2)
}
class NG {
construct new(a1, a, b1, b) {
_a1 = a1
_a = a
_b1 = b1
_b = b
}
ingress(n) {
var t = _a
_a = _a1
_a1 = t + _a1 * n
t = _b
_b = _b1
_b1 = t + _b1 * n
}
egress() {
var n = (_a/_b).truncate
var t = _a
_a = _b
_b = t - _b * n
t = _a1
_a1 = _b1
_b1 = t - _b1 * n
return n
}
needTerm { (_b == 0 || _b1 == 0) || ((_a / _b) != (_a1 / _b1)) }
egressDone {
if (needTerm) {
_a = _a1
_b = _b1
}
return egress()
}
done { _b == 0 && _b1 == 0 }
}
var data = [
CFData.new("[1;5,2] + 1/2 ", [2, 1, 0, 2], [13, 11], r2cf),
CFData.new("[3;7] + 1/2 ", [2, 1, 0, 2], [22, 7], r2cf),
CFData.new("[3;7] divided by 4 ", [1, 0, 0, 4], [22, 7], r2cf),
CFData.new("sqrt(2) ", [0, 1, 1, 0], [ 0, 0], recipRoot2),
CFData.new("1 / sqrt(2) ", [0, 1, 1, 0], [ 0, 0], root2),
CFData.new("(1 + sqrt(2)) / 2 ", [1, 1, 0, 2], [ 0, 0], root2),
CFData.new("(1 + 1 / sqrt(2)) / 2", [1, 1, 0, 2], [ 0, 0], recipRoot2)
]
System.print("Produced by NG class:")
for (cfd in data) {
System.write("%(cfd.str) -> ")
var a1 = cfd.ng[0]
var a = cfd.ng[1]
var b1 = cfd.ng[2]
var b = cfd.ng[3]
var op = NG.new(a1, a, b1, b)
var seq = []
var i = 0
var fib = Fiber.new(cfd.gen)
while (i < 20) {
var j = fib.call(cfd.r)
if (j) seq.add(j) else break
i = i + 1
}
for (n in seq) {
if (!op.needTerm) System.write(" %(op.egress()) ")
op.ingress(n)
}
while (true) {
System.write(" %(op.egressDone) ")
if (op.done) break
}
System.print()
}
System.print("\nProduced by direct calculation:")
var data2 = [
["(1 + sqrt(2)) / 2 ", (1 + 2.sqrt) / 2],
["(1 + 1 / sqrt(2)) / 2", (1 + 1 / 2.sqrt) / 2]
]
for (p in data2) {
var seq = []
var fib = Fiber.new(d2cf)
var i = 0
while (i < 20) {
var j = fib.call(p[1])
if (j) seq.add(j) else break
i = i + 1
}
System.print("%(p[0]) -> %(seq.join(" "))")
}
- Output:
Produced by NG class: [1;5,2] + 1/2 -> 1 1 2 7 [3;7] + 1/2 -> 3 1 1 1 4 [3;7] divided by 4 -> 0 1 3 1 2 sqrt(2) -> 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 / sqrt(2) -> 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 (1 + sqrt(2)) / 2 -> 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 (1 + 1 / sqrt(2)) / 2 -> 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5 Produced by direct calculation: (1 + sqrt(2)) / 2 -> 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 (1 + 1 / sqrt(2)) / 2 -> 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1
zkl
class NG{
fcn init(_a1,_a, _b1,_b){ var a1=_a1,a=_a, b1=_b1,b=_b; }
var [proxy] done =fcn{ b==0 and b1==0 };
var [proxy] needterm=fcn{ (b==0 or b1==0) or (a/b!=a1/b1) };
fcn ingress(n){
t:=self.copy(True); // tmp copy of vars for eager vs late evaluation
a,a1=t.a1, t.a + n*t.a1;
b,b1=t.b1, t.b + n*t.b1;
}
fcn egress{
n,t:=a/b,self.copy(True);
a,b =t.b, t.a - n*t.b;
a1,b1=t.b1,t.a1 - n*t.b1;
n
}
fcn egress_done{
if(needterm) a,b=a1,b1;
egress()
}
}
// from task: Continued fraction/Arithmetic/Construct from rational number
fcn r2cf(nom,dnom){ // -->Walker (iterator)
Walker.tweak(fcn(_,state){
nom,dnom:=state;
if(dnom==0) return(Void.Stop);
n,d:=nom.divr(dnom);
state.clear(dnom,d);
n
}.fp1(List(nom,dnom)))
}
data:=T(T("[1;5,2] + 1/2", T(2,1,0,2), T(13,11)),
T("[3;7] + 1/2", T(2,1,0,2), T(22, 7)),
T("[3;7] divided by 4", T(1,0,0,4), T(22, 7)));
foreach string,ng,r in (data){
print("%-20s-->".fmt(string));
op:=NG(ng.xplode());
foreach n in (r2cf(r.xplode())){
if(not op.needterm) print(" %s".fmt(op.egress()));
op.ingress(n);
}
do{ print(" ",op.egress_done()) }while(not op.done);
println();
}
- Output:
[1;5,2] + 1/2 --> 1 1 2 7 [3;7] + 1/2 --> 3 1 1 1 4 [3;7] divided by 4 --> 0 1 3 1 2