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

23,524 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Oops!
m (FreeBasic moved to the BASIC section.)
 
(21 intermediate revisions by 4 users not shown)
Line 492:
 
=== 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 505 ⟶ 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 1,161 ⟶ 1,165:
 
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. *)
This may not be a bad idea with non-linear streams, either. *)
extern fn {tk : tkind}
cf_vt2strptr : cf_vt tk -> Strptr1
Line 1,892 ⟶ 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 3,234 ⟶ 3,359:
 
=={{header|Mercury}}==
===A "straightforward" implementation===
{{works with|Mercury|22.01.1}}
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------
Line 3,367 ⟶ 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,955 ⟶ 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 4,105 ⟶ 4,456:
</pre>
=={{header|Scheme}}==
===Using a closure to generate terms===
{{works with|Chez Scheme}}
'''The Implementation'''
Line 4,217 ⟶ 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 4,478 ⟶ 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/337760...351926"