Jump to content

Continued fraction/Arithmetic/Construct from rational number

From Rosetta Code
Task
Continued fraction/Arithmetic/Construct from rational number
You are encouraged to solve this task according to the task description, using any language you may know.

To understand this task in context please see Continued fraction arithmetic

The purpose of this task is to write a function , or , which will output a continued fraction assuming:

is the numerator
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 divided by . It then sets to and to the determined remainder part. It then outputs the determined integer part. It does this until is zero.

Demonstrate the function by outputing the continued fraction for:

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

should approach 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 and convince yourself that, in the same way as may be represented as when an extra decimal place is required, may be represented as when an extra term is required.

11l

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

print(r2cf(1, 2))
print(r2cf(3, 1))
print(r2cf(23, 8))
print(r2cf(13, 11))
print(r2cf(22, 7))
print(r2cf(14142, 10000))
print(r2cf(141421, 100000))
print(r2cf(1414214, 1000000))
print(r2cf(14142136, 10000000))
Output:
[0, 2]
[3]
[2, 1, 7]
[1, 5, 2]
[3, 7]
[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]

Ada

Translation of: Fortran
with ada.text_io; use ada.text_io;
with ada.strings; use ada.strings;
with ada.strings.fixed; use ada.strings.fixed;

procedure continued_fraction_from_rational is

  -- The following implementation of r2cf both modifies its arguments
  -- and returns a value.
  function r2cf (N1 : in out integer;
                 N2 : in out integer)
    return integer
  is
    q, r : integer;
  begin
    -- We will use floor division, where the quotient is rounded
    -- towards negative infinity. Whenever the divisor is positive,
    -- this type of division gives a non-negative remainder.
    r := N1 mod N2;
    q := (N1 - r) / N2;

    N1 := N2;
    N2 := r;

    return q;
  end r2cf;

  procedure write_r2cf (N1 : in integer;
                        N2 : in integer)
  is
    M1, M2 : integer;
    digit : integer;
    sep : integer;
  begin
    put (trim (integer'image (N1), left));
    put ("/");
    put (trim (integer'image (N2), left));
    put (" => ");

    M1 := N1;
    M2 := N2;
    sep := 0;
    while M2 /= 0 loop
      digit := r2cf (M1, M2);
      if sep = 0 then
        put ("[");
        sep := 1;
      elsif sep = 1 then
        put ("; ");
        sep := 2;
      else
        put (", ");
      end if;
      put (trim (integer'image (digit), left));
    end loop;
    put_line ("]");
  end write_r2cf;

begin

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

  write_r2cf (14142, 10000);
  write_r2cf (141421, 100000);
  write_r2cf (1414214, 1000000);
  write_r2cf (14142136, 10000000);

  write_r2cf (31, 10);
  write_r2cf (314, 100);
  write_r2cf (3142, 1000);
  write_r2cf (31428, 10000);
  write_r2cf (314285, 100000);
  write_r2cf (3142857, 1000000);
  write_r2cf (31428571, 10000000);
  write_r2cf (314285714, 100000000);

end continued_fraction_from_rational;
Output:
$ gnatmake -q continued_fraction_from_rational.adb && ./continued_fraction_from_rational
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]

ALGOL 68

Translation of: C

...with code from the Arithmetic/Rational task.
The continued fraction expansion of -151/77 is sensitive to whether the language modulo operator follows the mathematical definition or the C definition.
Algol 68's MOD operator uses the mathematical definition (rounds towards -infinity), so the results for -157//77 agree with the EDSAC, J and a few other sdamples. Most other samples calculate the remainder using the C definotion.

BEGIN # construct continued fraction representations of rational numbers #
      # Translated from the C sample                                     #
      # Uses code from the Arithmetic/Rational task                      #

    # Code from the Arithmetic/Rational task                         #
    # ============================================================== #

    MODE FRAC = STRUCT( INT num #erator#,  den #ominator#);

    PROC gcd = (INT a, b) INT: # greatest common divisor #
       (a = 0 | b |: b = 0 | a |: ABS a > ABS b  | gcd(b, a MOD b) | gcd(a, b MOD a));
 
    PRIO // = 9; # higher then the ** operator #
    OP // = (INT num, den)FRAC: ( # initialise and normalise #
       INT common = gcd(num, den);
       IF den < 0 THEN
         ( -num OVER common, -den OVER common)
       ELSE
         ( num OVER common, den OVER common)
       FI
     );

    # ============================================================== #
    # end code from the Arithmetic/Rational task                     #

    []FRAC examples = ( 1//2, 3//1, 23//8, 13//11, 22//7, -151//77 ); 
    []FRAC sqrt2    = ( 14142//10000, 141421//100000, 1414214//1000000, 14142136//10000000 );
    []FRAC pif      = ( 31//10, 314//100, 3142//1000, 31428//10000
                      , 314285//100000, 3142857//1000000, 31428571//10000000, 314285714//100000000
                      );
 
    # returns the quotient of numerator over denominator and sets #
    #         numerator and denominator to the next values for    #
    #         the continued fraction                              #
    PROC r2cf = ( REF INT numerator, REF INT denominator )INT:
         IF denominator = 0
         THEN 0
         ELSE INT quotient      := numerator OVER denominator;
              INT prev numerator = numerator;
              numerator         := denominator;
              denominator       := prev numerator MOD denominator;
	      quotient
         FI # r2cf # ;
    # shows the continued fractions for the elements of f seq #
    PROC show r2cf = ( STRING legend, []FRAC f seq )VOID:
         BEGIN
            print( ( legend ) );
            FOR i FROM LWB f seq TO UPB f seq DO
                INT num := num OF f seq[ i ];
                INT den := den OF f seq[ i ];
                print( ( newline, "For N = ", whole( num , 0 ), ", D = ", whole( den , 0 ), " :" ) );
                WHILE den /= 0 DO
                    print( ( " ", whole( r2cf( num, den ), 0 ) ) )
                OD
            OD
         END # show r2cf # ;
    BEGIN # task #
        show r2cf( "Running the examples :", examples );
	print( ( newline, newline ) );
        show r2cf( "Running for root2 :", sqrt2 );
	print( ( newline, newline ) );
	show r2cf( "Running for pi :", pif );
        print( ( newline ) )
    END
END
Output:
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 25 1 2

Running for root2 :
For N = 7071, D = 5000 : 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 = 707107, D = 500000 : 1 2 2 2 2 2 2 2 3 6 1 2 1 12
For N = 1767767, D = 1250000 : 1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2

Running for pi :
For N = 31, D = 10 : 3 10
For N = 157, D = 50 : 3 7 7
For N = 1571, D = 500 : 3 7 23 1 2
For N = 7857, D = 2500 : 3 7 357
For N = 62857, D = 20000 : 3 7 2857
For N = 3142857, D = 1000000 : 3 7 142857
For N = 31428571, D = 10000000 : 3 7 476190 3
For N = 157142857, D = 50000000 : 3 7 7142857

ATS

Using a non-linear closure

In the first example solution, I demonstrate concretely that the method of integer division matters. I use 'Euclidean division' (see ACM Transactions on Programming Languages and Systems, Volume 14, Issue 2, pp 127–144. https://doi.org/10.1145/128861.128862) and show that you get a different continued fraction if you start with (-151)/77 than if you start with 151/(-77). I verified that both continued fractions do equal -(151/77).

A closure is used to generate the next term (or None()) each time it is called. The integer type is mostly arbitrary.

(*------------------------------------------------------------------*)

#include "share/atspre_staload.hats"

(*------------------------------------------------------------------*)
(* First, let us implement a proper method of division of signed
   integers, in which the remainder is always non-negative. (I
   implement such division in my ats2-xprelude package at
   https://sourceforge.net/p/chemoelectric/ats2-xprelude and have
   copied the implementation from there.) *)

extern fn {tk : tkind}
g0int_eucliddivrem :
  (g0int tk, g0int tk) -<> @(g0int tk, g0int tk)

implement {tk}
g0int_eucliddivrem (n, d) =
  let
    (* The C optimizer most likely will reduce these these two
       divisions to just one. They are simply synonyms for C '/' and
       '%', and perform division that rounds the quotient towards
       zero. *)
    val q0 = g0int_div (n, d)
    val r0 = g0int_mod (n, d)
  in
    (* The following calculation results in 'floor division', if the
       divisor is positive, or 'ceiling division', if the divisor is
       negative. This choice of method results in the remainder never
       being negative. *)
    if isgtez n then
      @(q0, r0)
    else if iseqz r0 then
      @(q0, r0)
    else if isltz d then
      @(succ q0, r0 - d)
    else
      @(pred q0, r0 + d)
  end

(*------------------------------------------------------------------*)
(* I implement the lazy evaluation by having r2cf explicitly create
   a thunk that returns the digits. *)

fn {tk : tkind}
step (N1 : ref (g0int tk),
      N2 : ref (g0int tk))
    : g0int tk =
  let
    val @(q, r) = g0int_eucliddivrem (!N1, !N2)
  in
    !N1 := !N2;
    !N2 := r;
    q
  end

fn {tk : tkind}
r2cf (N1 : g0int tk,
      N2 : g0int tk)
    : () -<cloref1> Option (g0int tk) =
  let
    val N1 = ref<g0int tk> N1
    and N2 = ref<g0int tk> N2
  in
    lam () =>
      if iseqz !N2 then
        None ()
      else
        Some (step (N1, N2))
  end

(*------------------------------------------------------------------*)

fn {tk : tkind}
print_digits (f : () -<cloref1> Option (g0int tk))
    : void =
  let
    fun
    loop (sep : string)
        : void =
      case+ f () of
      | None () => println! ("]")
      | Some d =>
        begin
          print! sep;
          fprint_val<g0int tk> (stdout_ref, d);
          if sep = "[" then
            loop "; "
          else
            loop ", "
        end
  in
    loop "["
  end

fn {tk : tkind}
print_continued_fraction
          (ratnum : @(g0int tk, g0int tk))
    : void =
  let
    val @(N1, N2) = ratnum
  in
    fprint_val<g0int tk> (stdout_ref, N1);
    print! "/";
    fprint_val<g0int tk> (stdout_ref, N2);
    print! " => ";
    print_digits (r2cf<tk> (N1, N2))
  end

(*------------------------------------------------------------------*)

val test_cases =
  $list (@(1LL, 2LL),
         @(3LL, 1LL),
         @(23LL, 8LL),
         @(13LL, 11LL),
         @(22LL, 7LL),
         @(~151LL, 77LL),       (* The numerator is negative. *)
         @(151LL, ~77LL),       (* The denominator is negative. *)
         @(14142LL, 10000LL),
         @(141421LL, 100000LL),
         @(1414214LL, 1000000LL),
         @(14142136LL, 10000000LL),
         @(1414213562373095049LL, 1000000000000000000LL),
         @(31LL, 10LL),
         @(314LL, 100LL),
         @(3142LL, 1000LL),
         @(31428LL, 10000LL),
         @(314285LL, 100000LL),
         @(3142857LL, 1000000LL),
         @(31428571LL, 10000000LL),
         @(314285714LL, 100000000LL),
         @(3142857142857143LL, 1000000000000000LL),
         @(2200000000000000000LL, 700000000000000000LL),
         @(2200000000000000001LL, 700000000000000000LL),
         @(2200000000000000000LL, 700000000000000001LL))

implement
main0 () =
  let
    var p : List0 @(llint, llint)
  in
    println! ();
    print! ("The continued fractions shown here are calculated by ");
    println! ("'Euclidean division',");
    println! ("where the remainder is always non-negative:");
    println! ();
    for (p := test_cases; ~list_is_nil p; p := list_tail p)
      print_continued_fraction<llintknd> (list_head p);
    println! ();
    println! ("Note that [3; 6, 1] is equal to [3; 7].");
    println! ()
  end

(*------------------------------------------------------------------*)
Output:
$ patscc -DATS_MEMALLOC_GCBDW -O2 -std=gnu2x continued-fraction-from-rational.dats -lgc && ./a.out

The continued fractions shown here are calculated by 'Euclidean division',
where the remainder is always non-negative:

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]
151/-77 => [-1; -2, 1, 23, 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]
1414213562373095049/1000000000000000000 => [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, 1, 39, 1, 5, 1, 3, 61, 1, 1, 8, 1, 2, 1, 7, 1, 1, 6]
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]
3142857142857143/1000000000000000 => [3; 6, 1, 142857142857142]
2200000000000000000/700000000000000000 => [3; 7]
2200000000000000001/700000000000000000 => [3; 6, 1, 14285714285714284, 1, 6]
2200000000000000000/700000000000000001 => [3; 7, 4545454545454545, 3, 7]

Note that [3; 6, 1] is equal to [3; 7].

Using a non-linear closure and multiple precision numbers

Library: ats2-xprelude
Library: GMP
Library: GNU MPFR

For this you need the ats2-xprelude package. I start with octuple precision (IEEE binary256) approximations to the square root of 2 and 22/7.

(*------------------------------------------------------------------*)
(* A version that uses the ats2-xprelude package
   https://sourceforge.net/p/chemoelectric/ats2-xprelude

   With ats2-xprelude installed, you can run the program with
   something like:   

     patscc -DATS_MEMALLOC_GCBDW `pkg-config --variable=PATSCCFLAGS ats2-xprelude` \
      `pkg-config --cflags ats2-xprelude` -O2 -std=gnu2x \
      continued-fraction-from-rational-2.dats \
      `pkg-config --libs ats2-xprelude` -lgc -lm && ./a.out

   *)

#include "share/atspre_staload.hats"
#include "xprelude/HATS/xprelude.hats"

staload "xprelude/SATS/exrat.sats"
staload _ = "xprelude/DATS/exrat.dats"

staload "xprelude/SATS/mpfr.sats"
staload _ = "xprelude/DATS/mpfr.dats"

(*------------------------------------------------------------------*)

fn
step (ratnum : ref exrat,
      done   : ref bool)
    : exrat =
  let
    (* Effectively we are doing the same thing as if we used integer
       floor division and the denominator were kept positive. *)
    val q = floor !ratnum
    val diff = !ratnum - q
  in
    if iseqz diff then
      begin
        !done := true;
        q
      end
    else
      begin
        !ratnum := reciprocal diff;
        q
      end
  end

fn
r2cf (ratnum : exrat)
    : () -<cloref1> Option exrat =
  let
    val ratnum = ref<exrat> ratnum
    and done = ref<bool> false
  in
    lam () =>
      if !done then
        None ()
      else
        Some (step (ratnum, done))
  end

(*------------------------------------------------------------------*)

fn
print_digits (f : () -<cloref1> Option exrat)
    : void =
  let
    fun
    loop (sep : string)
        : void =
      case+ f () of
      | None () => println! ("]")
      | Some d =>
        begin
          print! (sep, d);
          if sep = "[" then
            loop "; "
          else
            loop ", "
        end
  in
    loop "["
  end

fn {tk : tkind}
print_continued_fraction
          (ratnum : exrat)
    : void =
  begin
    print! (ratnum, " => ");
    print_digits (r2cf ratnum)
  end

(*------------------------------------------------------------------*)

(* The number of bits in the significand of an IEEE binary256
   floating point number. *)
#define OCTUPLE_PREC 237

implement
main0 () =
  begin
    print_continued_fraction (exrat_make (1, 2));
    print_continued_fraction (exrat_make (3, 1));
    print_continued_fraction (exrat_make (23, 8));
    print_continued_fraction (exrat_make (13, 11));
    print_continued_fraction (exrat_make (22, 7));
    print_continued_fraction (exrat_make (~151, 77));
    let
      val sqrt2 : mpfr = mpfr_SQRT2 OCTUPLE_PREC
      val sqrt2 : exrat = g0f2f sqrt2
    in
      println! ("Octuple precision sqrt2:");
      print_continued_fraction sqrt2
    end;
    let
      val val_22_7 : mpfr =
        mpfr_make ("22", OCTUPLE_PREC) / mpfr_make ("7", OCTUPLE_PREC)
      val val_22_7 : exrat = g0f2f val_22_7
    in
      println! ("Octuple precision 22/7:");
      print_continued_fraction val_22_7
    end;
  end

(*------------------------------------------------------------------*)
Output:
$ patscc -DATS_MEMALLOC_GCBDW `pkg-config --variable=PATSCCFLAGS ats2-xprelude` `pkg-config --cflags ats2-xprelude` -O2 -std=gnu2x continued-fraction-from-rational-2.dats `pkg-config --libs ats2-xprelude` -lgc -lm && ./a.out
1/2 => [0; 2]
3 => [3]
23/8 => [2; 1, 7]
13/11 => [1; 5, 2]
22/7 => [3; 7]
-151/77 => [-2; 25, 1, 2]
Octuple precision sqrt2:
78084346301521422975112153571109417254931862326853978216001371002918963/55213970774324510299478046898216203619608871777363092441300193790394368 => [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, 3, 4, 6, 1, 38, 2, 1, 9, 3, 16, 2, 1, 10, 2, 2, 1, 1, 18, 1, 2, 1, 3, 4, 1, 1, 2, 6, 6, 4, 3, 2, 1, 2, 4, 2, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 4, 1, 7, 10, 2, 1, 4, 3, 40, 1, 1, 5, 1, 2, 2, 1, 1, 7, 7, 6, 7, 1, 1, 2, 2]
Octuple precision 22/7:
86764811216795659042036930840054034259385369935856288122043161670619721/27606985387162255149739023449108101809804435888681546220650096895197184 => [3; 7, 3943855055308893592819860492729728829972062269811649460092870985028169]

Using a non-linear closure and memoizing in an array

This example solution was written specifically with the idea of providing a general representation of possibly infinitely long continued fractions. Terms can be obtained arbitrarily, in O(1) time, by their indices. One obtains Some term if the term is finite, or None() if the term is infinite.

One drawback is that, because a continued fraction is memoized, and its terms are generated as needed, the data structure may need to be updated. Therefore it must be stored in a mutable location, such as a var or ref.

(*------------------------------------------------------------------*)

#include "share/atspre_staload.hats"

staload UN = "prelude/SATS/unsafe.sats"

(*------------------------------------------------------------------*)
(* Continued fractions as processes for generating terms. The terms
   are memoized and are accessed by their zero-based index. The terms
   are represented as any one of the signed integer types for which
   there is a typekind. *)

abstype cf (tk : tkind) = ptr

typedef cf_generator (tk : tkind) =
  () -<cloref1> Option (g0int tk)

extern fn {tk : tkind}
cf_make :
  cf_generator tk -> cf tk

extern fn {tk  : tkind}
          {tki : tkind}
cf_get_at_guint :
  {i : int}
  (&cf tk >> _, g1uint (tki, i)) -> Option (g0int tk)

extern fn {tk  : tkind}
          {tki : tkind}
cf_get_at_gint :
  {i : nat}
  (&cf tk >> _, g1int (tki, i)) -> Option (g0int tk)

overload cf_get_at with cf_get_at_guint
overload cf_get_at with cf_get_at_gint
overload [] with cf_get_at

extern fn {tk : tkind}
cf2string_max_terms
          (cf        : &cf tk >> _,
           max_terms : size_t)
    : string

extern fn {tk : tkind}
cf2string_default_max_terms
          (cf : &cf tk >> _)
    : string

overload cf2string with cf2string_max_terms
overload cf2string with cf2string_default_max_terms

(*  -    -    -    -    -    -    -    -    -    -    -    -    -   *)

local

  typedef _cf (tk : tkind, terminated : bool, m : int, n : int) =
    [m <= n]
    '{
      terminated = bool terminated, (* No more terms? *)
      m = size_t m,         (* The number of terms computed so far. *)
      n = size_t n,         (* The size of memo storage.*)
      memo = arrayref (g0int tk, n), (* Memoized terms. *)
      gen = cf_generator tk          (* A thunk to generate terms. *)
    }
  typedef _cf (tk : tkind, m : int) =
    [terminated : bool]
    [n : int | m <= n]
    _cf (tk, terminated, m, n)
  typedef _cf (tk : tkind) =
    [m : int]
    _cf (tk, m)

  fn {tk : tkind}
  _cf_get_more_terms
            {terminated : bool}
            {m          : int}
            {n          : int}
            {needed     : int | m <= needed; needed <= n}
            (cf         : _cf (tk, terminated, m, n),
             needed     : size_t needed)
      : [m1 : int | m <= m1; m1 <= needed]
        [n1 : int | m1 <= n1]
        _cf (tk, m1 < needed, m1, n1) =
    let
      prval () = lemma_g1uint_param (cf.m)

      macdef memo = cf.memo

      fun
      loop {i : int | m <= i; i <= needed}
           .<needed - i>.
           (i : size_t i)
          : [m1 : int | m <= m1; m1 <= needed]
            [n1 : int | m1 <= n1]
            _cf (tk, m1 < needed, m1, n1) =
        if i = needed then
          '{
            terminated = false,
            m = needed,
            n = (cf.n),
            memo = memo,
            gen = (cf.gen)
          }
        else
          begin
            case+ (cf.gen) () of
            | None () =>
              '{
                terminated = true,
                m = i,
                n = (cf.n),
                memo = memo,
                gen = (cf.gen)
              }
            | Some term =>
              begin
                memo[i] := term;
                loop (succ i)
              end
          end
    in
      loop (cf.m)
    end

  fn {tk : tkind}
  _cf_update {terminated : bool}
             {m          : int}
             {n          : int | m <= n}
             {needed     : int}
             (cf         : _cf (tk, terminated, m, n),
              needed     : size_t needed)
      : [terminated1 : bool]
        [m1 : int | m <= m1]
        [n1 : int | m1 <= n1]
        _cf (tk, terminated1, m1, n1) =
    let
      prval () = lemma_g1uint_param (cf.m)
      macdef memo = cf.memo
      macdef gen = cf.gen
    in
      if (cf.terminated) then
        cf
      else if needed <= (cf.m) then
        cf
      else if needed <= (cf.n) then
        _cf_get_more_terms<tk> (cf, needed)
      else
        let         (* Provides about 50% more room than is needed. *)
          val n1 = needed + half needed
          val memo1 = arrayref_make_elt (n1, g0i2i 0)
          val () =
            let
              var i : [i : nat] size_t i
            in
              for (i := i2sz 0; i < (cf.m); i := succ i)
                memo1[i] := memo[i]
            end
          val cf1 =
            '{
              terminated = false,
              m = (cf.m),
              n = n1,
              memo = memo1,
              gen = (cf.gen)
            }
        in
          _cf_get_more_terms<tk> (cf1, needed)
        end
    end

in (* local *)

  assume cf tk = _cf tk

  implement {tk}
  cf_make gen =
    let
      #ifndef CF_START_SIZE #then
        #define CF_START_SIZE 8
      #endif
    in
      '{
        terminated = false,
        m = i2sz 0,
        n = i2sz CF_START_SIZE,
        memo = arrayref_make_elt (i2sz CF_START_SIZE, g0i2i 0),
        gen = gen
      }
    end

  implement {tk} {tki}
  cf_get_at_guint {i} (cf, i) =
    let
      prval () = lemma_g1uint_param i
      val i : size_t i = g1u2u i
      val cf1 = _cf_update<tk> (cf, succ i)
    in
      cf := cf1;
      if i < (cf1.m) then
        Some (arrayref_get_at<g0int tk> (cf1.memo, i))
      else
        None ()
    end

  implement {tk} {tki}
  cf_get_at_gint (cf, i) =
    cf_get_at_guint<tk><sizeknd> (cf, g1i2u i)

end (* local *)

implement {tk}
cf2string_max_terms (cf, max_terms) =
  let
    fun
    loop (i     : Size_t,
          cf    : &cf tk >> _,
          sep   : string,
          accum : string)
        : string =
      if i = max_terms then
        strptr2string (string_append (accum, ", ...]"))
      else
        begin
          case+ cf[i] of
          | None () =>
            strptr2string (string_append (accum, "]"))
          | Some term =>
            let
              val term_str = tostring_val<g0int tk> term
              val accum =
                strptr2string (string_append (accum, sep, term_str))
              val sep = if sep = "[" then "; " else ", "
            in
              loop (succ i, cf, sep, accum)
            end
        end
  in
    loop (i2sz 0, cf, "[", "")
  end

implement {tk}
cf2string_default_max_terms cf =
  let
    #ifndef DEFAULT_CF_MAX_TERMS #then
      #define DEFAULT_CF_MAX_TERMS 20
    #endif
  in
    cf2string_max_terms (cf, i2sz DEFAULT_CF_MAX_TERMS)
  end

(*------------------------------------------------------------------*)
(* r2cf: transform a rational number to a continued fraction. *)

extern fn {tk : tkind}
r2cf :
  (g0int tk, g0int tk) -> cf tk

(*  -    -    -    -    -    -    -    -    -    -    -    -    -   *)

implement {tk}
r2cf (n, d) =
  let
    val n = ref<g0int tk> n
    val d = ref<g0int tk> d

    fn
    gen () :<cloref1> Option (g0int tk) =
      if iseqz !d then
        None ()
      else
        let
          (* The method of rounding the quotient seems unimportant,
             and so let us simply use the truncation towards zero
             that is native to C. *)
          val numer = !n
          and denom = !d
          val q = numer / denom
          and r = numer mod denom
        in
          !n := denom;
          !d := r;
          Some q
        end
  in
    cf_make gen
  end

(*------------------------------------------------------------------*)

val some_rationals =
  $list (@(1LL, 2LL),
         @(3LL, 1LL),
         @(23LL, 8LL),
         @(13LL, 11LL),
         @(22LL, 7LL),
         @(~151LL, 77LL),
         @(14142LL, 10000LL),
         @(141421LL, 100000LL),
         @(1414214LL, 1000000LL),
         @(14142136LL, 10000000LL),
         @(1414213562373095049LL, 1000000000000000000LL),
         @(31LL, 10LL),
         @(314LL, 100LL),
         @(3142LL, 1000LL),
         @(31428LL, 10000LL),
         @(314285LL, 100000LL),
         @(3142857LL, 1000000LL),
         @(31428571LL, 10000000LL),
         @(314285714LL, 100000000LL),
         @(3142857142857143LL, 1000000000000000LL))

implement
main0 () =
  let
    var p : List0 @(llint, llint)
  in
    for (p := some_rationals; ~list_is_nil p; p := list_tail p)
      let
        val @(n, d) = list_head<@(llint, llint)> p
        var cf = r2cf (n, d)
      in
        println! (n, "/", d, " => ", cf2string cf)
      end
  end

(*------------------------------------------------------------------*)
Output:
$ patscc -DATS_MEMALLOC_GCBDW -O2 -std=gnu2x continued-fraction-from-rational-3.dats -lgc && ./a.out
1/2 => [0; 2]
3/1 => [3]
23/8 => [2; 1, 7]
13/11 => [1; 5, 2]
22/7 => [3; 7]
-151/77 => [-1; -1, -24, -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]
1414213562373095049/1000000000000000000 => [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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]
3142857142857143/1000000000000000 => [3; 6, 1, 142857142857142]

Using a non-linear lazy list

Translation of: Haskell

This implementation is inspired by the Haskell, although the way in which the integer divisions are done may differ.

Terms are memoized but as a linked list. For sequential access of terms, this is fine.

(* Continued fractions as non-linear lazy lists (stream types).

   I avoid the shorthands stream_make_nil and stream_make_cons,
   so the thunk-making is visible. *)

#include "share/atspre_staload.hats"

typedef cf (tk : tkind) = stream (g0int tk)

extern fn {tk : tkind}
r2cf : (g0int tk, g0int tk) -> cf tk

extern fn {tk : tkind}
cf2string : cf tk -> string

implement {tk}
r2cf (n, d) =
  let
    fun
    recurs (n : g0int tk,
            d : g0int tk)
        : cf tk =
      if iseqz d then
        $delay stream_nil ()
      else
        let
          val q = n / d
          and r = n mod d
        in
          $delay stream_cons (q, recurs (d, r))
        end
  in
    recurs (n, d)
  end

implement {tk}
cf2string cf =
  let
    val max_terms = 2000

    fun
    loop (i     : intGte 0,
          cf    : cf tk,
          slist : List0 string)
        : List0 string =
      (* One has to say "!cf" instead of just "cf", to force the lazy
         evaluation. If you simply wrote "cf", typechecking would
         fail. *)
      case+ !cf of
      | stream_nil () => list_cons ("]", slist)
      | stream_cons (term, cf) =>
        if i = max_terms then
          list_cons (",...]", slist)
        else
          let
            val sep_str =
              case+ i of
              | 0 => ""
              | 1 => ";"
              | _ => ","
            val term_str = tostring_val<g0int tk> term
            val slist = list_cons (term_str,
                                   list_cons (sep_str, slist))
          in
            loop (succ i, cf, slist)
          end

    val slist = loop (0, cf, list_sing "[")
    val slist = list_vt2t (reverse slist)
  in
    strptr2string (stringlst_concat slist)
  end

fn {tk : tkind}
show (n : g0int tk,
      d : g0int tk)
    : void =
  begin
    print! (tostring_val<g0int tk> n);
    print! "/";
    print! (tostring_val<g0int tk> d);
    print! " => ";
    println! (cf2string<tk> (r2cf<tk> (n, d)))
  end

implement
main () =
  begin
    show<intknd> (1, 2);
    show<lintknd> (g0i2i 3, g0i2i 1);
    show<llintknd> (g0i2i 23, g0i2i 8);
    show (13, 11);
    show (22L, 11L);
    show (~151LL, 77LL);
    show (14142LL, 10000LL);
    show (141421LL, 100000LL);
    show (1414214LL, 1000000LL);
    show (14142136LL, 10000000LL);
    show (1414213562373095049LL, 1000000000000000000LL);
    show (31LL, 10LL);
    show (314LL, 100LL);
    show (3142LL, 1000LL);
    show (31428LL, 10000LL);
    show (314285LL, 100000LL);
    show (3142857LL, 1000000LL);
    show (31428571LL, 10000000LL);
    show (314285714LL, 100000000LL);
    show (3142857142857143LL, 1000000000000000LL);
    0
  end;
Output:
$ patscc -g -O2 -std=gnu2x -DATS_MEMALLOC_GCBDW continued-fraction-from-rational-4.dats -lgc && ./a.out
1/2 => [0;2]
3/1 => [3]
23/8 => [2;1,7]
13/11 => [1;5,2]
22/11 => [2]
-151/77 => [-1;-1,-24,-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]
1414213562373095049/1000000000000000000 => [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,1,39,1,5,1,3,61,1,1,8,1,2,1,7,1,1,6]
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]
3142857142857143/1000000000000000 => [3;6,1,142857142857142]

