I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Continued fraction/Arithmetic/G(matrix ng, continued fraction n)

Continued fraction/Arithmetic/G(matrix ng, continued fraction n) is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

This task investigates mathmatical operations that can be performed on a single continued fraction. This requires only a baby version of NG:

${\displaystyle {\begin{bmatrix}a_{1}&a\\b_{1}&b\end{bmatrix}}}$

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 ${\displaystyle {\frac {a}{b}}}$ and ${\displaystyle {\frac {a_{1}}{b_{1}}}}$ are equal. Otherwise I input a term from N. If I need a term from N but N has no more terms I inject ${\displaystyle \infty }$.

When I input a term t my internal state: ${\displaystyle {\begin{bmatrix}a_{1}&a\\b_{1}&b\end{bmatrix}}}$ is transposed thus ${\displaystyle {\begin{bmatrix}a+a_{1}*t&a_{1}\\b+b_{1}*t&b_{1}\end{bmatrix}}}$

When I output a term t my internal state: ${\displaystyle {\begin{bmatrix}a_{1}&a\\b_{1}&b\end{bmatrix}}}$ is transposed thus ${\displaystyle {\begin{bmatrix}b_{1}&b\\a_{1}-b_{1}*t&a-b*t\end{bmatrix}}}$

When I need a term t but there are no more my internal state: ${\displaystyle {\begin{bmatrix}a_{1}&a\\b_{1}&b\end{bmatrix}}}$ is transposed thus ${\displaystyle {\begin{bmatrix}a_{1}&a_{1}\\b_{1}&b_{1}\end{bmatrix}}}$

I am done when b1 and b are zero.

[1;5,2] + 1/2
[3;7] + 1/2
[3;7] divided by 4

Using a generator for ${\displaystyle {\sqrt {2}}}$ (e.g., from Continued fraction) calculate ${\displaystyle {\frac {1}{\sqrt {2}}}}$. 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 ${\displaystyle {\frac {1+{\frac {1}{\sqrt {2}}}}{2}}}$ do this now to cross the starting line and begin the race.

## 11l

Translation of: Python
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


#### ${\displaystyle {\frac {1}{\sqrt {2}}}}$1 2 {\displaystyle {\frac {1}{\sqrt {2}}}}

First I generate ${\displaystyle {\frac {1}{\sqrt {2}}}}$ 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


#### ${\displaystyle {\frac {1+{\sqrt {2}}}{2}}}$1 + 2 2 {\displaystyle {\frac {1+{\sqrt {2}}}{2}}}

First I generate ${\displaystyle {\frac {1+{\sqrt {2}}}{2}}}$ 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 (|[email protected]] - ]*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 {."[email protected]}. ({: , (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   ":@>arbs1                        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   (+%)/@>arbs1 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.

1r2 + 13r11

   (+%)/1 5 21.18182   plus1r2 1 5 21 1 2 7   (+%)/plus1r2 1 5 21.68182

7r22 * 22r7

   (+%)/3 7x22r7   times7r22 3 7x1

1r2 + 22r7

   plus1r2 3 7x3 1 1 1 4   (+%)/plus1r2 3 7x3.64286   (+%)/x:plus1r2 3 7x51r14

1r4 * 22r7

   times1r4 3 7x0 1 3 1 2   (+%)/x:times1r4 3 7x11r14

${\displaystyle {\frac {1}{\sqrt {2}}}}$

   reciprocal 1,999$20 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$21.41421   (+%)/reciprocal 1,999$20.707107 ${\displaystyle {\frac {1+{\sqrt {2}}}{2}}}$  plus1r2times1r2 1,999$21 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 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$21.20711 ${\displaystyle {\frac {1+{\frac {1}{\sqrt {2}}}}{2}}}$  plus1r2times1r2 0 1,999$20 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$20.853553 ## Julia Translation of: Ruby function r2cf(n1::Integer, n2::Integer) ret = Int[] while n2 != 0 n1, (t1, n2) = n2, divrem(n1, n2) push!(ret, t1) end retendr2cf(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 retend mutable struct NG a1::Int a::Int b1::Int b::Intend 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 * nend 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 endend 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

Translation of: Kotlin
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

Library: Phix/Class
Library: Phix/mpfr

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 resend 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 send 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 send 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 resend 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

Translation of: Ruby

### 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

Translation of: Python
Translation of: C++

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)

Works with: Rakudo version 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.

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";} # Testingtest_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 NGclass 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 endend ### 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? putsend 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. Works with: Tcl version 8.6 Translation of: Ruby # The single-operand version of the NG operator, using our little generator frameworkoo::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 frameworkoo::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 20printcf "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

Translation of: Kotlin
Library: Wren-dynamic
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

Translation of: Python
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 numberfcn 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