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 ${\mathit {r2cf}}(\mathrm {int}$ $N_{1},\mathrm {int}$ $N_{2})$ , or ${\mathit {r2cf}}(\mathrm {Fraction}$ $N)$ , which will output a continued fraction assuming:

N_{1}

is the numerator

N_{2}

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_{1}$ divided by $N_{2}$ . It then sets $N_{1}$ to $N_{2}$ and $N_{2}$ to the determined remainder part. It then outputs the determined integer part. It does this until $\mathrm {abs} (N_{2})$ is zero.

Demonstrate the function by outputing the continued fraction for:

1/2

3

23/8

13/11

22/7

-151/77

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

14142,10000

141421,100000

1414214,1000000

14142136,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++

<lang cpp>#include <iostream> /* Interface for all Continued Fractions

  Nigel Galloway, February 9th., 2013.

/

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

  Nigel Galloway, February 9th., 2013.

/

class r2cf : public 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 fabs(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 -151/77

<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; for(r2cf cf(-151,77); cf.moreTerms(); std::cout << cf.nextTerm() << " "); std::cout << std::endl; return 0; }</lang>

Output:

0 2
3
2 1 7
1 5 2
3 7
-1 -1 -24 -1 -2

${\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

C#

<lang csharp>using System; using System.Collections.Generic;

class Program {

   static IEnumerable<int> r2cf(int n1, int n2)
   {
       while (Math.Abs(n2) > 0)
       {
           int t1 = n1 / n2;
           int t2 = n2;
           n2 = n1 - t1 * n2;
           n1 = t2;
           yield return t1;
       }
   }

   static void spit(IEnumerable<int> f)
   {
       foreach (int n in f) Console.Write(" {0}", n);
       Console.WriteLine();
   }

   static void Main(string[] args)
   {
       spit(r2cf(1, 2));
       spit(r2cf(3, 1));
       spit(r2cf(23, 8));
       spit(r2cf(13, 11));
       spit(r2cf(22, 7));
       spit(r2cf(-151, 77));
       for (int scale = 10; scale <= 10000000; scale *= 10)
       {
           spit(r2cf((int)(Math.Sqrt(2) * scale), scale));
       }
       spit(r2cf(31, 10));
       spit(r2cf(314, 100)); 
       spit(r2cf(3142, 1000));
       spit(r2cf(31428, 10000));
       spit(r2cf(314285, 100000));
       spit(r2cf(3142857, 1000000));
       spit(r2cf(31428571, 10000000));
       spit(r2cf(314285714, 100000000));
   }

} </lang> Output

 0 2
 3
 2 1 7
 1 5 2
 3 7
 -1 -1 -24 -1 -2
 1 2 2
 1 2 2 3 1 1 2
 1 2 2 2 2 5 3
 1 2 2 2 2 2 1 1 29
 1 2 2 2 2 2 2 3 1 1 3 1 7 2
 1 2 2 2 2 2 2 2 1 1 4 1 1 1 1 1 2 1 6
 1 2 2 2 2 2 2 2 2 2 1 594
 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

F#

<lang fsharp>let rec r2cf n d =

   if d = LanguagePrimitives.GenericZero then []
   else let q = n / d in q :: (r2cf d (n - q * d))

[<EntryPoint>] let main argv =

   printfn "%A" (r2cf 1 2)
   printfn "%A" (r2cf 3 1)
   printfn "%A" (r2cf 23 8)
   printfn "%A" (r2cf 13 11)
   printfn "%A" (r2cf 22 7)
   printfn "%A" (r2cf -151 77)
   printfn "%A" (r2cf 141 100)
   printfn "%A" (r2cf 1414 1000)
   printfn "%A" (r2cf 14142 10000)
   printfn "%A" (r2cf 141421 100000)
   printfn "%A" (r2cf 1414214 1000000)
   printfn "%A" (r2cf 14142136 10000000)
   0</lang>

Output

[0; 2]
[3]
[2; 1; 7]
[1; 5; 2]
[3; 7]
[-1; -1; -24; -1; -2]
[1; 2; 2; 3; 1; 1; 2]
[1; 2; 2; 2; 2; 5; 3]
[1; 2; 2; 2; 2; 2; 1; 1; 29]
[1; 2; 2; 2; 2; 2; 2; 3; 1; 1; 3; 1; 7; 2]
[1; 2; 2; 2; 2; 2; 2; 2; 3; 6; 1; 2; 1; 12]
[1; 2; 2; 2; 2; 2; 2; 2; 2; 2; 6; 1; 2; 4; 1; 1; 2]

Haskell

Translation of: Python

This more general version generates a continued fraction from any real number (with rationals as a special case): <lang haskell>import Data.Ratio ((%))

real2cf :: (RealFrac a, Integral b) => a -> [b] real2cf x =

 i : if f == 0 then [] else real2cf (1/f)
 where (i, f) = properFraction x

main :: IO () main = do

 print $ real2cf (13 % 11) -- => [1,5,2]
 print $ take 20 $ real2cf (sqrt 2) -- => [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]</lang>

J

Implemented as a class, r2cf preserves state in a separate locale. I've used some contrivances to jam the examples onto one line. <lang J> coclass'cf' create =: dyad def 'EMPTY [ N =: x , y' destroy =: codestroy r2cf =: monad define

if. 0 (= {:) N do. _ return. end.
RV =. <.@:(%/) N
N =: ({. , |/)@:|. N
RV

)

cocurrent'base' CF =: conew'cf'

Until =: conjunction def 'u^:(-.@:v)^:_'

(,. }.@:}:@:((,r2cf__CF)Until(_-:{:))@:(8[create__CF/)&.>)1 2;3 1;23 8;13 11;22 7;14142136 10000000;_151 77 Note 'Output' ┌─────────────────┬─────────────────────────────────┐ │1 2 │0 2 │ ├─────────────────┼─────────────────────────────────┤ │3 1 │3 │ ├─────────────────┼─────────────────────────────────┤ │23 8 │2 1 7 │ ├─────────────────┼─────────────────────────────────┤ │13 11 │1 5 2 │ ├─────────────────┼─────────────────────────────────┤ │22 7 │3 7 │ ├─────────────────┼─────────────────────────────────┤ │14142136 10000000│1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2│ ├─────────────────┼─────────────────────────────────┤ │_151 77 │_2 25 1 2 │ └─────────────────┴─────────────────────────────────┘ ) </lang>

version 2

 f =: 3 : 0

a =. {.y b =. {:y out=. <. a%b while. b > 1 do. 'a b' =. b; b|a out=. out , <. a%b end. )

  f each 1 2;3 1;23 8;13 11;22 7;14142136 10000000;_151 77

┌───┬─┬─────┬─────┬───┬───────────────────────────────────┬─────────┐ │0 2│3│2 1 7│1 5 2│3 7│1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2 _│_2 25 1 2│ └───┴─┴─────┴─────┴───┴───────────────────────────────────┴─────────┘ </lang>

Mathematica

Mathematica has a build-in function ContinuedFraction. <lang mathematica>ContinuedFraction[1/2] ContinuedFraction[3] ContinuedFraction[23/8] ContinuedFraction[13/11] ContinuedFraction[22/7] ContinuedFraction[-151/77] ContinuedFraction[14142/10000] ContinuedFraction[141421/100000] ContinuedFraction[1414214/1000000] ContinuedFraction[14142136/10000000]</lang>

Output:

{0, 2}
{3}
{2, 1, 7}
{1, 5, 2}
{3, 7}
{-1, -1, -24, -1, -2}
{1, 2, 2, 2, 2, 2, 1, 1, 29}
{1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2}
{1, 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12}
{1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2}

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>

Python

Translation of: Ruby

<lang python>def r2cf(n1,n2):

 while n2:
   n1, (t1, n2) = n2, divmod(n1, n2)
   yield t1

print(list(r2cf(1,2))) # => [0, 2] print(list(r2cf(3,1))) # => [3] print(list(r2cf(23,8))) # => [2, 1, 7] print(list(r2cf(13,11))) # => [1, 5, 2] print(list(r2cf(22,7))) # => [3, 7] print(list(r2cf(14142,10000))) # => [1, 2, 2, 2, 2, 2, 1, 1, 29] print(list(r2cf(141421,100000))) # => [1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2] print(list(r2cf(1414214,1000000))) # => [1, 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12] print(list(r2cf(14142136,10000000))) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2]</lang> This version generates it from any real number (with rationals as a special case): <lang python>def real2cf(x):

   while True:
       t1, f = divmod(x, 1)
       yield int(t1)
       if not f:
           break
       x = 1/f

from fractions import Fraction from itertools import islice

print(list(real2cf(Fraction(13, 11)))) # => [1, 5, 2] print(list(islice(real2cf(2 ** 0.5), 20))) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]</lang>

REXX

Programming notes:

Increase numeric digits to a higher value to generate more terms.
Two subroutines, sqrt & pi, were included here to demonstrate terms for √2 and π.
The subroutine $maxfact was included and is only needed if the number used for r2cf is a decimal fraction.
Checks were included to verify that the arguments being passed to r2cf are indeed numeric and also not zero.
This version also handles negative numbers.

<lang rexx>/*REXX pgm converts decimal or rational fraction to a continued fraction*/ numeric digits 230 /*this determines how many terms */

                                      /*can be generated for dec fracts*/

say ' 1/2 ──► CF: ' r2cf( '1/2' ) say ' 3 ──► CF: ' r2cf( 3 ) say ' 23/8 ──► CF: ' r2cf( '23/8' ) say ' 13/11 ──► CF: ' r2cf( '13/11' ) say ' 22/7 ──► CF: ' r2cf( '22/7 ' ) say say '───────── attempts at √2.' say '14142/1e4 ──► CF: ' r2cf( '14142/1e4 ' ) say '141421/1e5 ──► CF: ' r2cf( '141421/1e5 ' ) say '1414214/1e6 ──► CF: ' r2cf( '1414214/1e6 ' ) say '14142136/1e7 ──► CF: ' r2cf( '14142136/1e7 ' ) say '141421356/1e8 ──► CF: ' r2cf( '141421356/1e8 ' ) say '1414213562/1e9 ──► CF: ' r2cf( '1414213562/1e9 ' ) say '14142135624/1e10 ──► CF: ' r2cf( '14142135624/1e10 ' ) say '141421356237/1e11 ──► CF: ' r2cf( '141421356237/1e11 ' ) say '1414213562373/1e12 ──► CF: ' r2cf( '1414213562373/1e12 ' ) say '√2 ──► CF: ' r2cf( sqrt(2) ) say say '───────── an attempt at π' say 'π ──► CF: ' r2cf( pi() ) exit /*stick a fork in it, we're done.*/ /*────────────────────────────────R2CF subroutine───────────────────────*/ r2cf: procedure; parse arg g 1 s 2; $=; if s=='-' then g = substr(g,2)

                                                     else s =

if pos('.',g)\==0 then do

                      if \datatype(g,'N') then call serr 'not numeric:' g
                      g = $maxfact(g)
                      end

if pos('/',g)==0 then g = g"/"1 parse var g n '/' d if \datatype(n,'W') then call serr "a numerator isn't an integer:" n if \datatype(d,'W') then call serr "a denominator isn't an integer:" d n = abs(n) /*ensure numerator is positive. */ if d=0 then call serr 'a denominator is zero'

                do  while  d\==0      /*where the rubber meets the road*/
                $ = $    s || (n%d)   /*append another number to list. */
                _ = d
                d = n // d            /* %  is int div,  // is modulus.*/
                n = _
                end   /*while*/

return strip($) /*─────────────────────────────PI subroutine────────────────────────────*/ pi: return, /*a bit of overkill, but hey !! */ /* ··· should ≥ NUMERIC DIGITS */ 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271 /*─────────────────────────────SERR subroutine──────────────────────────*/ serr: say; say '***error!***'; say; say arg(1); say; exit /*─────────────────────────────SQRT subroutine──────────────────────────*/ sqrt: procedure; parse arg x; if x=0 then return 0; d=digits();numeric digits 11

     g=.sqrtGuess();       do j=0 while p>9;  m.j=p;  p=p%2+1;   end
     do k=j+5 to 0 by -1; if m.k>11 then numeric digits m.k; g=.5*(g+x/g); end
     numeric digits d;  return g/1

.sqrtGuess: if x<0 then call sqrtErr; numeric form; m.=11; p=d+d%4+2

     parse value format(x,2,1,,0) 'E0' with g 'E' _ .;   return g*.5'E'_%2

/*─────────────────────────────MAXFACT subroutine───────────────────────*/ $maxFact: procedure; parse arg x 1 _x,y; y=10**(digits()-1); b=0; h=1 a=1; g=0; do while a<=y & g<=y; n=trunc(_x); _=a; a=n*a+b; b=_; _=g g=n*g+h; h=_; if n=_x | a/g=x then do; if a>y | g>y then iterate; b=a h=g; leave; end; _x=1/(_x-n); end; return b'/'h</lang>

Output:

              1/2  ──► CF:  0 2
               3   ──► CF:  3
             23/8  ──► CF:  2 1 7
             13/11 ──► CF:  1 5 2
             22/7  ──► CF:  3 7

───────── attempts at √2.
14142/1e4          ──► CF:  1 2 2 2 2 2 1 1 29
141421/1e5         ──► CF:  1 2 2 2 2 2 2 3 1 1 3 1 7 2
1414214/1e6        ──► CF:  1 2 2 2 2 2 2 2 3 6 1 2 1 12
14142136/1e7       ──► CF:  1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2
141421356/1e8      ──► CF:  1 2 2 2 2 2 2 2 2 2 2 3 4 1 1 2 6 8
1414213562/1e9     ──► CF:  1 2 2 2 2 2 2 2 2 2 2 2 1 1 14 1 238 1 3
14142135624/1e10   ──► CF:  1 2 2 2 2 2 2 2 2 2 2 2 2 2 5 4 1 8 4 2 1 4
141421356237/1e11  ──► CF:  1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 1 4 1 2 1 63 2 1 1 1 4 2
1414213562373/1e12 ──► CF:  1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 1 11 2 3 2 1 1 1 25 1 2 3
√2                 ──► CF:  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 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3

───────── an attempt at π
π                  ──► CF:  3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1 2 2 2 2 1 84 2 1 1 15 3 13 1 4 2 6 6 99 1 2 2 6 3 5 1 1 6 8 1 7 1 2 3 7 1 2 1 1 12 1 1 1 3 1 1 8 1 1 2 1 6 1 1 5 2 2 3 1 2 4 4 16 1 161 45 1 22 1 2 2 1 4 1 2 24 1 2 1 3 1 2 1 1 10 2 5 4 1 2 2 8 1 5 2 2 26 1 4 1 1 8 2 42 2 1 7 3 3 1 1 7 2 4 9 7 2 3 1 57 1 18 1 9 19 1 2 18 1 3 7 30 1 1 1 3 3 3 1 2 8 1 1 2 1 15 1 2 13 1 2 1 4 1 12 1 1 3 3 28 1 10 3 2 20 1 1 1 1 4 1 1 1 5 3 2 1 6 1 4 1 120 2 1 1 3 1 23 1 15 1 3 7 1 16 1 2 1 21 2 1 1 2 9 1 6 4

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

Tcl

Works with: Tcl version 8.6

Translation of: Ruby

Direct translation

<lang tcl>package require Tcl 8.6

proc r2cf {n1 {n2 1}} {

   # Convert a decimal fraction (e.g., 1.23) into a form we can handle
   if {$n1 != int($n1) && [regexp {\.(\d+)} $n1 -> suffix]} {

set pow [string length $suffix] set n1 [expr {int($n1 * 10**$pow)}] set n2 [expr {$n2 * 10**$pow}]

   }
   # Construct the continued fraction as a coroutine that yields the digits in sequence
   coroutine cf\#[incr ::cfcounter] apply {{n1 n2} {

yield [info coroutine] while {$n2 > 0} { yield [expr {$n1 / $n2}] set n2 [expr {$n1 % [set n1 $n2]}] } return -code break

   }} $n1 $n2

}</lang> Demonstrating: <lang tcl>proc printcf {name cf} {

   puts -nonewline "$name -> "
   while 1 {

puts -nonewline "[$cf],"

   }
   puts "\b "

}

foreach {n1 n2} {

   1 2
   3 1
   23 8
   13 11
   22 7
   -151 77
   14142 10000
   141421 100000
   1414214 1000000
   14142136 10000000
   31 10
   314 100
   3142 1000
   31428 10000
   314285 100000
   3142857 1000000
   31428571 10000000
   314285714 100000000
   3141592653589793 1000000000000000

} {

   printcf "\[$n1;$n2\]" [r2cf $n1 $n2]

}</lang>

Output:

[1;2] -> 0,2 
[3;1] -> 3 
[23;8] -> 2,1,7 
[13;11] -> 1,5,2 
[22;7] -> 3,7 
[-151;77] -> -2,25,1,2 
[14142;10000] -> 1,2,2,2,2,2,1,1,29 
[141421;100000] -> 1,2,2,2,2,2,2,3,1,1,3,1,7,2 
[1414214;1000000] -> 1,2,2,2,2,2,2,2,3,6,1,2,1,12 
[14142136;10000000] -> 1,2,2,2,2,2,2,2,2,2,6,1,2,4,1,1,2 
[31;10] -> 3,10 
[314;100] -> 3,7,7 
[3142;1000] -> 3,7,23,1,2 
[31428;10000] -> 3,7,357 
[314285;100000] -> 3,7,2857 
[3142857;1000000] -> 3,7,142857 
[31428571;10000000] -> 3,7,476190,3 
[314285714;100000000] -> 3,7,7142857 
[3141592653589793;1000000000000000] -> 3,7,15,1,292,1,1,1,2,1,3,1,14,4,2,3,1,12,5,1,5,20,1,11,1,1,1,2

Objectified version

<lang tcl>package require Tcl 8.6

General generator class based on coroutines

oo::class create Generator {

   constructor {} {

coroutine [namespace current]::coro my Apply

   }
   destructor {

catch {rename [namespace current]::coro {}}

   }
   method Apply {} {

yield

       # Call the method (defined in subclasses) that actually produces values

my Produce my destroy return -code break

   }
   forward generate coro
   method unknown args {

if {![llength $args]} { tailcall coro } next {*}$args

   # Various ways to get the sequence from the generator
   method collect {} {

set result {} while 1 { lappend result [my generate] } return $result

   }
   method take {n {suffix ""}} {

set result {} for {set i 0} {$i < $n} {incr i} { lappend result [my generate] } while {$suffix ne ""} { my generate lappend result $suffix break } return $result

}

oo::class create R2CF {

   superclass Generator
   variable a b
   # The constructor converts other kinds of fraction (e.g., 1.23, 22/7) into a
   # form we can handle.
   constructor {n1 {n2 1}} {

next; # Delegate to superclass for coroutine management if {[regexp {(.*)/(.*)} $n1 -> a b]} { # Nothing more to do; assume we can ignore second argument here } elseif {$n1 != int($n1) && [regexp {\.(\d+)} $n1 -> suffix]} { set pow [string length $suffix] set a [expr {int($n1 * 10**$pow)}] set b [expr {$n2 * 10**$pow}] } else { set a $n1 set b $n2 }

   }
   # How to actually produce the values of the sequence
   method Produce {} {

while {$b > 0} { yield [expr {$a / $b}] set b [expr {$a % [set a $b]}] }

}

proc printcf {name cf {take ""}} {

   if {$take ne ""} {

set terms [$cf take $take \u2026]

   } else {

set terms [$cf collect]

   }
   puts [format "%-15s-> %s" $name [join $terms ,]]

}

foreach {n1 n2} {

   1 2
   3 1
   23 8
   13 11
   22 7
   -151 77
   14142 10000
   141421 100000
   1414214 1000000
   14142136 10000000
   31 10
   314 100
   3142 1000
   31428 10000
   314285 100000
   3142857 1000000
   31428571 10000000
   314285714 100000000
   3141592653589793 1000000000000000

} {

   printcf "\[$n1;$n2\]" [R2CF new $n1 $n2]

}

Demonstrate parsing of input in forms other than a direct pair of decimals

printcf "1.5" [R2CF new 1.5] printcf "23/7" [R2CF new 23/7]</lang>

Output:

[1;2]          -> 0,2
[3;1]          -> 3
[23;8]         -> 2,1,7
[13;11]        -> 1,5,2
[22;7]         -> 3,7
[-151;77]      -> -2,25,1,2
[14142;10000]  -> 1,2,2,2,2,2,1,1,29
[141421;100000]-> 1,2,2,2,2,2,2,3,1,1,3,1,7,2
[1414214;1000000]-> 1,2,2,2,2,2,2,2,3,6,1,2,1,12
[14142136;10000000]-> 1,2,2,2,2,2,2,2,2,2,6,1,2,4,1,1,2
[31;10]        -> 3,10
[314;100]      -> 3,7,7
[3142;1000]    -> 3,7,23,1,2
[31428;10000]  -> 3,7,357
[314285;100000]-> 3,7,2857
[3142857;1000000]-> 3,7,142857
[31428571;10000000]-> 3,7,476190,3
[314285714;100000000]-> 3,7,7142857
[3141592653589793;1000000000000000]-> 3,7,15,1,292,1,1,1,2,1,3,1,14,4,2,3,1,12,5,1,5,20,1,11,1,1,1,2
1.5            -> 1,2
23/7           -> 3,3,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

Testing

1/2 3 23/8 13/11 22/7 -151/77

2 {\displaystyle {\sqrt {2}}}

Real approximations of a rational number

version 2

Testing

Direct translation

Objectified version

${\sqrt {2}}$