Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Continued fraction/Arithmetic/Construct from rational number (view source)
Revision as of 22:05, 13 February 2023
, 1 year ago→{{header|C}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 181:
For N = 31428571, D = 10000000 : 3 7 476190 3
For N = 157142857, D = 50000000 : 3 7 7142857
</pre>
=={{header|ATS}}==
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.
I hope the point is not that one must use lazy evaluation to do this algorithm! Rather, it should be that, at each step, you are performing the same process, merely with a different starting point. If the function returned the next N1 and N2, along with the next digit, you would have a purely functional version.
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">
(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* First, let us implement a proper method of division of signed
integers, in which the remainder is always non-negative. (I
implement such division in my ats2-xprelude package at
https://sourceforge.net/p/chemoelectric/ats2-xprelude and have
copied the implementation from there.) *)
extern fn {tk : tkind}
g0int_eucliddivrem :
(g0int tk, g0int tk) -<> @(g0int tk, g0int tk)
implement {tk}
g0int_eucliddivrem (n, d) =
let
(* The C optimizer most likely will reduce these these two
divisions to just one. They are simply synonyms for C '/' and
'%', and perform division that rounds the quotient towards
zero. *)
val q0 = g0int_div (n, d)
val r0 = g0int_mod (n, d)
in
(* The following calculation results in 'floor division', if the
divisor is positive, or 'ceiling division', if the divisor is
negative. This choice of method results in the remainder never
being negative. *)
if isgtez n then
@(q0, r0)
else if iseqz r0 then
@(q0, r0)
else if isltz d then
@(succ q0, r0 - d)
else
@(pred q0, r0 + d)
end
(*------------------------------------------------------------------*)
(* I implement the lazy evaluation by having r2cf explicitly create
a thunk that returns the digits. *)
fn {tk : tkind}
step (N1 : ref (g0int tk),
N2 : ref (g0int tk))
: g0int tk =
let
val @(q, r) = g0int_eucliddivrem (!N1, !N2)
in
!N1 := !N2;
!N2 := r;
q
end
fn {tk : tkind}
r2cf (N1 : g0int tk,
N2 : g0int tk)
: () -<cloref1> Option (g0int tk) =
let
val N1 = ref<g0int tk> N1
and N2 = ref<g0int tk> N2
in
lam () =>
if iseqz !N2 then
None ()
else
Some (step (N1, N2))
end
(*------------------------------------------------------------------*)
fn {tk : tkind}
print_digits (f : () -<cloref1> Option (g0int tk))
: void =
let
fun
loop (sep : string)
: void =
case+ f () of
| None () => println! ("]")
| Some d =>
begin
print! sep;
fprint_val<g0int tk> (stdout_ref, d);
if sep = "[" then
loop "; "
else
loop ", "
end
in
loop "["
end
fn {tk : tkind}
print_continued_fraction
(ratnum : @(g0int tk, g0int tk))
: void =
let
val @(N1, N2) = ratnum
in
fprint_val<g0int tk> (stdout_ref, N1);
print! "/";
fprint_val<g0int tk> (stdout_ref, N2);
print! " => ";
print_digits (r2cf<tk> (N1, N2))
end
(*------------------------------------------------------------------*)
val test_cases =
$list (@(1LL, 2LL),
@(3LL, 1LL),
@(23LL, 8LL),
@(13LL, 11LL),
@(22LL, 7LL),
@(~151LL, 77LL), (* The numerator is negative. *)
@(151LL, ~77LL), (* The denominator is negative. *)
@(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),
@(2200000000000000000LL, 700000000000000000LL),
@(2200000000000000001LL, 700000000000000000LL),
@(2200000000000000000LL, 700000000000000001LL))
implement
main0 () =
let
var p : List0 @(llint, llint)
in
println! ();
print! ("The continued fractions shown here are calculated by ");
println! ("'Euclidean division',");
println! ("where the remainder is always non-negative:");
println! ();
for (p := test_cases; ~list_is_nil p; p := list_tail p)
print_continued_fraction<llintknd> (list_head p);
println! ();
println! ("Note that [3; 6, 1] is equal to [3; 7].");
println! ()
end
(*------------------------------------------------------------------*)
</syntaxhighlight>
{{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',
where the remainder is always non-negative:
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]
151/-77 => [-1; -2, 1, 23, 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]
2200000000000000000/700000000000000000 => [3; 7]
2200000000000000001/700000000000000000 => [3; 6, 1, 14285714285714284, 1, 6]
2200000000000000000/700000000000000001 => [3; 7, 4545454545454545, 3, 7]
Note that [3; 6, 1] is equal to [3; 7].
</pre>
| |||