Continued fraction/Arithmetic/Construct from rational number

To understand this task in context please see Continued fraction arithmetic

The purpose of this task is to write a function r2cf(int N₁, int N₂), or r2cf(Fraction N), which will output a continued fraction assuming:

N₁ is the numerator

N₂ is the denominator

The function should output its results one digit at a time each time it is called, in a manner sometimes described as lazy evaluation.

To achieve this it must determine: the integer part; and remainder part, of N₁ divided by N₂. It then sets N₁ to N₂ and N₂ to the determined remainder part. It then outputs the determined integer part. It does this until N₂ is zero.

Demonstrate the function by outputing the continued fraction for:

1/2

3

23/8

13/11

22/7

${\sqrt {2}}$ should approach [1; 2, 2, 2, 2, ...] try ever closer rational approximations until bordom gets the better of you:

14142,10000

141421,100000

1414214,1000000

4142136,10000000

Try :

31,10

314,100

3142,1000

31428,10000

314285,100000

3142857,1000000

31428571,10000000

314285714,100000000

Observe how this rational number behaves differently to ${\sqrt {2}}$ and convince yourself that in the same way as 3.7 may be represented as 3.70 when an extra decimal place is required [3;7] may be represented as [3;7, $\infty$ ] when an extra term is required.

C++

include <iostream>

/* Interface for all Continued Fractions

  Nigel Galloway, February 9th., 2013.

/

class ContinuedFraction { private: public: virtual const int nextTerm(){}; virtual const bool moreTerms(){}; }; /* Create a continued fraction from a rational number

  Nigel Galloway, February 9th., 2013.

/

class r2cf : ContinuedFraction { private: int n1, n2; public: r2cf(const int numerator, const int denominator) { n1 = numerator; n2 = denominator; } const int nextTerm() { const int thisTerm = n1/n2; const int t2 = n2; n2 = n1 - thisTerm * n2; n1 = t2; return thisTerm; } const bool moreTerms() {return n2 > 0;} }; /* Generate a continued fraction for sqrt of 2

  Nigel Galloway, February 9th., 2013.

/

class SQRT2 : public ContinuedFraction { private: bool first=true; public: const int nextTerm() {if (first) {first = false; return 1;} else return 2;} const bool moreTerms() {return true;} }; </lang>

Testing

1/2 3 23/8 13/11 22/7

<lang cpp> int main() { for(r2cf n(1,2); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(3,1); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(23,8); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(13,11); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; for(r2cf n(22,7); n.moreTerms(); std::cout << n.nextTerm() << " "); std::cout << std::endl; return 0; } </lang>

Output:

${\sqrt {2}}$

Output:

1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 2 2 2 2 2 1 1 29
1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2

Real approximations of a rational number

<lang cpp> int main() {

 for(r2cf n(31,10); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 for(r2cf n(314,100); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 for(r2cf n(3142,1000); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 for(r2cf n(31428,10000); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 for(r2cf n(314285,100000); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 for(r2cf n(3142857,1000000); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 for(r2cf n(31428571,10000000); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 for(r2cf n(314285714,100000000); n.moreTerms(); std::cout << n.nextTerm() << " ");
 std::cout << std::endl;
 return 0;

} </lang>

Output:

3 10
3 7 7
3 7 23 1 2
3 7 357
3 7 2857
3 7 142857
3 7 476190 3
3 7 7142857

Perl 6

Straightforward implementation: <lang perl6>sub r2cf(Rat $x is copy) {

   gather loop {

$x -= take $x.floor; last unless $x > 0; $x = 1 / $x;

}

say r2cf(.Rat) for <1/2 3 23/8 13/11 22/7 1.41 1.4142136>;</lang>

Output:

0 2
3
2 1 7
1 5 2
3 7
1 2 2 3 1 1 2
1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2

As a silly one-liner: <lang perl6>sub r2cf(Rat $x is copy) { gather $x [R/]= 1 while ($x -= take $x.floor) > 0 }</lang>

Ruby

<lang ruby> =begin

 Generate a continued fraction from a rational number

 Nigel Galloway, February 4th., 2013

=end def r2cf(n1,n2)

 while n2 > 0
   t1 = n1/n2; t2 = n2; n2 = n1 - t1 * n2; n1 = t2; yield t1 
 end

end </lang>

Testing

1/2 <lang ruby>r2cf(1,2) {|n| print "#{n} "}</lang>

Output:

0 2

3

<lang ruby>r2cf(3,1) {|n| print "#{n} "}</lang>

Output:

23/8 <lang ruby>r2cf(23,8) {|n| print "#{n} "}</lang>

Output:

2 1 7

13/11 <lang ruby>r2cf(13,11) {|n| print "#{n} "}</lang>

Output:

1 5 2

22/7 <lang ruby>r2cf(22,7) {|n| print "#{n} "}</lang>

Output:

3 7

1.4142 <lang ruby>r2cf(14142,10000) {|n| print "#{n} "}</lang>

Output:

1 2 2 2 2 2 1 1 29

1.4142 <lang ruby>r2cf(141421,100000) {|n| print "#{n} "}</lang>

Output:

1 2 2 2 2 2 2 3 1 1 3 1 7 2

1.414214 <lang ruby>r2cf(1414214,1000000) {|n| print "#{n} "}</lang>

Output:

1 2 2 2 2 2 2 2 3 6 1 2 1 12

1.4142136 <lang ruby>r2cf(14142136,10000000) {|n| print "#{n} "}</lang>

Output:

1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2

XPL0

<lang XPL0>include c:\cxpl\codes; real Val;

proc R2CF(N1, N2, Lev); \Output continued fraction for N1/N2 int N1, N2, Lev; int Quot, Rem; [if Lev=0 then Val:= 0.0; Quot:= N1/N2; Rem:= rem(0); IntOut(0, Quot); if Rem then [ChOut(0, if Lev then ^, else ^;); R2CF(N2, Rem, Lev+1)]; Val:= Val + float(Quot); \generate value from continued fraction if Lev then Val:= 1.0/Val; ];

int I, Data; [Data:= [1,2, 3,1, 23,8, 13,11, 22,7, 0]; Format(0, 15); I:= 0; while Data(I) do

  [IntOut(0, Data(I));  ChOut(0, ^/);  IntOut(0, Data(I+1));  ChOut(0, 9\tab\);
  ChOut(0, ^[);  R2CF(Data(I), Data(I+1), 0);  ChOut(0, ^]);  ChOut(0, 9\tab\);
  RlOut(0, Val);  CrLf(0);
  I:= I+2];

]</lang>

Output:

1/2     [0;2]    5.000000000000000E-001
3/1     [3]      3.000000000000000E+000
23/8    [2;1,7]  2.875000000000000E+000
13/11   [1;5,2]  1.181818181818180E+000
22/7    [3;7]    3.142857142857140E+000