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

C does not implement Lazy evaluation and it is this particular feature which is the real challenge of this particular example. It can however be simulated. The following example uses pointers. It seems that the same data is being passed but since the function accepts pointers, the variables are being changed. One other way to simulate laziness would be to use global variables. Then although it would seem that the same values are being passed even as constants, the job is actually getting done. In my view, that would be plain cheating.

<lang C> /*Abhishek Ghosh, 8th November 2013, Rotterdam*/

include<stdio.h>

typedef struct{ int num,den; }fraction;

fraction examples[] = {{1,2}, {3,1}, {23,8}, {13,11}, {22,7}, {-151,77}}; fraction sqrt2[] = {{14142,10000}, {141421,100000}, {1414214,1000000}, {14142136,10000000}}; fraction pi[] = {{31,10}, {314,100}, {3142,1000}, {31428,10000}, {314285,100000}, {3142857,1000000}, {31428571,10000000}, {314285714,100000000}};

int r2cf(int *numerator,int *denominator) { int quotient=0,temp;

if(denominator != 0) { quotient = *numerator / *denominator;

temp = *numerator;

*numerator = *denominator;

*denominator = temp % *denominator; }

return quotient; }

int main() { int i;

printf("Running the examples :");

for(i=0;i<sizeof(examples)/sizeof(fraction);i++) { printf("\nFor N = %d, D = %d :",examples[i].num,examples[i].den);

while(examples[i].den != 0){ printf(" %d ",r2cf(&examples[i].num,&examples[i].den)); } }

printf("\n\nRunning for %c2 :",251); /* 251 is the ASCII code for the square root symbol */

for(i=0;i<sizeof(sqrt2)/sizeof(fraction);i++) { printf("\nFor N = %d, D = %d :",sqrt2[i].num,sqrt2[i].den);

while(sqrt2[i].den != 0){ printf(" %d ",r2cf(&sqrt2[i].num,&sqrt2[i].den)); } }

printf("\n\nRunning for %c :",227); /* 227 is the ASCII code for Pi's symbol */

for(i=0;i<sizeof(pi)/sizeof(fraction);i++) { printf("\nFor N = %d, D = %d :",pi[i].num,pi[i].den);

while(pi[i].den != 0){ printf(" %d ",r2cf(&pi[i].num,&pi[i].den)); } }

return 0; }

</lang> And the run gives :

Running the examples :
For N = 1, D = 2 : 0  2
For N = 3, D = 1 : 3
For N = 23, D = 8 : 2  1  7
For N = 13, D = 11 : 1  5  2
For N = 22, D = 7 : 3  7
For N = -151, D = 77 : -1  -1  -24  -1  -2

Running for √2 :
For N = 14142, D = 10000 : 1  2  2  2  2  2  1  1  29
For N = 141421, D = 100000 : 1  2  2  2  2  2  2  3  1  1  3  1  7  2
For N = 1414214, D = 1000000 : 1  2  2  2  2  2  2  2  3  6  1  2  1  12
For N = 14142136, D = 10000000 : 1  2  2  2  2  2  2  2  2  2  6  1  2  4  1  1  2

Running for π :
For N = 31, D = 10 : 3  10
For N = 314, D = 100 : 3  7  7
For N = 3142, D = 1000 : 3  7  23  1  2
For N = 31428, D = 10000 : 3  7  357
For N = 314285, D = 100000 : 3  7  2857
For N = 3142857, D = 1000000 : 3  7  142857
For N = 31428571, D = 10000000 : 3  7  476190  3
For N = 314285714, D = 100000000 : 3  7  7142857

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

Common Lisp

<lang lisp>(defun r2cf (n1 n2)

 (lambda ()
   (unless (zerop n2)
     (multiple-value-bind (t1 r)
         (floor n1 n2)
       (setf n1 n2 n2 r)
       t1))))

Example usage

