Rosetta Code

Continued fraction/Arithmetic/G(matrix ng, continued fraction n): Difference between revisions

Page Discussion

Continued fraction/Arithmetic/G(matrix ng, continued fraction n) (view source)

Revision as of 17:16, 20 November 2023

27,118 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(11 intermediate revisions by 2 users not shown)
Line 1,831:
{{out}}
[[File:Univariate-continued-fraction-task-no-gc.dats.png|alt=The output of the program.]]
 
===Using lazy non-linear types===
{{trans|Haskell}}
{{trans|Mercury}}
 
This method is simple, and it memoizes terms. However, the memoization is in a linked list rather than a randomly accessible array.
 
The '''recurs''' routines do not execute recursions, but instead (thanks to '''$delay''') create what I will call "recursive thunks". Otherwise the stack would overflow.
 
The code leaks memory, so using a garbage collector may be a good idea.
 
<syntaxhighlight lang="ats">
(*------------------------------------------------------------------*)
 
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
 
(* For convenience (because the prelude provides it), we will use
integer division with truncation towards zero. *)
infixl ( / ) div
infixl ( mod ) rem
macdef div = g0int_div
macdef rem = g0int_mod
 
(*------------------------------------------------------------------*)
(* The definition of a continued fraction, and a few simple ones. *)
 
typedef cf (tk : tkind) = stream (g0int tk)
 
(* A "continued fraction" with no terms. *)
fn {tk : tkind}
cfnil ()
: cf tk =
stream_make_nil<g0int tk> ()
 
(* A continued fraction of one term followed by more terms. *)
fn {tk : tkind}
cfcons (term : g0int tk,
more : cf tk)
: cf tk =
stream_make_cons<g0int tk> (term, more)
 
(* A continued fraction with all terms equal. *)
fn {tk : tkind}
repeat_forever (term : g0int tk)
: cf tk =
let
fun recurs () : stream_con (g0int tk) =
stream_cons (term, $delay recurs ())
in
$delay recurs ()
end
 
(* The square root of two. *)
fn {tk : tkind}
sqrt2 ()
: cf tk =
cfcons<tk> (g0i2i 1, repeat_forever<tk> (g0i2i 2))
 
(*------------------------------------------------------------------*)
(* A continued fraction for a rational number. *)
 
typedef ratnum (tk : tkind) = @(g0int tk, g0int tk)
 
fn {tk : tkind}
r2cf_integers (n : g0int tk,
d : g0int tk)
: cf tk =
let
fun recurs (n : g0int tk,
d : g0int tk)
: cf tk =
if iseqz d then
cfnil<tk> ()
else
cfcons<tk> (n div d, recurs (d, n rem d))
in
recurs (n, d)
end
 
fn {tk : tkind}
r2cf_ratnum (r : ratnum tk)
: cf tk =
r2cf_integers (r.0, r.1)
 
overload r2cf with r2cf_integers
overload r2cf with r2cf_ratnum
 
(*------------------------------------------------------------------*)
(* Application of a homographic function to a continued fraction. *)
 
typedef ng4 (tk : tkind) = @(g0int tk, g0int tk,
g0int tk, g0int tk)
 
fn {tk : tkind}
apply_ng4 (ng4 : ng4 tk,
other_cf : cf tk)
: cf tk =
let
typedef t = g0int tk
 
fun
recurs (a1 : t,
a : t,
b1 : t,
b : t,
other_cf : cf tk)
: stream_con t =
let
fn {}
eject_term (a1 : t,
a : t,
b1 : t,
b : t,
other_cf : cf tk,
term : t)
: stream_con t =
stream_cons (term, $delay recurs (b1, b, a1 - (b1 * term),
a - (b * term), other_cf))
 
fn {}
absorb_term (a1 : t,
a : t,
b1 : t,
b : t,
other_cf : cf tk)
: stream_con t =
case+ !other_cf of
| stream_nil () =>
recurs (a1, a1, b1, b1, other_cf)
| stream_cons (term, rest) =>
recurs (a + (a1 * term), a1, b + (b1 * term), b1, rest)
in
if iseqz b1 && iseqz b then
stream_nil ()
else if iseqz b1 || iseqz b then
absorb_term (a1, a, b1, b, other_cf)
else
let
val q1 = a1 div b1
and q = a div b
in
if q1 = q then
eject_term (a1, a, b1, b, other_cf, q)
else
absorb_term (a1, a, b1, b, other_cf)
end
end
 