Using a linear lazy list

Translation of: Haskell

This implementation is inspired by the Haskell, although the way in which the integer divisions are done may differ.

(* Continued fractions as linear lazy lists (stream_vt types).

   I use the shorthands stream_vt_make_nil and stream_vt_make_cons,
   rather than explicitly write "$ldelay". To see how the shorthands
   are implemented, see prelude/DATS/stream_vt.dats *)

#include "share/atspre_staload.hats"

vtypedef cf_vt (tk : tkind) = stream_vt (g0int tk)

extern fn {tk : tkind}
r2cf_vt : (g0int tk, g0int tk) -> cf_vt tk

(* Note that cf_vt2strptr CONSUMES the stream. The stream will no
   longer exist.

   If you are using linear streams, I would imagine you might want to
   (for instance) convert to list_vt the parts you want to reuse. *)
extern fn {tk : tkind}
cf_vt2strptr : cf_vt tk -> Strptr1

implement {tk}
r2cf_vt (n, d) =
  let
    typedef integer = g0int tk
    fun
    recurs (n : integer,
            d : integer)
        : cf_vt tk =
      if iseqz d then
        stream_vt_make_nil<integer> ()
      else
        let
          val q = n / d
          and r = n mod d
        in
          stream_vt_make_cons<integer> (q, recurs (d, r))
        end
  in
    recurs (n, d)
  end

