Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Continued fraction/Arithmetic/Construct from rational number (view source)
Revision as of 21:04, 27 February 2023
, 1 year ago→Using a non-linear lazy list
Line 1,117:
{{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]
| |||