val @(a1, a, b1, b) = ng4
in
$delay recurs (a1, a, b1, b, other_cf)
end
 
(*------------------------------------------------------------------*)
(* Some special cases of homographic functions. *)
 
fn {tk : tkind}
integer_add_cf (n : g0int tk,
cf : cf tk)
: cf tk =
apply_ng4 (@(g0i2i 1, n, g0i2i 0, g0i2i 1), cf)
 
fn {tk : tkind}
cf_add_ratnum (cf : cf tk,
r : ratnum tk)
: cf tk =
let
val @(n, d) = r
in
apply_ng4 (@(d, n, g0i2i 0, d), cf)
end
 
fn {tk : tkind}
cf_mul_ratnum (cf : cf tk,
r : ratnum tk)
: cf tk =
let
val @(n, d) = r
in
apply_ng4 (@(n, g0i2i 0, g0i2i 0, d), cf)
end
 
fn {tk : tkind}
cf_div_integer (cf : cf tk,
n : g0int tk)
: cf tk =
apply_ng4 (@(g0i2i 1, g0i2i 0, g0i2i 0, g0i2i n), cf)
 
fn {tk : tkind}
integer_div_cf (n : g0int tk,
cf : cf tk)
: cf tk =
apply_ng4 (@(g0i2i 0, g0i2i n, g0i2i 1, g0i2i 0), cf)
 
overload + with integer_add_cf
overload + with cf_add_ratnum
overload * with cf_mul_ratnum
overload / with cf_div_integer
overload / with integer_div_cf
 
(*------------------------------------------------------------------*)
(* cf2string: convert a continued fraction to a string. *)
 
fn {tk : tkind}
cf2string_max_terms_given
(cf : cf tk,
max_terms : intGte 1)
: string =
let
fun
loop (i : intGte 0,
cf : cf tk,
accum : List0 string)
: List0 string =
case+ !cf of
| stream_nil () => list_cons ("]", accum)
| stream_cons (term, rest) =>
if i = max_terms then
list_cons (",...]", accum)
else
let
val accum =
list_cons
(tostring_val<g0int tk> term,
(case+ i of
| 0 => accum
| 1 => list_cons (";", accum)
| _ => list_cons (",", accum)) : List0 string)
in
loop (succ i, rest, accum)
end
 
val string_lst = list_vt2t (reverse (loop (0, cf, list_sing "[")))
in
strptr2string (stringlst_concat string_lst)
end
 
extern fn {tk : tkind}
cf2string$max_terms :
() -> intGte 1
 
implement {tk} cf2string$max_terms () = 20
 
fn {tk : tkind}
cf2string_max_terms_default
(cf : cf tk)
: string =
cf2string_max_terms_given<tk> (cf, cf2string$max_terms<tk> ())
 
overload cf2string with cf2string_max_terms_given
overload cf2string with cf2string_max_terms_default
 
(*------------------------------------------------------------------*)
 
fn {tk : tkind}
show (expression : string,
cf : cf tk)
: void =
begin
print! expression;
print! " => ";
println! (cf2string<tk> cf);
end
 
implement
main () =
let
val cf_13_11 = r2cf (13, 11)
val cf_22_7 = r2cf (22, 7)
val cf_sqrt2 = sqrt2<intknd> ()
val cf_1_sqrt2 = 1 / cf_sqrt2
in
show ("13/11", cf_13_11);
show ("22/7", cf_22_7);
show ("sqrt(2)", cf_sqrt2);
show ("13/11 + 1/2", cf_13_11 + @(1, 2));
show ("22/7 + 1/2", cf_22_7 + @(1, 2));
show ("(22/7)/4", cf_22_7 * @(1, 4));
show ("1/sqrt(2)", cf_1_sqrt2);
show ("(2 + sqrt(2))/4", apply_ng4 (@(1, 2, 0, 4), cf_sqrt2));
 
(* To show it can be done, write the following without using
results already obtained: *)
show ("(1 + 1/sqrt(2))/2", (1 + 1/sqrt2())/2);
 
0
end
 
(*------------------------------------------------------------------*)
</syntaxhighlight>
 