implement {tk}
cf_vt2strptr cf =
  let
    val max_terms = 2000

    typedef integer = g0int tk

    fun
    loop (i     : intGte 0,
          cf    : cf_vt tk,
          slist : List0_vt Strptr1)
        : List0_vt Strptr1 =
      let
        val cf_con = !cf        (* Force evaluation. *)
      in
        case+ cf_con of
        | ~ stream_vt_nil () => list_vt_cons (copy "]", slist)
        | ~ stream_vt_cons (term, tail) =>
          if i = max_terms then
            let
              val slist = list_vt_cons (copy ",...]", slist)
            in
              ~ tail;
              slist
            end
          else
            let
              val sep_str =
                copy ((case+ i of
                       | 0 => ""
                       | 1 => ";"
                       | _ => ",") : string)
              val term_str = tostrptr_val<g0int tk> term
              val slist = list_vt_cons (term_str,
                                        list_vt_cons (sep_str, slist))
          in
            loop (succ i, tail, slist)
          end
      end

    val slist = loop (0, cf, list_vt_sing (copy "["))
    val slist = reverse slist
    val s = strptrlst_concat slist
    val () = assertloc (isneqz s)
  in
    s
  end

fn {tk : tkind}
show (n : g0int tk,
      d : g0int tk)
    : void =
  let
    val n_str = tostrptr_val<g0int tk> n
    and d_str = tostrptr_val<g0int tk> d
    and cf_str = cf_vt2strptr<tk> (r2cf_vt<tk> (n, d))
  in
    print! n_str;
    print! "/";
    print! d_str;
    print! " => ";
    println! cf_str;
    strptr_free n_str;
    strptr_free d_str;
    strptr_free cf_str
  end

implement
main () =
  begin
    show<intknd> (1, 2);
    show<lintknd> (g0i2i 3, g0i2i 1);
    show<llintknd> (g0i2i 23, g0i2i 8);
    show (13, 11);
    show (22L, 11L);
    show (~151LL, 77LL);
    show (14142LL, 10000LL);
    show (141421LL, 100000LL);
    show (1414214LL, 1000000LL);
    show (14142136LL, 10000000LL);
    show (1414213562373095049LL, 1000000000000000000LL);
    show (31LL, 10LL);
    show (314LL, 100LL);
    show (3142LL, 1000LL);
    show (31428LL, 10000LL);
    show (314285LL, 100000LL);
    show (3142857LL, 1000000LL);
    show (31428571LL, 10000000LL);
    show (314285714LL, 100000000LL);
    show (3142857142857143LL, 1000000000000000LL);
    0
  end;
Output:
$ patscc -g -O2 -std=gnu2x -DATS_MEMALLOC_LIBC continued-fraction-from-rational-5.dats && ./a.out
1/2 => [0;2]
3/1 => [3]
23/8 => [2;1,7]
13/11 => [1;5,2]
22/11 => [2]
-151/77 => [-1;-1,-24,-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]
1414213562373095049/1000000000000000000 => [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,1,39,1,5,1,3,61,1,1,8,1,2,1,7,1,1,6]
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]
3142857142857143/1000000000000000 => [3;6,1,142857142857142]

BASIC

FreeBASIC

'with some other constants
data 1,2, 21,7, 21,-7, 7,21, -7,21
data 23,8, 13,11, 22,7, 3035,5258, -151,-77
data -151,77, 77,151, 77,-151, -832040,1346269
data 63018038201,44560482149, 14142,10000
data 31,10, 314,100, 3142,1000, 31428,10000, 314285,100000
data 3142857,1000000, 31428571,10000000, 314285714,100000000
data 139755218526789,44485467702853
data 534625820200,196677847971, 0,0

const Inf = -(clngint(1) shl 63)

type frc
declare sub init (byval a as longint, byval b as longint)
declare function digit () as longint
   as longint n, d
end type

'member functions
sub frc.init (byval a as longint, byval b as longint)
if b < 0 then b = -b: a = -a
   n = a: d = b
end sub

function frc.digit as longint
dim as longint q, r
digit = Inf

if d then
   q = n \ d
   r = n - q * d
   'floordiv
   if r < 0 then q -= 1: r += d
   n = d: d = r

digit = q
end if
end function

'main
dim as longint a, b
dim r2cf as frc
do
   print
   read a, b
   if b = 0 then exit do

   r2cf.init(a, b)
   do
      'lazy evaluation
      a = r2cf.digit
      if a = Inf then exit do
      print a;
   loop
loop
sleep
system
Output:
 0 2
 3
-3
 0 3
-1 1 2
 2 1 7
 1 5 2
 3 7
 0 1 1 2 1 2 1 4 3 13
 1 1 24 1 2
-2 25 1 2
 0 1 1 24 1 2
-1 2 24 1 2
-1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
 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
 1 2 2 2 2 2 1 1 29
 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
 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
 2 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 1 14 1 1 16 1 1 18

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.

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

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#

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));
    }
}

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

C++

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

Testing

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

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;
}
Output:
0 2
3
2 1 7
1 5 2
3 7
-1 -1 -24 -1 -2

int main() {
	int i = 0;
	for(SQRT2 n; i++ < 20; std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(14142,10000); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(14142136,10000000); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	return 0;
}
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

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;
}
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

Clojure

(defn r2cf [n d]
  (if-not (= d 0) (cons (quot n d) (lazy-seq (r2cf d (rem n d))))))

; Example usage
(def demo '((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)))

(doseq [inputs demo 
        :let [outputs (r2cf (first inputs) (last inputs))]]
  (println inputs ";" outputs))
Output:
(1 2) ; (0 2)
(3 1) ; (3)
(23 8) ; (2 1 7)
(13 11) ; (1 5 2)
(22 7) ; (3 7)
(-151 77) ; (-1 -1 -24 -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)

Common 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)))

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)

D

Translation of: Kotlin
import std.concurrency;
import std.stdio;

struct Pair {
    int first, second;
}

auto r2cf(Pair frac) {
    return new Generator!int({
        auto num = frac.first;
        auto den = frac.second;
        while (den != 0) {
            auto div = num / den;
            auto rem = num % den;
            num = den;
            den = rem;
            div.yield();
        }
    });
}

void iterate(Generator!int seq) {
    foreach(i; seq) {
        write(i, " ");
    }
    writeln();
}

void main() {
    auto fracs = [
        Pair(   1,  2),
        Pair(   3,  1),
        Pair(  23,  8),
        Pair(  13, 11),
        Pair(  22,  7),
        Pair(-151, 77),
    ];
    foreach(frac; fracs) {
        writef("%4d / %-2d = ", frac.first, frac.second);
        frac.r2cf.iterate;
    }
    writeln;

    auto root2 = [
        Pair(    14_142,     10_000),
        Pair(   141_421,    100_000),
        Pair( 1_414_214,  1_000_000),
        Pair(14_142_136, 10_000_000),
    ];
    writeln("Sqrt(2) ->");
    foreach(frac; root2) {
        writef("%8d / %-8d = ", frac.first, frac.second);
        frac.r2cf.iterate;
    }
    writeln;

    auto pi = [
        Pair(         31,          10),
        Pair(        314,         100),
        Pair(      3_142,       1_000),
        Pair(     31_428,      10_000),
        Pair(    314_285,     100_000),
        Pair(  3_142_857,   1_000_000),
        Pair( 31_428_571,  10_000_000),
        Pair(314_285_714, 100_000_000),
    ];
    writeln("Pi ->");
    foreach(frac; pi) {
        writef("%9d / %-9d = ", frac.first, frac.second);
        frac.r2cf.iterate;
    }
}
Output:
   1 / 2  = 0 2
   3 / 1  = 3
  23 / 8  = 2 1 7
  13 / 11 = 1 5 2
  22 / 7  = 3 7
-151 / 77 = -1 -1 -24 -1 -2

Sqrt(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

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


Delphi

Works with: Delphi version 6.0


function GetNextFraction(var N1,N2: integer): integer;
{Get next step in fraction series}
var R: integer;
begin
R:=FloorMod(N1, N2);
Result:= FloorDiv(N1 - R , N2);
N1 := N2;
N2 := R;
end;

procedure GetFractionList(N1,N2: integer; var IA: TIntegerDynArray);
{Get list of continuous fraction values}
var M1, M2,F : integer;
var S: integer;
begin
SetLength(IA,0);
M1 := N1;
M2 := N2;
while M2<>0 do
	begin
	F:=GetNextFraction(M1,M2);
	SetLength(IA,Length(IA)+1);
	IA[High(IA)]:=F;
	end;
end;


procedure ShowConFraction(Memo: TMemo; N1,N2: integer);
{Calculate and display continues fraction for Rational number N1/N2}
var I: integer;
var S: string;
var IA: TIntegerDynArray;
begin
GetFractionList(N1,N2,IA);
S:='[';
for I:=0 to High(IA) do
	begin
	if I>0 then S:=S+', ';
	S:=S+IntToStr(IA[I]);
	end;
S:=S+']';
Memo.Lines.Add(Format('%10d / %10d --> ',[N1,N2])+S);
end;


procedure ShowContinuedFractions(Memo: TMemo);
{Show all continued fraction tests}
begin
Memo.Lines.Add('Wikipedia Example');
ShowConFraction(Memo,415,93);

Memo.Lines.Add('');
Memo.Lines.Add('Rosetta Code Examples');
ShowConFraction(Memo,1, 2);
ShowConFraction(Memo,3, 1);
ShowConFraction(Memo,23, 8);
ShowConFraction(Memo,13, 11);
ShowConFraction(Memo,22, 7);
ShowConFraction(Memo,-151, 77);


Memo.Lines.Add('');
Memo.Lines.Add('Square Root of Two');
ShowConFraction(Memo,14142, 10000);
ShowConFraction(Memo,141421, 100000);
ShowConFraction(Memo,1414214, 1000000);
ShowConFraction(Memo,14142136, 10000000);

Memo.Lines.Add('');
Memo.Lines.Add('PI');
ShowConFraction(Memo,31, 10);
ShowConFraction(Memo,314, 100);
ShowConFraction(Memo,3142, 1000);
ShowConFraction(Memo,31428, 10000);
ShowConFraction(Memo,314285, 100000);
ShowConFraction(Memo,3142857, 1000000);
ShowConFraction(Memo,31428571, 10000000);
ShowConFraction(Memo,314285714, 100000000);
end;
Output:
Wikipedia Example
       415 /         93 --> [4, 2, 6, 7]

Rosetta Code Examples
         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]

Square Root of Two
     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]

PI
        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]
Elapsed Time: 41.009 ms.


EDSAC order code

