Rosetta Code

Continued fraction/Arithmetic/Construct from rational number: Difference between revisions

Page Discussion

Continued fraction/Arithmetic/Construct from rational number (view source)

Revision as of 17:11, 20 November 2023

41,079 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Oops!
 
(37 intermediate revisions by 5 users not shown)
Line 293:
=={{header|ATS}}==
 
===Using a non-linear closure===
The task is vague about how the "lazy evaluation" works, and it seems to me a function with side effects suffices. Nevertheless, what I did was write such a function that has side effects, and then wrap that function in a thunk (a closure taking no arguments). One might wish to go farther and produce a lazy stream, but I did not do that.
 
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).
I hope the point is not that one must use lazy evaluation to do this algorithm! That would beg the question of what "lazy evaluation" means. Rather, the point seems to write ''some'' method of producing the digits of the continued fraction. ''This process itself'' will be regarded as the value of the number.
 
A closure is used to generate the next term (or '''None()''') each time it is called. The integer type is mostly arbitrary.
(I have, by the way, long viewed "a real number" as such a process. It does not matter whether or not the process involves continued fractions, as long as it produces an arbitrarily precise rational number.)
 
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).
 
<syntaxhighlight lang="ats">
Line 459 ⟶ 457:
 
{{out}}
<pre> $ 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',
Line 493 ⟶ 491:
</pre>
 
=== Using a non-linear closure and multiple precision numbers ===
{{libheader|ats2-xprelude}}
{{libheader|GMP}}
{{libheader|GNU MPFR}}
 
For this you need the [https://sourceforge.net/p/chemoelectric/ats2-xprelude '''ats2-xprelude'''] package. I start with octuple precision (IEEE binary256) approximations to the square root of 2 and 22/7.
 
Line 507 ⟶ 509:
`pkg-config --cflags ats2-xprelude` -O2 -std=gnu2x \
continued-fraction-from-rational-2.dats \
`pkg-config --libs ats2-xprelude` -lgc -lm && ./a.out
 
*)
Line 626 ⟶ 628:
 
{{out}}
<pre> $ 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]
Line 637 ⟶ 639:
Octuple precision 22/7:
86764811216795659042036930840054034259385369935856288122043161670619721/27606985387162255149739023449108101809804435888681546220650096895197184 => [3; 7, 3943855055308893592819860492729728829972062269811649460092870985028169]
</pre>
 
===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'''.
 
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
 
#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
 
(*------------------------------------------------------------------*)
</syntaxhighlight>
 
{{out}}
 
<pre>$ 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]</pre>
 
===Using a non-linear lazy list===
{{trans|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.
 
<syntaxhighlight lang="ats">
(* 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;
</syntaxhighlight>
 
{{out}}
<pre>$ 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]</pre>
 
===Using a linear lazy list===
{{trans|Haskell}}
 
This implementation is inspired by the Haskell, although the way in which the integer divisions are done may differ.
 
<syntaxhighlight lang="ats">
(* 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;
</syntaxhighlight>
 
{{out}}
<pre>$ 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]</pre>
 
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
Line 1,135 ⟶ 1,894:
31428571 / 10000000 = 3 7 476190 3
314285714 / 100000000 = 3 7 7142857</pre>
 
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
 
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;
 
 
</syntaxhighlight>
{{out}}
<pre>
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.
 
</pre>
 
 
=={{header|EDSAC order code}}==
Line 1,640 ⟶ 2,522:
31428571/10000000 => [3; 7, 476190, 3]
314285714/100000000 => [3; 7, 7142857]</pre>
 
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|Go}}==
Line 2,568 ⟶ 3,359:
 
=={{header|Mercury}}==
===A "straightforward" implementation===
{{works with|Mercury|22.01.1}}
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------
Line 2,701 ⟶ 3,493:
31428571/10000000 => [3; 7, 476190, 3]
314285714/100000000 => [3; 7, 7142857]</pre>
 
===An implementation using lazy lists===
{{trans|Haskell}}
{{works with|Mercury|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.
 
<syntaxhighlight lang="mercury">
%%%-------------------------------------------------------------------
 
:- 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:
</syntaxhighlight>
 
{{out}}
<pre>$ 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]</pre>
 
=={{header|Modula-2}}==
Line 3,289 ⟶ 4,266:
───────── 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
</pre>
 
=={{header|RPL}}==
Half of the code is actually here to extract N1 and N2 from the expression 'N1/N2'. The algorithm itself is within the <code>WHILE..REPEAT..END</code> loop.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! 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 {}
|}
{{in}}
<pre>
≪ { '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
</pre>
{{out}}
<pre>
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 ] }
</pre>
 
Line 3,439 ⟶ 4,456:
</pre>
=={{header|Scheme}}==
===Using a closure to generate terms===
{{works with|Chez Scheme}}
'''The Implementation'''
Line 3,551 ⟶ 4,569:
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)
</pre>
 
===Using SRFI-41 streams (lazy lists)===
{{trans|Haskell}}
{{works with|Gauche Scheme|0.9.12}}
{{works with|Chibi Scheme|0.10.0}}
{{works with|CHICKEN Scheme|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.)
 
<syntaxhighlight lang="scheme">
(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)
</syntaxhighlight>
 
{{out}}
<pre>$ 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]</pre>
 
===Using ''call-with-current-continuation'' to implement coroutines===
{{works with|Gauche Scheme|0.9.12}}
{{works with|Chibi Scheme|0.10.0}}
{{works with|CHICKEN Scheme|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.)
 
<syntaxhighlight lang="scheme">
(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)
</syntaxhighlight>
 
{{out}}
<pre>$ 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]
</pre>
 
Line 3,812 ⟶ 5,085:
{{libheader|Wren-rat}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./rat" for Rat
import "./fmt" for Fmt
 
var toContFrac = Fn.new { |r|
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/337130...351926"