{{out}}
<pre>$ patscc -g -O2 -std=gnu2x -DATS_MEMALLOC_GCBDW univariate-continued-fraction-task-lazy.dats -lgc && ./a.out
13/11 => [1;5,2]
22/7 => [3;7]
sqrt(2) => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
13/11 + 1/2 => [1;1,2,7]
22/7 + 1/2 => [3;1,1,1,4]
(22/7)/4 => [0;1,3,1,2]
1/sqrt(2) => [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
(2 + sqrt(2))/4 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]
(1 + 1/sqrt(2))/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]</pre>
 
=={{header|C}}==
Line 3,238 ⟶ 3,541:
if (!terminated && m < needed)
{
if (needed <= memo.length < needed)
{
// Increase the space to twice what might be needed
Line 4,293 ⟶ 4,596:
One might note that a lazy list automatically memoizes terms, but not with O(1) access times.
 
The continued fraction generated here for sqrt(2) is actually the continued fraction for a close rational approximation to sqrt(2). I borrowed the definition along with that of '''real2cf'''. The approximation is probably ''not'' what you would want in a practical application, but I thought the definitionimplementation was cool, and I did not feel like being pedantic (until I wrotewriting this commentary). :)
 
<syntaxhighlight lang="haskell">
Line 4,709 ⟶ 5,012:
(+%)/plus1r2times1r2 0 1,999$2
0.853553</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.List;
 
public final class ContinuedFractionArithmeticG1 {
 
public static void main(String[] aArgs) {
List<CFData> cfData = List.of(
new CFData("[1; 5, 2] + 1 / 2 ", new int[] { 2, 1, 0, 2 }, (CFIterator) new R2cfIterator(13, 11) ),
new CFData("[3; 7] + 1 / 2 ", new int[] { 2, 1, 0, 2 }, (CFIterator) new R2cfIterator(22, 7) ),
new CFData("[3; 7] divided by 4 ", new int[] { 1, 0, 0, 4 }, (CFIterator) new R2cfIterator(22, 7) ),
new CFData("sqrt(2) ", new int[] { 0, 1, 1, 0 }, (CFIterator) new ReciprocalRoot2() ),
new CFData("1 / sqrt(2) ", new int[] { 0, 1, 1, 0 }, (CFIterator) new Root2() ),
new CFData("(1 + sqrt(2)) / 2 ", new int[] { 1, 1, 0, 2 }, (CFIterator) new Root2() ),
new CFData("(1 + 1 / sqrt(2)) / 2", new int[] { 1, 1, 0, 2 }, (CFIterator) new ReciprocalRoot2() ) );
for ( CFData data : cfData ) {
System.out.print(data.text + " -> ");
NG ng = new NG(data.arguments);
CFIterator iterator = data.iterator;
int nextTerm = 0;
for ( int i = 1; i <= 20 && iterator.hasNext(); i++ ) {
nextTerm = iterator.next();
if ( ! ng.needsTerm() ) {
System.out.print(ng.egress() + " ");
}
ng.ingress(nextTerm);
}
while ( ! ng.done() ) {
System.out.print(ng.egressDone() + " ");
}
System.out.println();
}
 
}
private static class NG {
public NG(int[] aArgs) {
a1 = aArgs[0]; a = aArgs[1]; b1 = aArgs[2]; b = aArgs[3];
}
 
public void ingress(int aN) {
int temp = a; a = a1; a1 = temp + a1 * aN;
temp = b; b = b1; b1 = temp + b1 * aN;
}
 
public int egress() {
final int n = a / b;
int temp = a; a = b; b = temp - b * n;
temp = a1; a1 = b1; b1 = temp - b1 * n;
return n;
}
 
public boolean needsTerm() {
return ( b == 0 || b1 == 0 ) || ( a * b1 != a1 * b );
}
public int egressDone() {
if ( needsTerm() ) {
a = a1;
b = b1;
}
return egress();
}
public boolean done() {
return ( b == 0 || b1 == 0 );
}
private int a1, a, b1, b;
}
 
private static abstract class CFIterator {
public abstract boolean hasNext();
public abstract int next();
}
private static class R2cfIterator extends CFIterator {
public R2cfIterator(int aNumerator, int aDenominator) {
numerator = aNumerator; denominator = aDenominator;
}
public boolean hasNext() {
return denominator != 0;
}
public int next() {
int div = numerator / denominator;
int rem = numerator % denominator;
numerator = denominator;
denominator = rem;
return div;
}
private int numerator, denominator;
}
 
private static class Root2 extends CFIterator {
public Root2() {
firstReturn = true;
}
public boolean hasNext() {
return true;
}
public int next() {
if ( firstReturn ) {
firstReturn = false;
return 1;
}
return 2;
}
private boolean firstReturn;
}
private static class ReciprocalRoot2 extends CFIterator {
public ReciprocalRoot2() {
firstReturn = true;
secondReturn = true;
}
public boolean hasNext() {
return true;
}
public int next() {
if ( firstReturn ) {
firstReturn = false;
return 0;
}
if ( secondReturn ) {
secondReturn = false;
return 1;
}
return 2;
}
private boolean firstReturn, secondReturn;
}
private static record CFData(String text, int[] arguments, CFIterator iterator) {}
}
</syntaxhighlight>
{{ out }}
<pre>
[1; 5, 2] + 1 / 2 -> 1 1 2 7
[3; 7] + 1 / 2 -> 3 1 1 1 4
[3; 7] divided by 4 -> 0 1 3 1 2
sqrt(2) -> 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 / sqrt(2) -> 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
(1 + sqrt(2)) / 2 -> 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4
(1 + 1 / sqrt(2)) / 2 -> 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 5
</pre>
 
=={{header|Julia}}==
Line 4,933 ⟶ 5,404:
(1 + 1 / sqrt(2)) / 2 -> 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1
</pre>
 
=={{header|Mercury}}==
{{trans|Haskell}}
 
<syntaxhighlight lang="mercury">
%%%-------------------------------------------------------------------
 
:- module univariate_continued_fraction_task_lazy.
 
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
 
:- implementation.
:- import_module integer. % Arbitrary-precision integers.
:- import_module lazy. % Lazy evaluation.
:- import_module list.
:- import_module rational. % Arbitrary-precision fractions.
:- import_module string.
 
%%%-------------------------------------------------------------------
%%%
%%% The following lazy list implementation is suggested in the Mercury
%%% Library Reference, although (for convenience) I have changed the
%%% names.
%%%
 
:- type lzlist(T)
---> lzlist(lazy(lzcell(T))).
 
:- type lzcell(T)
---> lzcons(T, lzlist(T))
; lznil.
 
%%%-------------------------------------------------------------------
%%%
%%% Types of interest.
%%%
 
:- type cf == lzlist(integer). % A continued fraction.
:- type hf == {integer, integer,
integer, integer}. % A homographic function.
:- type ng4 == hf. % A synonym for hf.
 
 
%%%-------------------------------------------------------------------
%%%
%%% Make a "continued fraction" that has no terms.
%%%
 
:- func cfnil = cf.
cfnil = lzlist(delay((func) = lznil)).
 
%%%-------------------------------------------------------------------
%%%
%%% Make a continued fraction that repeats the same term forever.
%%%
 
:- func repeat_forever(integer) = cf.
 
repeat_forever(N) = CF :-
CF = lzlist(delay(Cons)),
Cons = ((func) = lzcons(N, repeat_forever(N))).
 
%%%-------------------------------------------------------------------
%%%
%%% sqrt2 is a continued fraction for the square root of two.
%%%
 
:- func sqrt2 = cf.
 
sqrt2 = lzlist(delay((func) = lzcons(one, repeat_forever(two)))).
 
%%%-------------------------------------------------------------------
%%%
%%% r2cf takes a fraction, and returns a continued fraction as a lazy
%%% list of terms.
%%%
 
:- func r2cf(rational) = cf.
:- func r2cf(integer, integer) = cf.
 
r2cf(Ratnum) = CF :-
r2cf(numer(Ratnum), denom(Ratnum)) = CF.
 
r2cf(Numerator, Denominator) = CF :-
(if (Denominator = zero)
then (CF = cfnil)
else (CF = lzlist(delay(Cons)),
((func) = X :-
(X = lzcons(Quotient, r2cf(Denominator, Remainder)),
%% What follows is division with truncation towards zero.
divide_with_rem(Numerator, Denominator,
Quotient, Remainder))) = Cons)).
 
%%%-------------------------------------------------------------------
%%%
%%% Homographic functions of continued fractions.
%%%
 
:- func apply_ng4(ng4, cf) = cf.
 
:- func add_integer(cf, integer) = cf.
:- func add_rational(cf, rational) = cf.
:- func mul_integer(cf, integer) = cf.
:- func mul_rational(cf, rational) = cf.
:- func div_integer(cf, integer) = cf.
:- func reciprocal(cf) = cf.
 
add_integer(CF, I) = apply_ng4({one, I, zero, one}, CF).
add_rational(CF, R) = CF1 :-
N = (rational.numer(R)),
D = (rational.denom(R)),
CF1 = apply_ng4({D, N, zero, D}, CF).
mul_integer(CF, I) = apply_ng4({I, zero, zero, one}, CF).
mul_rational(CF, R) = apply_ng4({numer(R), zero, zero, denom(R)}, CF).
div_integer(CF, I) = apply_ng4({one, zero, zero, I}, CF).
reciprocal(CF) = apply_ng4({zero, one, one, zero}, CF).
 
apply_ng4({ A1, A, B1, B }, Other_CF) = CF :-
(if (B1 = zero, B = zero)
then (CF = cfnil)
else if (B1 \= zero, B \= zero)
then (
% The integer divisions here truncate towards zero. Say "div"
% instead of "//" to truncate towards negative infinity.
Q1 = A1 // B1,
Q = A // B,
(if (Q1 = Q)
then (CF = lzlist(delay(Cons)),
Cons = ((func) = lzcons(Q, ng4_eject_term(A1, A, B1, B,
Other_CF, Q))))
else (CF = ng4_absorb_term(A1, A, B1, B, Other_CF)))
)
else (CF = ng4_absorb_term(A1, A, B1, B, Other_CF))).
 
:- func ng4_eject_term(integer, integer, integer, integer, cf,
integer) = cf.
ng4_eject_term(A1, A, B1, B, Other_CF, Term) = CF :-
CF = apply_ng4({ B1, B, A1 - (B1 * Term), A - (B * Term) },
Other_CF).
 
:- func ng4_absorb_term(integer, integer, integer, integer, cf) = cf.
ng4_absorb_term(A1, A, B1, B, Other_CF) = CF :-
(Other_CF = lzlist(Cell),
CF = (if (force(Cell) = lzcons(Term, Rest))
then apply_ng4({ A + (A1 * Term), A1,
B + (B1 * Term), B1 },
Rest)
else apply_ng4({ A1, A1, B1, B1 }, cfnil))).
 
 
%%%-------------------------------------------------------------------
%%%
%%% cf2string and cf2string_with_max_terms convert a continued
%%% fraction to a printable string.
%%%
 
:- func cf2string(cf) = string.
:- func cf2string_with_max_terms(cf, integer) = string.
 
cf2string(CF) = cf2string_with_max_terms(CF, integer(20)).
 
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 = lzlist(ValCell),
force(ValCell) = Cell,
(if (Cell = lzcons(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 ++ "]"))).
 
%%%-------------------------------------------------------------------
 
:- pred show(string::in, cf::in, io::di, io::uo) is det.
show(Expression, CF, !IO) :-
print(Expression, !IO),
print(" => ", !IO),
print(cf2string(CF), !IO),
nl(!IO).
 
main(!IO) :-
CF_13_11 = r2cf(rational(13, 11)),
CF_22_7 = r2cf(rational(22, 7)),
 
show("13/11", CF_13_11, !IO),
show("22/7", CF_22_7, !IO),
show("sqrt(2)", sqrt2, !IO),
 
show("13/11 + 1/2", add_rational(CF_13_11, rational(1, 2)), !IO),
show("22/7 + 1/2", add_rational(CF_22_7, rational(1, 2)), !IO),
show("(22/7)/4", div_integer(CF_22_7, integer(4)), !IO),
show("(22/7)*(1/4)", mul_rational(CF_22_7, rational(1, 4)), !IO),
show("1/sqrt(2)", reciprocal(sqrt2), !IO),
show("sqrt(2)/2", div_integer(sqrt2, two), !IO),
show("sqrt(2)*(1/2)", mul_rational(sqrt2, rational(1, 2)), !IO),
 
%% Getting (1 + 1/sqrt(2))/2 in a single step.
show("(2 + sqrt(2))/4",
apply_ng4({one, two, zero, integer(4)}, sqrt2),
!IO),
 
%% Different ways to compute the same thing.
show("(1/sqrt(2) + 1)/2",
div_integer(add_integer(reciprocal(sqrt2), one),
two),
!IO),
show("(1/sqrt(2))*(1/2) + 1/2",
add_rational(mul_rational(reciprocal(sqrt2),
rational(1, 2)),
rational(1, 2)),
!IO),
show("((sqrt(2)/2 + 1)/4)*2", % Contrived, to get in mul_integer.
mul_integer(div_integer(add_integer(div_integer(sqrt2, two),
one),
integer(4)),
two),
!IO),
 
true.
 
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
</syntaxhighlight>
 
{{out}}
<pre>$ mmc -m univariate_continued_fraction_task_lazy && ./univariate_continued_fraction_task_lazy
Making Mercury/int3s/univariate_continued_fraction_task_lazy.int3
Making Mercury/ints/univariate_continued_fraction_task_lazy.int
Making Mercury/cs/univariate_continued_fraction_task_lazy.c
Making Mercury/os/univariate_continued_fraction_task_lazy.o
Making univariate_continued_fraction_task_lazy
13/11 => [1;5,2]
22/7 => [3;7]
sqrt(2) => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
13/11 + 1/2 => [1;1,2,7]
22/7 + 1/2 => [3;1,1,1,4]
(22/7)/4 => [0;1,3,1,2]
(22/7)*(1/4) => [0;1,3,1,2]
1/sqrt(2) => [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
sqrt(2)/2 => [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
sqrt(2)*(1/2) => [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
(2 + sqrt(2))/4 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]
(1/sqrt(2) + 1)/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]
(1/sqrt(2))*(1/2) + 1/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]
((sqrt(2)/2 + 1)/4)*2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]</pre>
 