Besides the assigned task, this program demonstrates a division subroutine for 35-bit positive integers, returning quotient and remainder.

 [Continued fractions from rationals.
  EDSAC program, Initial Orders 2.]

 [Memory usage:
   56..109  Print subroutine, modified from the EDSAC library
  110..146  Division subroutine for long positive integers
  148..196  Continued fraction subroutine, as specified by Rosetta Code
  200..260  Main routine
  262..     List of rationals, variable number of items]

 [Define where to store the list of rationals.]
          T  45 K [store address in location 45;
                   values are then accessed by code letter H (*)]
          P 262 F [<------ address here]
 [(*) Arbitrary choice. We could equally well use 46 and N, 47 and M, etc.]

 [Library subroutine R2. Reads positive integers during input of orders,
    and is then overwritten (so doesn't take up any memory).
  Negative numbers can be input by adding 2^35.
  Each integer is followed by 'F', except the last is followed by '#TZ'.]
  GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z
          T    #H  [Tell R2 the storage location defined above]

 [Rationals to be read by R2. First item is count, then num/den pairs.]
  8F 1F2F 3F1F 33F8F 13F11F 22F7F 34359738217F77F
  141421356F100000000F 314285714F100000000#TZ

 [----------------------------------------------------------------------
  Modification of library subroutine P7.
  Prints signed integer up to 10 digits, left-justified.
  54 storage locations; working position 4D.
  Must be loaded at an even address.
  Input: Number is at 0D.]
          T  56 K
  GKA3FT42@A49@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@TF
  H17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@
  T31@A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFSFL8FT4DE39@

 [----------------------------------------------------------------------
  Division subroutine for long positive integers.
  35-bit dividend and divisor (max 2^34 - 1)
    returning quotient and remainder.
  Input:  dividend at 4D, divisor at 6D
  Output: remainder at 4D, quotient at 6D.
  Working locations 0D, 8D.]
          T 110 K
          G     K
          A   3 F [plant link]
          T  35 @
          A   6 D [load divisor]
          U   8 D [save at 8D (6D is required for quotient)]
    [4]   T     D [initialize shifted divisor]
          A   4 D [load dividend]
          R     D [shift 1 right]
          S     D [shifted divisor > dividend/2 yet?]
          G  13 @ [yes, start subtraction]
          T  36 @ [no, clear acc]
          A     D [shift divisor 1 more]
          L     D
          E   4 @ [loop back (always, since acc >= 0)]
   [13]   T  36 @ [clear acc]
          T   6 D [initialize quotient to 0]
   [15]   A   4 D [load remainder (initially = dividend)]
          S     D [trial subtraction]
          G  23 @ [skip if can't subtract]
          T   4 D [update remainder]
          A   6 D [load quotient]
          Y     F [add 1 by rounding twice (*)]
          Y     F
          T   6 D
   [23]   T  36 @ [clear acc]
          A   8 D [load original divisor]
          S     D [is shifted divisor back to original?]
          E  35 @ [yes, exit (with accumulator = 0,
                   in accordance with EDSAC convention)]
          T  36 @ [no, clear acc]
          A     D [shift divisor 1 right]
          R     D
          T     D
          A   6 D [shift quotient 1 left]
          L     D
          T   6 D
          E  15 @ [loop back (always, since acc = 0)]
   [35]   E     F [return; order set up at runtime]
   [36]   P     F [junk word, to clear accumulator]

 [(*) This saves the bother of defining a double-word constant 1
      and making sure that it's at an even address.]

 [----------------------------------------------------------------------
  Subroutine for lazy evaluation of continued fraction.
  Must be loaded at an even address.
  Locations relative to start of subroutine:
  0:    Entry point
  1:    Flag, < 0 if c.f. is finished, >= 0 if there's another term
  2, 3: Next term of c.f., provided the flag (location 1) is >= 0
  4, 5: Caller places numerator here before first call
  6, 7: Caller places denominator here before first call; must be > 0

  After setting up the numerator and denominator of the rational number,
    the caller should repeatedly call location 0, reading the result
    from location 1 and double location 2.
  Locations 4..7 are maintained by the subroutine and should not be changed
    by the caller until a new continued fraction is required.]

          T  46 K [place address of subroutine in location 46]
          P 148 F
          E  25 K [load the code below to that address (WWG page 18)]
          T     N
          G     K
    [0]   G   8 @ [entry point]
    [1]   P     F [flag returned here]
    [2]   P F P F [term returned here, if flag >= 0;
                   also used as temporary store]
    [4]   P F P F [caller puts numerator here]
    [6]   P F P F [caller puts denominator here]
    [8]   A   3 F [plant link]
          T  28 @
          S   6#@ [load negative of denominator]
          E  44 @ [if denom <= 0, no more terms]
          T     F [clear acc]
          A   4#@ [load numerator]
          T   2#@ [save before overwriting]
          A   6#@ [load denominator]
          U   4#@ [make it numerator for next call]
          T   6 D [also to 6D for division]
          A   2#@ [load numerator]
          G  29 @ [special action if negative]
          T   4 D [to 4D for division]
   [21]   A  21 @ [for return from next]
          G 110 F [call the above division subroutine]
          A   4 D [load remainder]
          T   6#@ [make it denominator for next call]
          A   6 D [load quotient]
   [26]   T   2#@ [return it as next term]
   [27]   T   1 @ [flag >= 0 means term is valid]
   [28]   E     F [exit with acc = 0]

         [Here if rational = -n/d where n, d > 0. Principle is:
          if  n + d - 1 = qd + r  then  -n = -qd + (d - 1 - r)]
   [29]   T   4 D [save numerator in 4D]
          S   6 D [acc := -den]
          Y     F [add 1 by rounding twice]
          Y     F
          T   2#@ [save (1 - den) for later]
          S   4 D [load abs(num)]
          S   2#@ [add (den - 1)]
          T   4 D [to 4D for division]
   [37]   A  37 @ [for return from next]
          G 110 F [call the above division subroutine]
          S   2#@ [load (den - 1)]
          S   4 D [subtract remainder]
          T   6#@ [result is new denominator]
          S   6 D [load negated quotient]
          G  26 @ [join common code]

         [Here if there are no more terms of the c.f.]
   [44]   T     F [clear acc]
          A   8 @ [this is negative since 'A' = -4]
          G  27 @ [exit with negative flag]

 [----------------------------------------------------------------------
  Main routine]
          T 200 K
          G     K
    [Variables]
    [0]   P     F [negative counter of continued fractions]
    [1]   P     F [character before term, first '=' then ',']
    [Constants]
    [2]   P     D [single-word 1]
    [3]   A   2#H [order to load first numerator]
    [4]   P   2 F [to inc addresses by 2]
    [5]   #     F [teleprinter figures shift]
    [6]   X     F [slash (in figures mode)]
    [7]   V     F [equals sign (in figures mode)]
    [8]   N     F [comma (in figures mode)]
    [9]   !     F [space]
   [10]   @     F [carriage return]
   [11]   &     F [line feed]
   [12]   K4096 F [teleprinter null]

          [Enter with acc = 0]
   [13]   O   5 @ [set teleprinter to figures]
          S     H [negative of number of c.f.s]
          T     @ [initialize counter]
          A   3 @ [initial load order]
   [17]   U  22 @ [plant order to load numerator]
          A   4 @ [inc address by 2]
          T  28 @ [plant order to load denominator]
          A   7 @ [set to print '=' before first term]
          T   1 @

          [Demonstrate the subroutine above.
          Since its address was placed in location 46,
          we can use code letter N to refer to it.]
   [22]   A    #H [load numerator (order set up at runtime)]
          U   4#N [pass to subroutine]
          T     D [also to 0D for printing]
   [25]   A  25 @ [for return from print subroutine]
          G  56 F [print numerator]
          O   6 @ [followed by slash]
   [28]   A    #H [load denominator (order set up at runtime)]
          U   6#N [pass to subroutine]
          T     D [also to 0D for printing]
   [31]   A  31 @ [for return from print subroutine]
          G  56 F [print denominator]
          O   9 @ [followed by space]
   [34]   A  34 @ [for return from subroutine]
          G     N [call subroutine for next term]
          A   1 N [load flag]
          G  48 @ [if < 0, c.f. is finished, jump out]
          O   1 @ [print equals or comma]
          O   9 @ [print space]
          T     F [clear acc]
          A   2#N [load term]
          T     D [to 0D for printing]
   [43]   A  43 @ [for return from print subroutine]
          G  56 F [print term; clears acc]
          A   8 @ [set to print ',' before subsequent terms]
          T   1 @
          E  34 @ [loop back for next term]

         [On to next continued fraction]
   [48]   O  10 @ [print new line]
          O  11 @
          T     F [clear acc]
          A     @ [load negative count of c.f.s]
          A   2 @ [add 1]
          E  59 @ [exit if count = 0]
          T     @ [store back]
          A  22 @ [order to load numerator]
          A   4 @ [inc address by 4 for next c.f.]
          A   4 @
          G  17 @ [loop back (always, since 'A' < 0)]

   [59]   O  12 @ [print null to flush teleprinter buffer]
          Z     F [stop]

          E  13 Z [define entry point]
          P     F [acc = 0 on entry]
Output:
1/2 = 0, 2
3/1 = 3
33/8 = 4, 8
13/11 = 1, 5, 2
22/7 = 3, 7
-151/77 = -2, 25, 1, 2
141421356/100000000 = 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 1, 1, 2, 6, 8
314285714/100000000 = 3, 7, 7142857


F#

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

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]
A version for larger numerators and denominators.
let rec rI2cf n d =
    if d = 0I then []
    else let q = n / d in (decimal)q :: (rI2cf d (n - q * d))

Factor

Note that the input values are stored as strings and converted to numbers before being fed to r2cf. This is because ratios automatically reduce themselves to the lowest-terms mixed number, which would make for confusing output in this instance.

USING: formatting kernel lists lists.lazy math math.parser qw
sequences ;
IN: rosetta-code.cf-arithmetic

: r2cf ( x -- lazy )
    [ >fraction [ /mod ] keep swap [ ] [ / ] if-zero nip ]
    lfrom-by [ integer? ] luntil [ >fraction /i ] lmap-lazy ;

: main ( -- )
    qw{
        1/2
        3
        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
    }
    [ dup string>number r2cf list>array "%19s -> %u\n" printf ]
    each ;
    
MAIN: main
Output:
                1/2 -> { 0 2 }
                  3 -> { 3 }
               23/8 -> { 2 1 7 }
              13/11 -> { 1 5 2 }
               22/7 -> { 3 7 }
            -151/77 -> { -1 -1 -24 -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 }

Forth

Works with: gforth version 0.7.3
: r2cf ( num1 den1 -- num2 den2 )  swap over >r s>d r> sm/rem . ;

: .r2cf ( num den -- )
  cr 2dup swap . ." / " . ." : "
  begin
  r2cf dup 0<> while
  repeat 2drop ;

: r2cf-demo
            1 2 .r2cf
            3 1 .r2cf
            23 8 .r2cf
            13 11 .r2cf
            22 7 .r2cf
            -151 77 .r2cf
            14142 10000 .r2cf
            141421 100000 .r2cf
            1414214 1000000 .r2cf
            14142136 10000000 .r2cf
            31 10 .r2cf
            314 100 .r2cf
            3142 1000 .r2cf
            31428 10000 .r2cf
            314285 100000 .r2cf
            3142857 1000000 .r2cf
            31428571 10000000 .r2cf
            314285714 100000000 .r2cf
            3141592653589793 1000000000000000 .r2cf ;
r2cf-demo
Output:
1 / 2 : 0 2 
3 / 1 : 3 
23 / 8 : 2 1 7 
13 / 11 : 1 5 2 
22 / 7 : 3 7 
-151 / 77 : -1 -1 -24 -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  ok


Fortran

program r2cf_demo
  implicit none

  call write_r2cf (1, 2)
  call write_r2cf (3, 1)
  call write_r2cf (23, 8)
  call write_r2cf (13, 11)
  call write_r2cf (22, 7)
  call write_r2cf (-151, 77)

  call write_r2cf (14142, 10000)
  call write_r2cf (141421, 100000)
  call write_r2cf (1414214, 1000000)
  call write_r2cf (14142136, 10000000)

  call write_r2cf (31, 10)
  call write_r2cf (314, 100)
  call write_r2cf (3142, 1000)
  call write_r2cf (31428, 10000)
  call write_r2cf (314285, 100000)
  call write_r2cf (3142857, 1000000)
  call write_r2cf (31428571, 10000000)
  call write_r2cf (314285714, 100000000)

contains

  ! This implementation of r2cf both modifies its arguments and
  ! returns a value.
  function r2cf (N1, N2) result (q)
    integer, intent(inout) :: N1, N2
    integer :: q

    integer r

    ! We will use floor division, where the quotient is rounded
    ! towards negative infinity. Whenever the divisor is positive,
    ! this type of division gives a non-negative remainder.
    r = modulo (N1, N2)
    q = (N1 - r) / N2

    N1 = N2
    N2 = r
  end function r2cf

  subroutine write_r2cf (N1, N2)
    integer, intent(in) :: N1, N2

    integer :: digit, M1, M2
    character(len = :), allocatable :: sep

    write (*, '(I0, "/", I0, " => ")', advance = "no") N1, N2

    M1 = N1
    M2 = N2
    sep = "["
    do while (M2 /= 0)
       digit = r2cf (M1, M2)
       write (*, '(A, I0)', advance = "no") sep, digit
       if (sep == "[") then
          sep = "; "
       else
          sep = ", "
       end if
    end do
    write (*, '("]")', advance = "yes")
  end subroutine write_r2cf

end program r2cf_demo
Output:
$ gfortran -std=f2018 continued-fraction-from-rational.f90 && ./a.out
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]

Go

(Note, the files making up this package are re-used as presented here for for the Continued_fraction/Arithmetic/G(matrix_NG,_Contined_Fraction_N)#Go and Continued_fraction/Arithmetic/G(matrix_NG,_Contined_Fraction_N1,_Contined_Fraction_N2)#Go tasks.)

File cf.go:

package cf

import (
	"fmt"
	"strings"
)

// ContinuedFraction is a regular continued fraction.
type ContinuedFraction func() NextFn

// NextFn is a function/closure that can return
// a posibly infinite sequence of values.
type NextFn func() (term int64, ok bool)

// String implements fmt.Stringer.
// It formats a maximum of 20 values, ending the
// sequence with ", ..." if the sequence is longer.
func (cf ContinuedFraction) String() string {
	var buf strings.Builder
	buf.WriteByte('[')
	sep := "; "
	const maxTerms = 20
	next := cf()
	for n := 0; ; n++ {
		t, ok := next()
		if !ok {
			break
		}
		if n > 0 {
			buf.WriteString(sep)
			sep = ", "
		}
		if n >= maxTerms {
			buf.WriteString("...")
			break
		}
		fmt.Fprint(&buf, t)
	}
	buf.WriteByte(']')
	return buf.String()
}

// Sqrt2 is the continued fraction for √2, [1; 2, 2, 2, ...].
func Sqrt2() NextFn {
	first := true
	return func() (int64, bool) {
		if first {
			first = false
			return 1, true
		}
		return 2, true
	}
}

// Phi is the continued fraction for ϕ, [1; 1, 1, 1, ...].
func Phi() NextFn {
	return func() (int64, bool) { return 1, true }
}

// E is the continued fraction for e,
// [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, ...].
func E() NextFn {
	var i int
	return func() (int64, bool) {
		i++
		switch {
		case i == 1:
			return 2, true
		case i%3 == 0:
			return int64(i/3) * 2, true
		default:
			return 1, true
		}
	}
}

File rat.go:

package cf

import "fmt"

// A Rat represents a quotient N/D.
type Rat struct {
	N, D int64
}

// String implements fmt.Stringer and returns a string
// representation of `r` in the form "N/D" (even if D == 1).
func (r Rat) String() string {
	return fmt.Sprintf("%d/%d", r.N, r.D)
}

// As ContinuedFraction returns a contined fraction representation of `r`.
func (r Rat) AsContinuedFraction() ContinuedFraction { return r.CFTerms }
func (r Rat) CFTerms() NextFn {
	return func() (int64, bool) {
		if r.D == 0 {
			return 0, false
		}
		q := r.N / r.D
		r.N, r.D = r.D, r.N-q*r.D
		return q, true
	}
}

// Rosetta Code task explicitly asked for this function,
// so here it is. We'll just use the types above instead.
func r2cf(n1, n2 int64) ContinuedFraction { return Rat{n1, n2}.CFTerms }

File rat_test.go:

package cf

import (
	"fmt"
	"math"
)

func Example_ConstructFromRational() {
	cases := [...]Rat{
		{1, 2},
		{3, 1},
		{23, 8},
		{13, 11},
		{22, 7},
		{-151, 77},
	}
	for _, r := range cases {
		fmt.Printf("%7s = %s\n", r, r.AsContinuedFraction())
	}

	for _, tc := range [...]struct {
		name   string
		approx float64
		cf     ContinuedFraction
		d1, d2 int64
	}{
		{"√2", math.Sqrt2, Sqrt2, 1e4, 1e8},
		{"π", math.Pi, nil, 10, 1e10},
		{"ϕ", math.Phi, Phi, 10, 1e5},
		{"e", math.E, E, 1e5, 1e9},
	} {
		fmt.Printf("\nApproximating %s ≅ %v:\n", tc.name, tc.approx)
		for d := tc.d1; d < tc.d2; d *= 10 {
			n := int64(math.Round(tc.approx * float64(d)))
			r := Rat{n, d}
			fmt.Println(r, "=", r.AsContinuedFraction())
		}
		if tc.cf != nil {
			wid := int(math.Log10(float64(tc.d2)))*2 + 2 // ick
			fmt.Printf("%*s: %v\n", wid, "Actual", tc.cf)
		}
	}

	// Output:
	// [… commented output used by go test omitted for
	//    Rosetta Code listing; it is the same as below …]
}
Output:
    1/2 = [0; 2]
    3/1 = [3]
   23/8 = [2; 1, 7]
  13/11 = [1; 5, 2]
   22/7 = [3; 7]
-151/77 = [-1; -1, -24, -1, -2]

Approximating √2 ≅ 1.4142135623730951:
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]
            Actual: [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...]

Approximating π ≅ 3.141592653589793:
31/10 = [3; 10]
314/100 = [3; 7, 7]
3142/1000 = [3; 7, 23, 1, 2]
31416/10000 = [3; 7, 16, 11]
314159/100000 = [3; 7, 15, 1, 25, 1, 7, 4]
3141593/1000000 = [3; 7, 16, 983, 4, 2]
31415927/10000000 = [3; 7, 15, 1, 354, 2, 6, 1, 4, 1, 2]
314159265/100000000 = [3; 7, 15, 1, 288, 1, 2, 1, 3, 1, 7, 4]
3141592654/1000000000 = [3; 7, 15, 1, 293, 11, 1, 1, 7, 2, 1, 3, 3, 2]

Approximating ϕ ≅ 1.618033988749895:
16/10 = [1; 1, 1, 2]
162/100 = [1; 1, 1, 1, 1, 1, 2, 2]
1618/1000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
16180/10000 = [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]
      Actual: [1; 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]

Approximating e ≅ 2.718281828459045:
271828/100000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 10, 1, 1, 2]
2718282/1000000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 3, 141]
27182818/10000000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 11, 1, 2, 10, 6, 2]
271828183/100000000 = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 2, 1, 1, 17, 6, 1, 1, 1, ...]
              Actual: [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, ...]

