Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Continued fraction/Arithmetic/Construct from rational number (view source)
Revision as of 19:31, 27 February 2023
, 1 year ago→Using a non-linear closure and memoizing in an array
Line 994:
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>
=={{header|C}}==
| |||