=={{header|Nim}}==
Line 6,548 ⟶ 7,276:
(sqrt(2)/2)/2 + 1/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]
(1/sqrt(2))/2 + 1/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]</pre>
 
===Translated from Haskell===
 
{{trans|Haskell}}
{{trans|Mercury}}
 
{{works with|Gauche Scheme|0.9.12}}
{{works with|CHICKEN Scheme|5.3.0}}
{{works with|Chibi Scheme|0.10.0}}
 
For CHICKEN Scheme you need the '''r7rs''' and '''srfi-41''' eggs.
 
This implementation represents a continued fraction as a lazy list. Thus there is memoization of terms suitable for sequential access to them.
 
<syntaxhighlight lang="scheme">
;;;-------------------------------------------------------------------
;;;
;;; With continued fractions as SRFI-41 lazy lists and homographic
;;; functions as vectors of length 4.
;;;
 
(cond-expand
(r7rs)
(chicken (import (r7rs))))
 
(import (scheme base))
(import (scheme case-lambda))
(import (scheme write))
(import (srfi 41)) ; Streams (lazy lists).
 
;;;-------------------------------------------------------------------
;;;
;;; Some simple continued fractions.
;;;
 
(define nil ; A "continued fraction" that contains no terms.
stream-null)
 
(define (repeat term) ; Infinite repetition of one term.
(stream-cons term (repeat term)))
 