(defun demo-generator (numbers)

 (let* ((n1 (car numbers))
        (n2 (cadr numbers))
        (gen (r2cf n1 n2)))
   (format t "~S  ; ~S~%"
           `(r2cf ,n1 ,n2)
           (loop
             :for r = (funcall gen)
             :until (null r)
             :collect r))))

(mapcar #'demo-generator

       '((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)))</lang>

Output:

(R2CF 3 1)  ; (3)
(R2CF 23 8)  ; (2 1 7)
(R2CF 13 11)  ; (1 5 2)
(R2CF 22 7)  ; (3 7)
(R2CF -151 77)  ; (-2 25 1 2)
(R2CF 14142 10000)  ; (1 2 2 2 2 2 1 1 29)
(R2CF 141421 100000)  ; (1 2 2 2 2 2 2 3 1 1 3 1 7 2)
(R2CF 1414214 1000000)  ; (1 2 2 2 2 2 2 2 3 6 1 2 1 12)
(R2CF 14142136 10000000)  ; (1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2)
(R2CF 31 10)  ; (3 10)
(R2CF 314 100)  ; (3 7 7)
(R2CF 3142 1000)  ; (3 7 23 1 2)
(R2CF 31428 10000)  ; (3 7 357)
(R2CF 314285 100000)  ; (3 7 2857)
(R2CF 3142857 1000000)  ; (3 7 142857)
(R2CF 31428571 10000000)  ; (3 7 476190 3)
(R2CF 314285714 100000000)  ; (3 7 7142857)
(R2CF 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)

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

Tacit version

This version is a modification of an explicit version shown in http://www.jsoftware.com/jwiki/Essays/Continued%20Fractions to comply with the task specifications. <lang j>cf=: _1 1 ,@}. (, <.)@%@-/ ::]^:a:@(, <.)@(%&x:/)</lang>

Examples

<lang j> cf 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│ └───┴─┴─────┴─────┴───┴─────────────────────────────────┴─────────┘

  cf each 14142 10000;141421 100000;1414214 1000000;14142136 10000000

┌──────────────────┬───────────────────────────┬────────────────────────────┬─────────────────────────────────┐ │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│ └──────────────────┴───────────────────────────┴────────────────────────────┴─────────────────────────────────┘

  cf each 31 10;314 100;3142 1000;31428 10000;314285 100000;3142857 1000000;31428571 10000000;314285714 100000000

┌────┬─────┬──────────┬───────┬────────┬──────────┬────────────┬───────────┐ │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│ └────┴─────┴──────────┴───────┴────────┴──────────┴────────────┴───────────┘</lang> This tacit version first produces the answer with a trailing ∞ (represented by _ in J) which is then removed by the last operation (}:). A continued fraction can be evaluated using the verb ((+%)/) and both representations produce equal results, <lang j> 3 7 =&((+ %)/) 3 7 _ 1</lang> Incidentally, J and Tcl report a different representation for -151/77 versus the representation of other implementations; however, both representations produce equal results. <lang j> _2 25 1 2 =&((+ %)/) _1 _1 _24 _1 _2 1</lang>

Explicit versions

version 1

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}

PARI/GP

<lang parigp>apply(contfrac,[1/2,3,23/8,13/11,22/7,-151/77])</lang>

Output:

[[0, 2], [3], [2, 1, 7], [1, 5, 2], [3, 7], [-2, 25, 1, 2]]

Perl

To do output one digit at a time, we first turn off buffering to be pedantic, then use a closure that yields one term per call. <lang perl>$|=1;

sub rc2f {

 my($num, $den) = @_;
 return sub { return unless $den;
              my $q = int($num/$den);
              ($num, $den) = ($den, $num - $q*$den);
              $q; };

}

sub rcshow {

 my $sub = shift;
 print "[";
 my $n = $sub->();
 print "$n" if defined $n;
 print "; $n" while defined($n = $sub->());
 print "]\n";

}

rcshow(rc2f(@$_))

  for ([1,2],[3,1],[23,8],[13,11],[22,7],[-151,77]);

print "\n"; rcshow(rc2f(@$_))

  for ([14142,10000],[141421,100000],[1414214,1000000],[14142136,10000000]);

print "\n"; rcshow(rc2f(314285714,100000000));</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]

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

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>

Racket

lang racket

(define ((r2cf n d))

 (or (zero? d)
     (let-values ([(q r) (quotient/remainder n d)])
       (set! n d)
       (set! d r)
       q)))

(define (r->cf n d)

 (for/list ([i (in-producer (r2cf n d) #t)]) i))

(define (real->cf x places)

 (define d (expt 10 places))
 (define n (exact-floor (* x d)))
 (r->cf n d))

(map r->cf

    '(1 3 23 13 22 -151)
    '(2 1  8 11  7   77))

(real->cf (sqrt 2) 10) (real->cf pi 10) </lang>

Output:

'((0 2) (3) (2 1 7) (1 5 2) (3 7) (-1 -1 -24 -1 -2))
'(1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 1 3 8 9 1 20 1 2)
'(3 7 15 1 292 1 1 6 2 13 3 1 12 3)

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># Generate a continued fraction from a rational number

def r2cf(n1,n2)

 while n2 > 0
   n1, (t1, n2) = n2, n1.divmod(n2)
   yield t1
 end

end</lang>

Testing

Test 1: <lang ruby>[[1,2], [3,1], [23,8], [13,11], [22,7], [-151,77]].each do |n1,n2|

 print "%10s : " % "#{n1} / #{n2}"
 r2cf(n1,n2) {|n| print "#{n} "}
 puts

end</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

Test 2: ${\sqrt {2}}$ <lang ruby>(5..8).each do |digit|

 n2 = 10 ** (digit-1)
 n1 = (Math.sqrt(2) * n2).round
 print "%-8s / %-8s : " % [n1, n2]
 r2cf(n1,n2) {|n| print "#{n} "}
 puts

end</lang>

Output:

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

Test 3: <lang ruby>a =[ [31,10],

    [314,100],
    [3142,1000],
    [31428,10000],
    [314285,100000],
    [3142857,1000000],
    [31428571,10000000],
    [314285714,100000000]
  ]

a.each do |n1,n2|

 print "%-9s / %-9s : " % [n1, n2]
 r2cf(n1,n2) {|n| print "#{n} "}
 puts

end</lang>

Output:

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

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

Tacit version

Examples

Explicit versions

version 1

version 2

Testing

Direct translation

Objectified version

${\sqrt {2}}$