Haskell

Translation of: Python

This more general version generates a continued fraction from any real number (with rationals as a special case):

import Data.Ratio ((%))

real2cf :: (RealFrac a, Integral b) => a -> [b]
real2cf x =
  let (i, f) = properFraction x
  in i :
     if f == 0
       then []
       else real2cf (1 / f)

main :: IO ()
main =
  mapM_
    print
    [ real2cf (13 % 11)
    , take 20 $ real2cf (sqrt 2)
    ]
Output:
[1,5,2]
[1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

Icon

Here, for each test case, r2cf is really "called" only once, but then suspended and resumed repeatedly.

procedure main ()
  write_r2cf (1, 2)
  write_r2cf (3, 1)
  write_r2cf (23, 8)
  write_r2cf (13, 11)
  write_r2cf (22, 7)
  write_r2cf (-151, 77)
  write_r2cf (14142, 10000)
  write_r2cf (141421, 100000)
  write_r2cf (1414214, 1000000)
  write_r2cf (14142136, 10000000)

  # Decimal expansion of sqrt(2): https://oeis.org/A002193
  write_r2cf (141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157,
              100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

  write_r2cf (31, 10)
  write_r2cf (314, 100)
  write_r2cf (3142, 1000)
  write_r2cf (31428, 10000)
  write_r2cf (314285, 100000)
  write_r2cf (3142857, 1000000)
  write_r2cf (31428571, 10000000)
  write_r2cf (314285714, 100000000)

  # 22/7 = 3 + 1/7 = 3 + 0.142857...
  write_r2cf (3142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857,
              1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
end

procedure write_r2cf (N1, N2)
  local sep, digit

  writes (N1, "/", N2, " => ")
  sep := "["
  every digit := r2cf (N1, N2) do {
    writes (sep, digit)
    sep := (if sep == "[" then "; " else ", ")
  }
  write ("]")
end

procedure r2cf (N1, N2)
  local q, r
  while N2 ~= 0 do {
    # We will use Icon's native version of integer division, which
    # rounds quotients towards zero, and so may return a negative
    # remainder.
    q := N1 / N2
    r := N1 % N2
    N1 := N2
    N2 := r
    suspend q
  }
end
Output:
 $ icon continued-fraction-from-rational.icn
1/2 => [0; 2]
3/1 => [3]
23/8 => [2; 1, 7]
13/11 => [1; 5, 2]
22/7 => [3; 7]
-151/77 => [-1; -1, -24, -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]
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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, 5, 1, 8, 3, 1, 2, 2, 1, 6, 2, 2, 3, 1, 2, 3, 1, 1, 39, 1, 3, 1, 2, 4, 10, 1, 6, 1, 30, 5, 2, 1, 1, 1, 1, 1, 32, 1, 4, 18, 124, 3, 2, 1, 1, 8, 1, 1, 1, 6, 15, 2, 3, 2, 7, 1, 4, 9, 2, 7, 1, 1, 1, 1, 1, 2, 1, 10, 1, 31, 5, 1, 1, 1, 7, 1, 14, 10, 3, 11, 1, 2, 1, 65, 4, 9, 2, 3, 2, 2, 9, 1, 1, 2, 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]
3142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857/1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [3; 7, 142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857142857]

J

Note that the continued fractions shown in this task differ from those in the Continued fraction task as b here is implicitly always 1.

Tacit version 1

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.

cf=: _1 1 ,@}. (, <.)@%@-/ ::]^:a:@(, <.)@(%&x:/)

Examples

   cf each 1 2;3 1;23 8;13 11;22 7;14142136 10000000;_151 77
┌───┬─┬─────┬─────┬───┬─────────────────────────────────┬─────────┐
0 232 1 71 5 23 71 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 291 2 2 2 2 2 2 3 1 1 3 1 7 21 2 2 2 2 2 2 2 3 6 1 2 1 121 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 103 7 73 7 23 1 23 7 3573 7 28573 7 1428573 7 476190 33 7 7142857
└────┴─────┴──────────┴───────┴────────┴──────────┴────────────┴───────────┘

This tacit version first produces the answer with a trailing ∞ (represented by _ in J) which is then removed by the last operation (_1 1 ,@}. ...). A continued fraction can be evaluated using the verb ((+%)/) and both representations produce equal results,

   3 7 =&((+ %)/) 3 7 _
1

Incidentally, J and Tcl report a different representation for -151/77 versus the representation of some other implementations; however, both representations produce equal results.

   _2 25 1 2 =&((+ %)/) _1 _1 _24 _1 _2
1

Tacit version 2

Translation of python