(define sqrt2 ; The square root of two.
(stream-cons 1 (repeat 2)))
 
;;;-------------------------------------------------------------------
;;;
;;; Continued fraction for a rational number.
;;;
 
(define r2cf
(case-lambda
((n d)
(letrec ((recurs
(stream-lambda (n d)
(if (zero? d)
stream-null
(let-values (((q r) (floor/ n d)))
(stream-cons q (recurs d r)))))))
(recurs n d)))
((ratnum)
(let ((ratnum (exact ratnum)))
(r2cf (numerator ratnum)
(denominator ratnum))))))
 
;;;-------------------------------------------------------------------
;;;
;;; Application of a homographic function to a continued fraction.
;;;
 
(define-stream (apply-ng4 ng4 other-cf)
(define (eject-term a1 a b1 b other-cf term)
(apply-ng4 (vector b1 b (- a1 (* b1 term)) (- a (* b term)))
other-cf))
(define (absorb-term a1 a b1 b other-cf)
(if (stream-null? other-cf)
(apply-ng4 (vector a1 a1 b1 b1) other-cf)
(let ((term (stream-car other-cf))
(rest (stream-cdr other-cf)))
(apply-ng4 (vector (+ a (* a1 term)) a1
(+ b (* b1 term)) b1)
rest))))
(let ((a1 (vector-ref ng4 0))
(a (vector-ref ng4 1))
(b1 (vector-ref ng4 2))
(b (vector-ref ng4 3)))
(cond ((and (zero? b1) (zero? b)) stream-null)
((or (zero? b1) (zero? b)) (absorb-term a1 a b1 b other-cf))
(else
(let ((q1 (floor-quotient a1 b1))
(q (floor-quotient a b)))
(if (= q1 q)
(stream-cons q (eject-term a1 a b1 b other-cf q))
(absorb-term a1 a b1 b other-cf)))))))
 
;;;-------------------------------------------------------------------
;;;
;;; Particular homographic function applications.
;;;
 
(define (add-number cf num)
(if (integer? num)
(apply-ng4 (vector 1 num 0 1) cf)
(let ((num (exact num)))
(let ((n (numerator num))
(d (denominator num)))
(apply-ng4 (vector d n 0 d) cf)))))
 
(define (mul-number cf num)
(if (integer? num)
(apply-ng4 (vector num 0 0 1) cf)
(let ((num (exact num)))
(let ((n (numerator num))
(d (denominator num)))
(apply-ng4 (vector n 0 0 d) cf)))))
 
(define (div-number cf num)
(if (integer? num)
(apply-ng4 (vector 1 0 0 num) cf)
(let ((num (exact num)))
(let ((n (numerator num))
(d (denominator num)))
(apply-ng4 (vector d 0 0 n) cf)))))
 
(define (reciprocal cf) (apply-ng4 #(0 1 1 0) cf))
 
;;;-------------------------------------------------------------------
;;;
;;; cf2string: conversion from a continued fraction to a string.
;;;
 
(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 expression cf)
(display expression)
(display " => ")
(display (cf2string cf))
(newline))
 
(define cf:13/11 (r2cf 13/11))
(define cf:22/7 (r2cf 22/7))
(define cf:1/sqrt2 (reciprocal sqrt2))
 
(show "13/11" cf:13/11)
(show "22/7" cf:22/7)
(show "sqrt(2)" sqrt2)
(show "13/11 + 1/2" (add-number cf:13/11 1/2))
(show "22/7 + 1/2" (add-number cf:22/7 1/2))
(show "(22/7)/4" (div-number cf:22/7 4))
(show "(22/7)*(1/4)" (mul-number cf:22/7 1/4))
(show "(22/49)/(4/7)" (div-number (r2cf 22 49) 4/7))
(show "(22/49)*(7/4)" (mul-number (r2cf 22/49) 7/4))
(show "1/sqrt(2)" cf:1/sqrt2)
 
;; The simplest way to get (1 + 1/sqrt(2))/2.
(show "(sqrt(2) + 2)/4" (apply-ng4 #(1 2 0 4) sqrt2))
 
;; Getting it in a more obvious way.
(show "(1/sqrt(2) + 1)/2)" (div-number (add-number cf:1/sqrt2 1) 2))
 
;;;-------------------------------------------------------------------
</syntaxhighlight>
 
{{out}}
<pre>$ gosh univariate-continued-fraction-task-srfi41.scm
13/11 => [1;5,2]
22/7 => [3;7]
sqrt(2) => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
13/11 + 1/2 => [1;1,2,7]
22/7 + 1/2 => [3;1,1,1,4]
(22/7)/4 => [0;1,3,1,2]
(22/7)*(1/4) => [0;1,3,1,2]
(22/49)/(4/7) => [0;1,3,1,2]
(22/49)*(7/4) => [0;1,3,1,2]
1/sqrt(2) => [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
(sqrt(2) + 2)/4 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]
(1/sqrt(2) + 1)/2) => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]</pre>
 
=={{header|Standard ML}}==
Line 6,964 ⟶ 7,892:
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="ecmascriptwren">import "./dynamic" for Tuple
 
var CFData = Tuple.create("Tuple", ["str", "ng", "r", "gen"])
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/337727...351927"