r2cf=:1 1{."1@}.({:,(0,{:)#:{.)^:(*@{:)^:a:

Example use:

   ((":@{.,'/',":@{:),':  ',":@r2cf)@>1 2;3 1;23 8;13 11;22 7;14142136 10000000;_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 
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                                  
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

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.

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                        │
└─────────────────┴─────────────────────────────────┘
)

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 232 1 71 5 23 71 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2 __2 25 1 2
└───┴─┴─────┴─────┴───┴───────────────────────────────────┴─────────┘

version 3

translation of python:

r2cf=:3 :0
  'n1 n2'=. y
  r=.''
  while.n2 do.
    'n1 t1 n2'=. n2,(0,n2)#:n1
    r=.r,t1
  end.
)

Example:

   r2cf each 1 2;3 1;23 8;13 11;22 7;14142136 10000000;_151 77
┌───┬─┬─────┬─────┬───┬─────────────────────────────────┬─────────┐
0 232 1 71 5 23 71 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2_2 25 1 2
└───┴─┴─────┴─────┴───┴─────────────────────────────────┴─────────┘

Java

Translation of: Kotlin
Works with: Java version 9
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class ConstructFromRationalNumber {
    private static class R2cf implements Iterator<Integer> {
        private int num;
        private int den;

        R2cf(int num, int den) {
            this.num = num;
            this.den = den;
        }

        @Override
        public boolean hasNext() {
            return den != 0;
        }

        @Override
        public Integer next() {
            int div = num / den;
            int rem = num % den;
            num = den;
            den = rem;
            return div;
        }
    }

    private static void iterate(R2cf generator) {
        generator.forEachRemaining(n -> System.out.printf("%d ", n));
        System.out.println();
    }

    public static void main(String[] args) {
        List<Map.Entry<Integer, Integer>> fracs = List.of(
                Map.entry(1, 2),
                Map.entry(3, 1),
                Map.entry(23, 8),
                Map.entry(13, 11),
                Map.entry(22, 7),
                Map.entry(-151, 77)
        );
        for (Map.Entry<Integer, Integer> frac : fracs) {
            System.out.printf("%4d / %-2d = ", frac.getKey(), frac.getValue());
            iterate(new R2cf(frac.getKey(), frac.getValue()));
        }

        System.out.println("\nSqrt(2) ->");
        List<Map.Entry<Integer, Integer>> root2 = List.of(
                Map.entry(    14_142,     10_000),
                Map.entry(   141_421,    100_000),
                Map.entry( 1_414_214,  1_000_000),
                Map.entry(14_142_136, 10_000_000)
        );
        for (Map.Entry<Integer, Integer> frac : root2) {
            System.out.printf("%8d / %-8d = ", frac.getKey(), frac.getValue());
            iterate(new R2cf(frac.getKey(), frac.getValue()));
        }

        System.out.println("\nPi ->");
        List<Map.Entry<Integer, Integer>> pi = List.of(
                Map.entry(         31,        10),
                Map.entry(        314,       100),
                Map.entry(      3_142,      1_000),
                Map.entry(     31_428,     10_000),
                Map.entry(    314_285,    100_000),
                Map.entry(  3_142_857,   1_000_000),
                Map.entry( 31_428_571,  10_000_000),
                Map.entry(314_285_714, 100_000_000)
        );
        for (Map.Entry<Integer, Integer> frac : pi) {
            System.out.printf("%9d / %-9d = ", frac.getKey(), frac.getValue());
            iterate(new R2cf(frac.getKey(), frac.getValue()));
        }
    }
}
Output:
   1 / 2  = 0 2 
   3 / 1  = 3 
  23 / 8  = 2 1 7 
  13 / 11 = 1 5 2 
  22 / 7  = 3 7 
-151 / 77 = -1 -1 -24 -1 -2 

Sqrt(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 

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

jq

Adapted from Wren

Works with jq, the C implementation of jq

Works with gojq, the Go implementation of jq

With a few minor tweaks, the following program also works with jaq, the Rust implementation of jq.

### Generic utilities

def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
def rpad($len): tostring | ($len - length) as $l | . + (" " * $l);

# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be a pair of integers.
def divmod($i; $j):
  ($i % $j) as $mod
  | [($i - $mod) / $j, $mod] ;

def whilst(cond; update):
     def _whilst:
         if cond then update | (., _whilst) else empty end;
     _whilst;


### Continued fractions

# $a/$b
def toContFrac($a; $b):
  {$a,$b}
  | whilst( .b != 0;
      divmod(.a; .b) as [$d, $r]
      | .a = .b
      | .b = $r
      | .d = $d
      | if .a == 1 then .b = 0 end)
  | .d ;

def examples: [
  {heading: "Examples ->",
   group:   [ [1, 2], [3, 1], [23, 8], [13, 11], [22, 7], [-151, 77] ],
   lengths: [4,2] },
   
  {heading: "Sqrt(2) ->",
   group:   [ [14142, 10000], [141421, 100000], [1414214, 1000000], [14142136, 10000000] ],
   lengths: [8,8]},
   
  {heading: "Pi ->",
   group:   [ [31, 10], [314, 100], [3142, 1000], [31428, 10000], [314285, 100000], [3142857, 1000000],
              [31428571, 10000000], [314285714,100000000]],
   lengths: [9, 9] }
];

def task:
  examples[]
  | .lengths as $lengths
  | .heading,
    (foreach .group[] as [$a, $b] (.;
           .emit = "\($a|lpad($lengths[0])) / \($b|rpad($lengths[1]))"
           | .emit += " = " + ([toContFrac($a;$b)] | join(" "))  )
         | .emit ),
    "";

task
Output:

As for Wren.

Julia

Works with: Julia version 0.6
# It'st most appropriate to define a Julia iterable object for this task
# Julia doesn't have Python'st yield, the closest to it is produce/consume calls with Julia tasks
# but for various reasons they don't work out for this task
# This solution works with two integers, a Julia rational or a real

mutable struct ContinuedFraction{T<:Integer}
    n1::T # numerator or real
    n2::T # denominator or 1 if real
    t1::T # generated coefficient
end

# Constructors for all possible input types
ContinuedFraction{T<:Integer}(n1::T, n2::T) = ContinuedFraction(n1, n2, 0)
ContinuedFraction(n::Rational) = ContinuedFraction(numerator(n), denominator(n))
ContinuedFraction(n::AbstractFloat) = ContinuedFraction(Rational(n))

# Methods to make our object iterable
Base.start(::ContinuedFraction) = nothing
# Returns true if we've prepared the continued fraction
Base.done(cf::ContinuedFraction, st) = cf.n2 == 0
# Generates the next coefficient
function Base.next(cf::ContinuedFraction, st)
    cf.n1, (cf.t1, cf.n2) = cf.n2, divrem(cf.n1, cf.n2)
    return cf.t1, nothing
end

# Tell Julia that this object always returns ints (all coeffs are integers)
Base.eltype{T}(::Type{ContinuedFraction{T}}) = T

# Overload the default collect function so that we can collect the first maxiter coeffs of infinite continued fractions
# array slicing doesn't work as Julia crashes before the slicing due to our infinitely long array
function Base.collect(itr::ContinuedFraction, maxiter::Integer = 100)
    r = Array{eltype(itr)}(maxiter)
    i = 1
    for v in itr
        r[i] = v
        i += 1
        if i > maxiter break end
    end
    return r[1:i-1]
end

# Test cases according to task description with outputs in comments
println(collect(ContinuedFraction(1, 2)))       # => [0, 2]
println(collect(ContinuedFraction(3, 1)))       # => [3]
println(collect(ContinuedFraction(23, 8)))      # => [2, 1, 7]
println(collect(ContinuedFraction(13, 11)))     # => [1, 5, 2]
println(collect(ContinuedFraction(22, 7)))      # => [3, 7]
println(collect(ContinuedFraction(14142, 10000)))       # => [1, 2, 2, 2, 2, 2, 1, 1, 29]
println(collect(ContinuedFraction(141421, 100000)))     # => [1, 2, 2, 2, 2, 2, 2, 3, 1, 1, 3, 1, 7, 2]
println(collect(ContinuedFraction(1414214, 1000000)))   # => [1, 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12]
println(collect(ContinuedFraction(14142136, 10000000))) # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2]

println(collect(ContinuedFraction(13 // 11)))   # => [1, 5, 2]
println(collect(ContinuedFraction(2), 20))     # => [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Kotlin

// version 1.1.2
// compile with -Xcoroutines=enable flag from command line

import kotlin.coroutines.experimental.buildSequence

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 iterate(seq: Sequence<Int>) {
    for (i in seq) print("$i ")
    println()
}

fun main(args: Array<String>) {
    val fracs = arrayOf(1 to 2, 3 to 1, 23 to 8, 13 to 11, 22 to 7, -151 to 77)
    for (frac in fracs) {
        print("${"%4d".format(frac.first)} / ${"%-2d".format(frac.second)} = ")
        iterate(r2cf(frac))
    }
    val root2 = arrayOf(14142 to 10000, 141421 to 100000,
                        1414214 to 1000000, 14142136 to 10000000)
    println("\nSqrt(2) ->")
    for (frac in root2) {
        print("${"%8d".format(frac.first)} / ${"%-8d".format(frac.second)} = ")
        iterate(r2cf(frac))
    }
    val pi = arrayOf(31 to 10, 314 to 100, 3142 to 1000, 31428 to 10000,
                     314285 to 100000, 3142857 to 1000000,
                     31428571 to 10000000, 314285714 to 100000000)
    println("\nPi ->")
    for (frac in pi) {
        print("${"%9d".format(frac.first)} / ${"%-9d".format(frac.second)} = ")
        iterate(r2cf(frac))
    }
}
Output:
   1 / 2  = 0 2 
   3 / 1  = 3 
  23 / 8  = 2 1 7 
  13 / 11 = 1 5 2 
  22 / 7  = 3 7 
-151 / 77 = -1 -1 -24 -1 -2 

Sqrt(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 

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

m4

Being able to do such things in m4, without much trouble, makes it very useful as a program-source preprocessor. There may be better macroprocessors, but having some version of m4 is standard for POSIX platforms.

divert(-1)

# m4 is a recursive macro language with eager evaluation.  Generally
# there is no tail-call optimization. I shall define r2cf in a natural
# way, rather than try to mimic call-by-reference or lazy evaluation.

define(`r2cf',`$1/$2 => [_$0($1,$2,`')]')
define(`_r2cf',
  `ifelse(eval($2 != 0),1,
    `$3eval($1 / $2)$0($2,eval($1 % $2),ifelse($3,,`; ',```,'' '))')')

divert`'dnl
dnl
r2cf(1, 2)
r2cf(3, 1)
r2cf(23, 8)
r2cf(13, 11)
r2cf(22, 7)
r2cf(-151, 77)
dnl
r2cf(14142, 10000)
r2cf(141421, 100000)
r2cf(1414214, 1000000)
r2cf(14142136, 10000000)
dnl
r2cf(31, 10)
r2cf(314, 100)
r2cf(3142, 1000)
r2cf(31428, 10000)
r2cf(314285, 100000)
r2cf(3142857, 1000000)
r2cf(31428571, 10000000)
r2cf(314285714, 100000000)
Output:
$ m4 continued-fraction-from-rational.m4
1/2 => [0; 2]
3/1 => [3]
23/8 => [2; 1, 7]
13/11 => [1; 5, 2]
22/7 => [3; 7]
-151/77 => [-1; -1, -24, -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]

Make

GNU Make and POSIX shell

The r2cf GNU Make function both computes and prints the digits, one by one, via a POSIX shell loop.

.SILENT:
.DEFAULT_GOAL := start-here

define r2cf =
	M=`expr $(1)`; \
	N=`expr $(2)`; \
	printf '%d/%d => ' $$M $$N; \
	SEP='['; \
	while test $$N -ne 0; do \
		printf "%s%d" "$$SEP" `expr $$M '/' $$N`; \
		if test "$$SEP" = '['; then SEP='; '; else SEP=', '; fi; \
		R=`expr $$M '%' $$N`; \
		M=$$N; \
		N=$$R; \
	done; \
	printf ']\n'
endef

start-here:
	$(call r2cf, 1, 2)
	$(call r2cf, 3, 1)
	$(call r2cf, 23, 8)
	$(call r2cf, 13, 11)
	$(call r2cf, 22, 7)
	$(call r2cf, -151, 77)

	$(call r2cf, 14142, 10000)
	$(call r2cf, 141421, 100000)
	$(call r2cf, 1414214, 1000000)
	$(call r2cf, 14142136, 10000000)

	$(call r2cf, 31, 10)
	$(call r2cf, 314, 100)
	$(call r2cf, 3142, 1000)
	$(call r2cf, 31428, 10000)
	$(call r2cf, 314285, 100000)
	$(call r2cf, 3142857, 1000000)
	$(call r2cf, 31428571, 10000000)
	$(call r2cf, 314285714, 100000000)
Output:
$ make -f continued-fraction-from-rational.mk
1/2 => [0; 2]
3/1 => [3]
23/8 => [2; 1, 7]
13/11 => [1; 5, 2]
22/7 => [3; 7]
-151/77 => [-1; -1, -24, -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]

Mathematica / Wolfram Language

Mathematica has a build-in function ContinuedFraction.

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]
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}

Mercury

A "straightforward" implementation

Works with: Mercury version 22.01.1
%%%-------------------------------------------------------------------

:- module continued_fraction_from_rational.

:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.

:- implementation.
:- import_module int.
:- import_module list.
:- import_module string.

%%%-------------------------------------------------------------------
%%%
%%% ‘r2cf’ is a predicate, not a function. If it succeeds, it
%%% calculates not only the next digit, but the next starting
%%% fraction. If it fails, we are done.
%%%

:- pred r2cf(int::in, int::out, int::in, int::out, int::out)
   is semidet.
r2cf(!N1, !N2, Digit) :-
  (Dividend = !.N1),
  (Divisor = !.N2),
  (Divisor \= 0),                 % Fail if we have reached the end.
  (!:N1 = Divisor),               % The next Dividend.
  (!:N2 = Dividend mod Divisor),  % Floor division. The next divisor.
  (Digit = Dividend div Divisor). % Floor division. The next digit.

%%%-------------------------------------------------------------------
%%%
%%% ‘r2cf_digits’ takes numerator and denominator of a rational
%%% number, and returns a list of continued fraction digits.
%%%

:- func r2cf_digits(int, int) = list(int).
:- pred r2cf_digits_loop(int::in, int::in,
                         list(int)::in, list(int)::out) is det.
r2cf_digits(N1, N2) = Digit_list :-
  r2cf_digits_loop(N1, N2, [], Digit_list).
r2cf_digits_loop(N1, N2, !Digit_list) :-
   (if r2cf(N1, N1_next, N2, N2_next, Digit)
    then r2cf_digits_loop(N1_next, N2_next,
                          [Digit | !.Digit_list],
                          !:Digit_list)
    else (!:Digit_list = reverse(!.Digit_list))).

%%%-------------------------------------------------------------------
%%%
%%% ‘print_cf’ prints a continued fraction nicely.
%%%

:- pred print_cf(list(int)::in, io::di, io::uo) is det.
:- pred print_cf_loop(list(int)::in, string::in, io::di, io::uo)
   is det.
print_cf(Digit_list, !IO) :-
  print_cf_loop(Digit_list, "[", !IO).
print_cf_loop(Digit_list, Sep, !IO) :-
  (if (Digit_list = [Digit | More_digits])
   then (print(Sep, !IO),
         print(Digit, !IO),
         (if (Sep = "[")
          then print_cf_loop(More_digits, "; ", !IO)
          else print_cf_loop(More_digits, ", ", !IO)))
   else print("]", !IO)).

%%%-------------------------------------------------------------------
%%%
%%% ‘example’ takes numerator and denominator of a rational number,
%%% and prints a line of output.
%%%

:- pred example(int::in, int::in, io::di, io::uo) is det.
example(N1, N2, !IO) :-
  print(N1, !IO),
  print("/", !IO),
  print(N2, !IO),
  print(" => ", !IO),
  print_cf(r2cf_digits(N1, N2), !IO),
  nl(!IO).

%%%-------------------------------------------------------------------

main(!IO) :-
  example(1, 2, !IO),
  example(3, 1, !IO),
  example(23, 8, !IO),
  example(13, 11, !IO),
  example(22, 7, !IO),
  example(-151, 77, !IO),
  example(14142, 10000, !IO),
  example(141421, 100000, !IO),
  example(1414214, 1000000, !IO),
  example(14142136, 10000000, !IO),
  example(31, 10, !IO),
  example(314, 100, !IO),
  example(3142, 1000, !IO),
  example(31428, 10000, !IO),
  example(314285, 100000, !IO),
  example(3142857, 1000000, !IO),
  example(31428571, 10000000, !IO),
  example(314285714, 100000000, !IO),
  true.

%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
Output:
$ mmc continued_fraction_from_rational.m && ./continued_fraction_from_rational
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]

An implementation using lazy lists

Translation of: Haskell
Works with: Mercury version 22.01.1

This version has the advantage that it memoizes terms in a form that is efficient for sequential access.

I used arbitrary-precision numbers so I could plug in some big numbers.

Important: in Mercury, delay takes an explicit thunk (not an expression implicitly wrapped in a thunk) as its argument. If you use val instead of delay, you will get eager evaluation.

%%%-------------------------------------------------------------------

:- module continued_fraction_from_rational_lazy.

:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.

:- implementation.
:- import_module exception.
:- import_module integer.       % Arbitrary-precision integers.
:- import_module lazy.          % Lazy evaluation.
:- import_module list.
:- import_module string.

%% NOTE: There IS a "rational" module, for arbitrary-precision
%% rational numbers, but I wrote this example for plain "integer"
%% type. One could easily add "rational" support.

%%%-------------------------------------------------------------------
%%%
%%% The following lazy list implementation is suggested in the Mercury
%%% Library Reference.
%%%

:- type lazy_list(T)
   ---> lazy_list(lazy(list_cell(T))).

:- type list_cell(T)
   ---> cons(T, lazy_list(T))
   ;    nil.

:- type cf == lazy_list(integer).

%%%-------------------------------------------------------------------
%%%
%%% r2cf takes numerator and denominator of a fraction, and returns a
%%% continued fraction as a lazy list of terms.
%%%

:- func r2cf(integer, integer) = cf.
r2cf(Numerator, Denominator) = CF :-
  (if (Denominator = zero)
   then (CF = lazy_list(delay((func) = nil)))
   else (CF = lazy_list(delay(Cons)),
         ((func) = Cell :-
            (Cell = cons(Quotient, r2cf(Denominator, Remainder)),
             %% What follows is division with truncation towards zero.
             divide_with_rem(Numerator, Denominator,
                             Quotient, Remainder))) = Cons)).

%%%-------------------------------------------------------------------
%%%
%%% cf2string and cf2string_with_max_terms convert a continued
%%% fraction to a printable string.
%%%

:- func cf2string(cf) = string.
cf2string(CF) = cf2string_with_max_terms(CF, integer(1000)).

:- func cf2string_with_max_terms(cf, integer) = string.
cf2string_with_max_terms(CF, MaxTerms) = S :-
  S = cf2string_loop(CF, MaxTerms, zero, "[").

:- func cf2string_loop(cf, integer, integer, string) = string.
cf2string_loop(CF, MaxTerms, I, Accum) = S :-
  (CF = lazy_list(ValCell),
   force(ValCell) = Cell,
   (if (Cell = cons(Term, Tail))
    then (if (I = MaxTerms) then (S = Accum ++ ",...]")
          else ((Separator = (if (I = zero) then ""
                              else if (I = one) then ";"
                              else ",")),
                TermStr = to_string(Term),
                S = cf2string_loop(Tail, MaxTerms, I + one,
                                   Accum ++ Separator ++ TermStr)))
    else (S = Accum ++ "]"))).

%%%-------------------------------------------------------------------
%%%
%%% example takes a fraction, as a string, or as separate numerator
%%% and denominator strings, and prints a line of output.
%%%

:- pred example(string::in, io::di, io::uo) is det.
:- pred example(string::in, string::in, io::di, io::uo) is det.
example(Fraction, !IO) :-
  split_at_char(('/'), Fraction) = Split,
  (if (Split = [Numerator])
   then example_(Fraction, Numerator, "1", !IO)
   else if (Split = [Numerator, Denominator])
   then example_(Fraction, Numerator, Denominator, !IO)
   else throw("Not an integer or fraction: \"" ++ Fraction ++ "\"")).
example(Numerator, Denominator, !IO) :-
  example_(Numerator ++ "/" ++ Denominator,
           Numerator, Denominator, !IO).

:- pred example_(string::in, string::in, string::in, io::di, io::uo)
   is det.
example_(Fraction, Numerator, Denominator, !IO) :-
  (N = integer.det_from_string(Numerator)),
  (D = integer.det_from_string(Denominator)),
  print(Fraction, !IO),
  print(" => ", !IO),
  print(cf2string(r2cf(N, D)), !IO),
  nl(!IO).

%%%-------------------------------------------------------------------

main(!IO) :-
  example("1/2", !IO),
  example("3", !IO),
  example("23/8", !IO),
  example("13/11", !IO),
  example("22/7", !IO),
  example("-151/77", !IO),

  %% I made "example" overloaded, so it can take separate numerator
  %% and denominator strings.
  example("151", "-77", !IO),

  example("14142/10000", !IO),
  example("141421/100000", !IO),
  example("1414214/1000000", !IO),
  example("14142136/10000000", !IO),

  %% Decimal expansion of sqrt(2): see https://oeis.org/A002193
  example("141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", !IO),

  example("31/10", !IO),
  example("314/100", !IO),
  example("3142/1000", !IO),
  example("31428/10000", !IO),
  example("314285/100000", !IO),
  example("3142857/1000000", !IO),
  example("31428571/10000000", !IO),
  example("314285714/100000000", !IO),

  %% Decimal expansion of pi: see https://oeis.org/A000796
  example("314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", !IO),

  true.

%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
Output:
$ mmc --use-subdirs continued_fraction_from_rational_lazy.m && ./continued_fraction_from_rational_lazy
1/2 => [0;2]
3 => [3]
23/8 => [2;1,7]
13/11 => [1;5,2]
22/7 => [3;7]
-151/77 => [-1;-1,-24,-1,-2]
151/-77 => [-1;-1,-24,-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]
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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,5,1,8,3,1,2,2,1,6,2,2,3,1,2,3,1,1,39,1,3,1,2,4,10,1,6,1,30,5,2,1,1,1,1,1,32,1,4,18,124,3,2,1,1,8,1,1,1,6,15,2,3,2,7,1,4,9,2,7,1,1,1,1,1,2,1,10,1,31,5,1,1,1,7,1,14,10,3,11,1,2,1,65,4,9,2,3,2,2,9,1,1,2,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]
314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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,8,2,1,4,1,1,2,3,6,8,1,1,1,7,1,1,1,1,21,1,2,1,2,1,1,21,1,6,1,2,2,1,1,2,5,2,3,2,9,3,3,2,2,1,1,3,7,3,1,8,36,20,6,17,15,1,2,5,1,4,9,6,26,1,1,1,7,1,79,4,1,1,10,4,5,1,1,55,8,1,4,4,10,5,3,1,2,6,1,2,1,1,2,1,20,3,1,1,2,3]

Modula-2

MODULE ConstructFromrationalNumber;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

TYPE R2cf = RECORD
    num,den : INTEGER;
END;

PROCEDURE HasNext(self : R2cf) : BOOLEAN;
BEGIN
    RETURN self.den # 0;
END HasNext;

PROCEDURE Next(VAR self : R2cf) : INTEGER;
VAR div,rem : INTEGER;
BEGIN
    div := self.num / self.den;
    rem := self.num REM self.den;
    self.num := self.den;
    self.den := rem;
    RETURN div;
END Next;

PROCEDURE Iterate(self : R2cf);
VAR buf : ARRAY[0..64] OF CHAR;
BEGIN
    WHILE HasNext(self) DO
        FormatString("%i ", buf, Next(self));
        WriteString(buf);
    END;
    WriteLn;
END Iterate;

PROCEDURE Print(num,den : INTEGER);
VAR frac : R2cf;
VAR buf : ARRAY[0..64] OF CHAR;
BEGIN
    FormatString("%9i / %-9i = ", buf, num, den);
    WriteString(buf);

    frac.num := num;
    frac.den := den;
    Iterate(frac);
END Print;

VAR frac : R2cf;
BEGIN
    Print(1,2);
    Print(3,1);
    Print(23,8);
    Print(13,11);
    Print(22,7);
    Print(-151,77);

    WriteLn;
    WriteString("Sqrt(2) ->");
    WriteLn;
    Print(14142,10000);
    Print(141421,100000);
    Print(1414214,1000000);
    Print(14142136,10000000);

    WriteLn;
    WriteString("Pi ->");
    WriteLn;
    Print(31,10);
    Print(314,100);
    Print(3142,1000);
    Print(31428,10000);
    Print(314285,100000);
    Print(3142857,1000000);
    Print(31428571,10000000);
    Print(314285714,100000000);

    ReadChar;
END ConstructFromrationalNumber.

Nim

iterator r2cf*(n1, n2: int): int =
  var (n1, n2) = (n1, n2)
  while n2 != 0:
    yield n1 div n2
    n1 = n1 mod n2
    swap n1, n2

#———————————————————————————————————————————————————————————————————————————————————————————————————

when isMainModule:

  from sequtils import toSeq

  for pair in [(1, 2), (3, 1), (23, 8), (13, 11), (22, 7), (-151, 77)]:
    echo pair, " -> ", toSeq(r2cf(pair[0], pair[1]))

  echo ""
  for pair in [(14142, 10000), (141421, 100000), (1414214, 1000000), (14142136, 10000000)]:
    echo pair, " -> ", toSeq(r2cf(pair[0], pair[1]))

  echo ""
  for pair in [(31,10), (314,100), (3142,1000), (31428,10000), (314285,100000),
              (3142857,1000000), (31428571,10000000), (314285714,100000000)]:
    echo pair, " -> ", toSeq(r2cf(pair[0], pair[1]))
Output:
(1, 2) -> @[0, 2]
(3, 1) -> @[3]
(23, 8) -> @[2, 1, 7]
(13, 11) -> @[1, 5, 2]
(22, 7) -> @[3, 7]
(-151, 77) -> @[-1, -1, -24, -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]

PARI/GP

apply(contfrac,[1/2,3,23/8,13/11,22/7,-151/77])
Output:
[[0, 2], [3], [2, 1, 7], [1, 5, 2], [3, 7], [-2, 25, 1, 2]]

PascalABC.NET

Translation of: Nim
function r2cf(n1, n2: integer): sequence of integer;
begin
  while n2 <> 0 do
  begin
    yield n1 div n2;
    n1 := n1 mod n2;
    swap(n1, n2);
  end;
end;

begin
  foreach var pair in |(1, 2), (3, 1), (23, 8), (13, 11), (22, 7), (-151, 77)| do
    println(pair, ' -> ', r2cf(pair[0], pair[1]));
  
  println;
  foreach var pair in |(14142, 10000), (141421, 100000), (1414214, 1000000), (14142136, 10000000)| do
    println(pair, ' -> ', r2cf(pair[0], pair[1]));
  
  println;
  foreach var pair in |(31, 10), (314, 100), (3142, 1000), (31428, 10000), (314285, 100000),
  (3142857, 1000000), (31428571, 10000000), (314285714, 100000000)| do
    println(pair, ' -> ', r2cf(pair[0], pair[1]));
end.
Output:
(1,2)  ->  [0,2]
(3,1)  ->  [3]
(23,8)  ->  [2,1,7]
(13,11)  ->  [1,5,2]
(22,7)  ->  [3,7]
(-151,77)  ->  [-1,-1,-24,-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]

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.

$|=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));
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]

Phix

with javascript_semantics
function r2cf(atom num, denom)
    atom quot = 0
    if denom!=0 then
        quot = trunc(num/denom)
        {num,denom} = {denom,num-quot*denom}
    end if
    return {quot,{num,denom}}
end function
 
procedure test(string txt, sequence tests)
    printf(1,"Running %s :\n",{txt})
    for i=1 to length(tests) do
        atom {num,denom} = tests[i], quot
        string sep = ";"
        printf(1,"%d/%d ==> [",{num,denom})
        while denom!=0 do
            {quot,{num,denom}} = r2cf(num,denom)
            printf(1,"%d",quot)
            if denom=0 then exit end if
            printf(1,"%s",sep)
            sep = ","
        end while
        printf(1,"]\n")
    end for
    printf(1,"\n")
end procedure
 
constant examples = {{1,2}, {3,1}, {23,8}, {13,11}, {22,7}, {-151,77}},
         sqrt2 = {{14142,10000}, {141421,100000}, {1414214,1000000}, {14142136,10000000}},
         pi = {{31,10}, {314,100}, {3142,1000}, {31428,10000}, {314285,100000}, {3142857,1000000}, 
               {31428571,10000000}, {314285714,100000000}, {3141592653589793,1000000000000000}}
 
test("the examples",examples)
test("for sqrt(2)",sqrt2)
test("for pi",pi)
Output:
Running the examples :
1/2 ==> [0;2]
3/1 ==> [3]
23/8 ==> [2;1,7]
13/11 ==> [1;5,2]
22/7 ==> [3;7]
-151/77 ==> [-1;-1,-24,-1,-2]

Running for sqrt(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]

Running for pi :
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]

Python

Translation of: Ruby
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]

This version generates it from any real number (with rationals as a special case):

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]

Quackery

  [ $ "bigrat.qky" loadfile ] now!

  [ [] unrot
    [ proper
      2swap join unrot
      over 0 != while
      1/v again ]
    2drop ]            is cf ( n/d --> [ )

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

  witheach
    [ do over echo say "/"
      dup echo
      say " = "
      cf echo cr ]
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 ]

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

Raku

(formerly Perl 6) Straightforward implementation:

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>;
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:

sub r2cf(Rat $x is copy) { gather $x [R/]= 1 while ($x -= take $x.floor) > 0 }

RATFOR

Works with: ratfor77 version public domain 1.0
Works with: gfortran version 12.2.1

To get nice output with f2c would have been more tedious than I felt like doing, and so the I/O facilities employed here are more advanced than often was the case with an historical FORTRAN77 compiler.

# This implementation assumes the I/O facilities of gfortran, and so
# is not suited to f2c as the FORTRAN77 compiler.

function r2cf (N1, N2)
  implicit none

  integer N1, N2
  integer r2cf

  integer r

  # We will use division with rounding towards zero, which is the
  # native integer division method of FORTRAN77.
  r2cf = N1 / N2
  r = mod (N1, N2)

  N1 = N2
  N2 = r
end

subroutine wrr2cf (N1, N2)      # Write r2cf results.
  implicit none

  integer N1, N2
  integer r2cf
  integer digit, M1, M2
  integer sep

  write (*, '(I0, "/", I0, " => ")', advance = "no") N1, N2

  M1 = N1
  M2 = N2
  sep = 0
  while (M2 != 0)
    {
      digit = r2cf (M1, M2)
      if (sep == 0)
        {
          write (*, '("[", I0)', advance = "no") digit
          sep = 1
        }
      else if (sep == 1)
        {
          write (*, '("; ", I0)', advance = "no") digit
          sep = 2
        }
      else
        {
          write (*, '(", ", I0)', advance = "no") digit
        }
    }
    write (*, '("]")', advance = "yes")
end

program demo
  implicit none

  call wrr2cf (1, 2)
  call wrr2cf (3, 1)
  call wrr2cf (23, 8)
  call wrr2cf (13, 11)
  call wrr2cf (22, 7)
  call wrr2cf (-151, 77)

  call wrr2cf (14142, 10000)
  call wrr2cf (141421, 100000)
  call wrr2cf (1414214, 1000000)
  call wrr2cf (14142136, 10000000)

  call wrr2cf (31, 10)
  call wrr2cf (314, 100)
  call wrr2cf (3142, 1000)
  call wrr2cf (31428, 10000)
  call wrr2cf (314285, 100000)
  call wrr2cf (3142857, 1000000)
  call wrr2cf (31428571, 10000000)
  call wrr2cf (314285714, 100000000)
end
Output:
$ (ratfor77 continued-fraction-from-rational.r | gfortran -x f77 -) && ./a.out
1/2 => [0; 2]
3/1 => [3]
23/8 => [2; 1, 7]
13/11 => [1; 5, 2]
22/7 => [3; 7]
-151/77 => [-1; -1, -24, -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]

REXX

Programming notes:

  •   Increasing   numeric digits   to a higher value will generate more terms.
  •   Two subroutines,   sqrt   and   pi,   were included here to demonstrate terms for   √ 2   and   pi.
  •   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 REXX version also handles negative numbers.
/*REXX program converts a  decimal  or  rational fraction  to a  continued fraction.    */
numeric digits 230                               /*determines how many terms to be gened*/
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 pi'
say 'pi                 ──► CF: '   r2cf(  pi() )
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
$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
/*──────────────────────────────────────────────────────────────────────────────────────*/
pi: return 3.1415926535897932384626433832795028841971693993751058209749445923078164062862,
           || 089986280348253421170679821480865132823066470938446095505822317253594081284,
           || 811174502841027019385211055596446229489549303819644288109756659334461284756,
           || 48233786783165271                        /* ··· should  ≥  NUMERIC DIGITS */
/*──────────────────────────────────────────────────────────────────────────────────────*/
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
      if d=0                 then call serr  'a denominator is zero'
      n=abs(n)                                         /*ensure numerator is positive.  */
                         do  while  d\==0;      _=d    /*where the rubber meets the road*/
                         $=$  s || (n%d)               /*append another number to list. */
                         d=n // d;              n=_    /* %  is int div,  // is modulus.*/
                         end   /*while*/
      return strip($)
/*──────────────────────────────────────────────────────────────────────────────────────*/
serr: say;    say '***error***';    say;    say arg(1);     say;    exit 13
/*──────────────────────────────────────────────────────────────────────────────────────*/
sqrt: procedure; parse arg x;  if x=0  then return 0;  d=digits();   h=d+6;   numeric form
      m.=9; numeric digits; parse value format(x,2,1,,0) 'E0' with g 'E' _ .; g=g*.5'e'_%2
                     do j=0  while h>9;      m.j=h;               h=h%2+1;       end /*j*/
                     do k=j+5  to 0  by -1;  numeric digits m.k;  g=(g+x/g)*.5;  end /*k*/
      numeric digits d;                      return g/1
output   when using the default (internal) inputs:
              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 pi
pi                 ──► 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

RPL

Half of the code is actually here to extract N1 and N2 from the expression 'N1/N2'. The algorithm itself is within the WHILE..REPEAT..END loop.

Works with: Halcyon Calc version 4.2.7
RPL code Comment
≪ 
  DUP 1 EXGET EVAL SWAP
  IF DUP SIZE 3 < THEN DROP 1
  ELSE DUP SIZE EXGET END
  { } SWAP 
  WHILE DUP REPEAT 
     ROT OVER MOD LAST / FLOOR
     4 ROLL SWAP + SWAP END 
  ROT DROP2 LIST→ →ARRY
≫ ‘RC2F’ STO
RC2F ( 'n1/n2'  - [ a0 a1.. an ] ) 
get numerator
if no denominator, use 1
else get it
prepare stack 3:n1 2:output list 1:n2
loop
   divmod(n1,n2)
   add n1//n2 to list
clean stack, convert data type to have [] instead of {}

Input:
≪ { '1/2' '3' '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' } → fracs
≪ {} 1 fracs SIZE FOR j fracs j GET RC2F + NEXT ≫ ≫ EVAL
Output:
1: { [ 0 2 ]  [ 3 ]  [ 2 1 7 ]  [ 1 5 2 ]  [ 3 7 ]  [ -2 25 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 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 ] }

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

Testing

Test 1:

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

(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
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:

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

Rust

struct R2cf {
    n1: i64,
    n2: i64
}

// This iterator generates the continued fraction representation from the
// specified rational number.
impl Iterator for R2cf {
    type Item = i64;

    fn next(&mut self) -> Option<i64> {
        if self.n2 == 0 {
            None
        }
        else {
            let t1 = self.n1 / self.n2;
            let t2 = self.n2;
            self.n2 = self.n1 - t1 * t2;
            self.n1 = t2;
            Some(t1)
        }
    }
}

fn r2cf(n1: i64, n2: i64) -> R2cf {
    R2cf { n1: n1, n2: n2 }
}

macro_rules! printcf {
    ($x:expr, $y:expr) => (println!("{:?}", r2cf($x, $y).collect::<Vec<_>>()));
}

fn main() {
    printcf!(1, 2);
    printcf!(3, 1);
    printcf!(23, 8);
    printcf!(13, 11);
    printcf!(22, 7);
    printcf!(-152, 77);

    printcf!(14_142, 10_000);
    printcf!(141_421, 100_000);
    printcf!(1_414_214, 1_000_000);
    printcf!(14_142_136, 10_000_000);

    printcf!(31, 10);
    printcf!(314, 100);
    printcf!(3142, 1000);
    printcf!(31_428, 10_000);
    printcf!(314_285, 100_000);
    printcf!(3_142_857, 1_000_000);
    printcf!(31_428_571, 10_000_000);
    printcf!(314_285_714, 100_000_000);
}
Output:
[0, 2]
[3]
[2, 1, 7]
[1, 5, 2]
[3, 7]
[-1, -1, -37, -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, 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]

Scheme

Using a closure to generate terms

Works with: Chez Scheme

The Implementation

; Create a terminating Continued Fraction generator for the given rational number.
; Returns one term per call; returns #f when no more terms remaining.
(define make-continued-fraction-gen
  (lambda (rat)
    (let ((num (numerator rat)) (den (denominator rat)))
      (lambda ()
        (if (= den 0)
          #f
          (let ((ret (quotient num den))
                (rem (modulo num den)))
            (set! num den)
            (set! den rem)
            ret))))))

; Return the continued fraction representation of a rational number as a string.
(define rat->cf-string
  (lambda (rat)
    (let* ((cf (make-continued-fraction-gen rat))
           (str (string-append "[" (format "~a" (cf))))
           (sep ";"))
      (let loop ((term (cf)))
        (when term
          (set! str (string-append str (format "~a ~a" sep term)))
          (set! sep ",")
          (loop (cf))))
      (string-append str "]"))))

; Return the continued fraction representation of a rational number as a list of terms.
(define rat->cf-list
  (lambda (rat)
    (let ((cf (make-continued-fraction-gen rat))
          (lst '()))
      (let loop ((term (cf)))
        (when term
          (set! lst (append lst (list term)))
          (loop (cf))))
      lst)))

The Task
Each continued fraction is displayed in both the conventional written form and as a list of terms.

(printf "~%Basic examples:~%")
(for-each
  (lambda (rat)
    (printf "~a = ~a~%" rat (rat->cf-string rat))
    (printf "~a : ~a~%" rat (rat->cf-list rat)))
  '(1/2 3 23/8 13/11 22/7 -151/77 0))

(printf "~%Root2 approximations:~%")
(for-each
  (lambda (rat)
    (printf "~a = ~a~%" rat (rat->cf-string rat))
    (printf "~a : ~a~%" rat (rat->cf-list rat)))
  '(14142/10000 141421/100000 1414214/1000000 14142136/10000000 141421356237/100000000000))

(printf "~%Pi approximations:~%")
(for-each
  (lambda (rat)
    (printf "~a = ~a~%" rat (rat->cf-string rat))
    (printf "~a : ~a~%" rat (rat->cf-list rat)))
  '(31/10 314/100 3142/1000 31428/10000 314285/100000 3142857/1000000
    31428571/10000000 314285714/100000000 31415926535898/10000000000000))
Output:
Basic examples:
1/2 = [0; 2]
1/2 : (0 2)
3 = [3]
3 : (3)
23/8 = [2; 1, 7]
23/8 : (2 1 7)
13/11 = [1; 5, 2]
13/11 : (1 5 2)
22/7 = [3; 7]
22/7 : (3 7)
-151/77 = [-1; 25, 1, 2]
-151/77 : (-1 25 1 2)
0 = [0]
0 : (0)

Root2 approximations:
7071/5000 = [1; 2, 2, 2, 2, 2, 1, 1, 29]
7071/5000 : (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]
141421/100000 : (1 2 2 2 2 2 2 3 1 1 3 1 7 2)
707107/500000 = [1; 2, 2, 2, 2, 2, 2, 2, 3, 6, 1, 2, 1, 12]
707107/500000 : (1 2 2 2 2 2 2 2 3 6 1 2 1 12)
1767767/1250000 = [1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 1, 2, 4, 1, 1, 2]
1767767/1250000 : (1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2)
141421356237/100000000000 = [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]
141421356237/100000000000 : (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)

Pi approximations:
31/10 = [3; 10]
31/10 : (3 10)
157/50 = [3; 7, 7]
157/50 : (3 7 7)
1571/500 = [3; 7, 23, 1, 2]
1571/500 : (3 7 23 1 2)
7857/2500 = [3; 7, 357]
7857/2500 : (3 7 357)
62857/20000 = [3; 7, 2857]
62857/20000 : (3 7 2857)
3142857/1000000 = [3; 7, 142857]
3142857/1000000 : (3 7 142857)
31428571/10000000 = [3; 7, 476190, 3]
31428571/10000000 : (3 7 476190 3)
157142857/50000000 = [3; 7, 7142857]
157142857/50000000 : (3 7 7142857)
15707963267949/5000000000000 = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 21, 17, 1, 1, 1, 1, 8, 1, 7, 2, 1, 2, 2]
15707963267949/5000000000000 : (3 7 15 1 292 1 1 1 2 1 3 1 21 17 1 1 1 1 8 1 7 2 1 2 2)

Using SRFI-41 streams (lazy lists)

Translation of: Haskell
Works with: Gauche Scheme version 0.9.12
Works with: Chibi Scheme version 0.10.0
Works with: CHICKEN Scheme version 5.3.0

This is for R7RS Scheme. Modify as necessary, for your Scheme. For CHICKEN, you will need the r7rs and srfi-41 eggs.

Due to the use of a lazy list, the terms are memoized in a manner suitable for sequential access again and again.

(For -151/77 the solution here is for floor division. You will get a different solution if you round the fraction differently.)

(cond-expand
  (r7rs)
  (chicken (import (r7rs))))

(import (scheme base))
(import (scheme case-lambda))
(import (scheme write))
(import (srfi 41))

;;;-------------------------------------------------------------------

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; The entirety of r2cf, two different ways ;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; r2cf-VERSION1 works with integers. (Any floating-point number is
;; first converted to exact rational.)
(define (r2cf-VERSION1 fraction)
  (define-stream (recurs n d)
    (if (zero? d)
        stream-null
        (let-values (((q r) (floor/ n d)))
          (stream-cons q (recurs d r)))))
  (let ((fraction (exact fraction)))
    (recurs (numerator fraction) (denominator fraction))))

;; r2cf-VERSION2 works directly with fractions. (Any floating-point
;; number is first converted to exact rational.)
(define (r2cf-VERSION2 fraction)
  (define-stream (recurs fraction)
    (let* ((quotient (floor fraction))
           (remainder (- fraction quotient)))
      (stream-cons quotient (if (zero? remainder)
                                stream-null
                                (recurs (/ remainder))))))
  (recurs (exact fraction)))

;;(define r2cf r2cf-VERSION1)
(define r2cf r2cf-VERSION2)

;;;-------------------------------------------------------------------

(define *max-terms* (make-parameter 20))

(define cf2string
  (case-lambda
    ((cf) (cf2string cf (*max-terms*)))
    ((cf max-terms)
     (let loop ((i 0)
                (s "[")
                (strm cf))
       (if (stream-null? strm)
           (string-append s "]")
           (let ((term (stream-car strm))
                 (tail (stream-cdr strm)))
             (if (= i max-terms)
                 (string-append s ",...]")
                 (let ((separator (case i
                                    ((0) "")
                                    ((1) ";")
                                    (else ",")))
                       (term-str (number->string term)))
                   (loop (+ i 1)
                         (string-append s separator term-str)
                         tail)))))))))

(define (show fraction)
  (parameterize ((*max-terms* 1000))
    (display fraction)
    (display " => ")
    (display (cf2string (r2cf fraction)))
    (newline)))

(show 1/2)
(show 3)
(show 23/8)
(show 13/11)
(show 22/11)
(show -151/77)
(show 14142/10000)
(show 141421/100000)
(show 1414214/1000000)
(show 14142136/10000000)
(show 1414213562373095049/1000000000000000000)

;; Decimal expansion of sqrt(2): see https://oeis.org/A002193
(show 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

(show 31/10)
(show 314/100)
(show 3142/1000)
(show 31428/10000)
(show 314285/100000)
(show 3142857/1000000)
(show 31428571/10000000)
(show 314285714/100000000)
(show 3142857142857143/1000000000000000)

;; Decimal expansion of pi: see https://oeis.org/A000796
(show 314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
Output:
$ gosh continued-fraction-from-rational-srfi41.scm
1/2 => [0;2]
3 => [3]
23/8 => [2;1,7]
13/11 => [1;5,2]
2 => [2]
-151/77 => [-2;25,1,2]
7071/5000 => [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]
707107/500000 => [1;2,2,2,2,2,2,2,3,6,1,2,1,12]
1767767/1250000 => [1;2,2,2,2,2,2,2,2,2,6,1,2,4,1,1,2]
1414213562373095049/1000000000000000000 => [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,1,39,1,5,1,3,61,1,1,8,1,2,1,7,1,1,6]
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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,5,1,8,3,1,2,2,1,6,2,2,3,1,2,3,1,1,39,1,3,1,2,4,10,1,6,1,30,5,2,1,1,1,1,1,32,1,4,18,124,3,2,1,1,8,1,1,1,6,15,2,3,2,7,1,4,9,2,7,1,1,1,1,1,2,1,10,1,31,5,1,1,1,7,1,14,10,3,11,1,2,1,65,4,9,2,3,2,2,9,1,1,2,1,1,2]
31/10 => [3;10]
157/50 => [3;7,7]
1571/500 => [3;7,23,1,2]
7857/2500 => [3;7,357]
62857/20000 => [3;7,2857]
3142857/1000000 => [3;7,142857]
31428571/10000000 => [3;7,476190,3]
157142857/50000000 => [3;7,7142857]
3142857142857143/1000000000000000 => [3;6,1,142857142857142]
157079632679489661923132169163975144209858469968755291048747229615390820314310449931401741267105853399107/50000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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,8,2,1,4,1,1,2,3,6,8,1,1,1,7,1,1,1,1,21,1,2,1,2,1,1,21,1,6,1,2,2,1,1,2,5,2,3,2,9,3,3,2,2,1,1,3,7,3,1,8,36,20,6,17,15,1,2,5,1,4,9,6,26,1,1,1,7,1,79,4,1,1,10,4,5,1,1,55,8,1,4,4,10,5,3,1,2,6,1,2,1,1,2,1,20,3,1,1,2,3]

Using call-with-current-continuation to implement coroutines

Works with: Gauche Scheme version 0.9.12
Works with: Chibi Scheme version 0.10.0
Works with: CHICKEN Scheme version 5.3.0

This is for R7RS Scheme. Modify as necessary, for your Scheme. For CHICKEN, you will need the r7rs egg.

This implementation employs coroutines. The r2cf procedure is passed not only a number to convert to a continued fraction, but also a "consumer" of the terms. In this case, the consumer is display-cf, which prints the terms nicely.

The implementation here is, in a way, backwards from the requirements of the task: the producer is going first, so that the consumer does not have to "ask for" the first term. But I had not thought of that before writing the code, and also every term after the first can be thought of as "asked for".

(For -151/77 the solution here is for floor division. You will get a different solution if you round the fraction differently.)

(cond-expand
  (r7rs)
  (chicken (import (r7rs))))

(import (scheme base))
(import (scheme write))

;;;-------------------------------------------------------------------

(define (r2cf fraction consumer)
  (let* ((fraction (exact fraction)))
    (let loop ((n (numerator fraction))
               (d (denominator fraction))
               (consumer consumer))
      (if (zero? d)
          (call-with-current-continuation
           (lambda (kont) (consumer #f kont)))
          (let-values (((q r) (floor/ n d)))
            (loop d r (call-with-current-continuation
                       (lambda (kont) (consumer q kont)))))))))

(define (display-cf term producer)
  (display "[")
  (let loop ((term term)
             (producer producer)
             (separator ""))
    (if term
        (begin
          (display separator)
          (display term)
          (let-values (((term producer)
                        (call-with-current-continuation producer)))
            (loop term producer
                  (if (string=? separator "") ";" ","))))
        (begin
          (display "]")
          (call-with-current-continuation producer)))))

;;;-------------------------------------------------------------------

(define (show fraction)
  (display fraction)
  (display " => ")
  (r2cf fraction display-cf)
  (newline))

(show 1/2)
(show 3)
(show 23/8)
(show 13/11)
(show 22/11)
(show -151/77)
(show 14142/10000)
(show 141421/100000)
(show 1414214/1000000)
(show 14142136/10000000)
(show 1414213562373095049/1000000000000000000)

;; Decimal expansion of sqrt(2): see https://oeis.org/A002193
(show 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

(show 31/10)
(show 314/100)
(show 3142/1000)
(show 31428/10000)
(show 314285/100000)
(show 3142857/1000000)
(show 31428571/10000000)
(show 314285714/100000000)
(show 3142857142857143/1000000000000000)

;; Decimal expansion of pi: see https://oeis.org/A000796
(show 314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
Output:
$ gosh continued-fraction-from-rational-callcc.scm
1/2 => [0;2]
3 => [3]
23/8 => [2;1,7]
13/11 => [1;5,2]
2 => [2]
-151/77 => [-2;25,1,2]
7071/5000 => [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]
707107/500000 => [1;2,2,2,2,2,2,2,3,6,1,2,1,12]
1767767/1250000 => [1;2,2,2,2,2,2,2,2,2,6,1,2,4,1,1,2]
1414213562373095049/1000000000000000000 => [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,1,39,1,5,1,3,61,1,1,8,1,2,1,7,1,1,6]
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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,5,1,8,3,1,2,2,1,6,2,2,3,1,2,3,1,1,39,1,3,1,2,4,10,1,6,1,30,5,2,1,1,1,1,1,32,1,4,18,124,3,2,1,1,8,1,1,1,6,15,2,3,2,7,1,4,9,2,7,1,1,1,1,1,2,1,10,1,31,5,1,1,1,7,1,14,10,3,11,1,2,1,65,4,9,2,3,2,2,9,1,1,2,1,1,2]
31/10 => [3;10]
157/50 => [3;7,7]
1571/500 => [3;7,23,1,2]
7857/2500 => [3;7,357]
62857/20000 => [3;7,2857]
3142857/1000000 => [3;7,142857]
31428571/10000000 => [3;7,476190,3]
157142857/50000000 => [3;7,7142857]
3142857142857143/1000000000000000 => [3;6,1,142857142857142]
157079632679489661923132169163975144209858469968755291048747229615390820314310449931401741267105853399107/50000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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,8,2,1,4,1,1,2,3,6,8,1,1,1,7,1,1,1,1,21,1,2,1,2,1,1,21,1,6,1,2,2,1,1,2,5,2,3,2,9,3,3,2,2,1,1,3,7,3,1,8,36,20,6,17,15,1,2,5,1,4,9,6,26,1,1,1,7,1,79,4,1,1,10,4,5,1,1,55,8,1,4,4,10,5,3,1,2,6,1,2,1,1,2,1,20,3,1,1,2,3]

Sidef

Translation of: Perl
func r2cf(num, den) {
    func() {
        den || return nil
        var q = num//den
        (num, den) = (den, num - q*den)
        return q
    }
}

func showcf(f) {
    print "["
    var n = f()
    print "#{n}" if defined(n)
    print "; #{n}" while defined(n = f())
    print "]\n"
}

[
    [1/2, 3/1, 23/8, 13/11, 22/7, -151/77],
    [14142/10000, 141421/100000, 1414214/1000000, 14142136/10000000],
    [314285714/100000000],
].each { |seq|
    seq.each { |r| showcf(r2cf(r.nude)) }
    print "\n"
}
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]

Tcl

Works with: Tcl version 8.6
Translation of: Ruby

Direct translation

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
}

Demonstrating:

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]
}
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

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

Wren

Library: Wren-rat
Library: Wren-fmt
import "./rat" for Rat
import "./fmt" for Fmt

var toContFrac = Fn.new { |r|
    var a = r.num
    var b = r.den
    while (true) {
        Fiber.yield((a/b).truncate)
        var t = a % b
        a = b
        b = t
        if (a == 1) return
    }
}

var groups = [
    [ [1, 2], [3, 1], [23, 8], [13, 11], [22, 7], [-151, 77] ],
    [ [14142, 1e4], [141421, 1e5], [1414214, 1e6], [14142136, 1e7] ],
    [ [31, 10], [314, 100], [3142, 1e3], [31428, 1e4], [314285, 1e5], [3142857, 1e6],
      [31428571, 1e7], [314285714,1e8]]
]

var lengths = [ [4, 2], [8, 8], [9, 9] ]
var headings = [ "Examples ->", "Sqrt(2) ->", "Pi ->" ]
var i = 0
for (group in groups) {
    System.print(headings[i])
    for (pair in group) {
        Fmt.write("$*d / $*d = ", lengths[i][0], pair[0], -lengths[i][1], pair[1])
        var f = Fiber.new(toContFrac)
        var r = Rat.new(pair[0], pair[1])
        while (!f.isDone) {
           var d = f.call(r)
           if (d) System.write("%(d) ")
        }
        System.print()
    }
    System.print()
    i = i + 1
}
Output:
Examples ->
   1 / 2  = 0 2 
   3 / 1  = 3 
  23 / 8  = 2 1 7 
  13 / 11 = 1 5 2 
  22 / 7  = 3 7 
-151 / 77 = -1 -1 -24 -1 -2 

Sqrt(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 

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

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];
]
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

zkl

Two iterators; one light weight, one heavy weight.

Light weight, explicit state:

fcn r2cf(nom,dnom){ // -->Walker (iterator)
   Walker.tweak(fcn(state){
      nom,dnom:=state;
      if(dnom==0) return(Void.Stop);
      n,d:=nom.divr(dnom);
      state.clear(dnom,d);
      n
   }.fp(List(nom,dnom)))  // partial application (light weight closure)
}

Heavy weight, implicit state:

fcn r2cf2(nom,dnom){ // -->Generator (heavy weight Walker)
   Utils.Generator(fcn(nom,dnom){
      while(dnom){
	 n,d:=nom.divr(dnom); nom,dnom=dnom,d;
	 vm.yield(n);
      }
      Void.Stop;
   },nom,dnom)
}

Both of the above return an iterator so they function the same:

foreach nom,dnom in (T(T(1,2), T(3,1), T(23,8), T(13,11), T(22,7), 
	T(14142,10000), T(141421,100000), T(1414214,1000000), 
	T(14142136,10000000))){
   r2cf(nom,dnom).walk(25).println();  // print up to 25 numbers
}
Output:
L(0,2)
L(3)
L(2,1,7)
L(1,5,2)
L(3,7)
L(1,2,2,2,2,2,1,1,29)
L(1,2,2,2,2,2,2,3,1,1,3,1,7,2)
L(1,2,2,2,2,2,2,2,3,6,1,2,1,12)
L(1,2,2,2,2,2,2,2,2,2,6,1,2,4,1,1,2)
Cookies help us deliver our services. By using our services, you agree to our use of cookies.