Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Continued fraction/Arithmetic/Construct from rational number (view source)
Revision as of 23:05, 16 February 2023
, 1 year ago→{{header|ATS}}
Line 293:
=={{header|ATS}}==
I am not certain "lazy evaluation" is the best way to describe what is needed, for it implies features of a programming language. Haskell, for example, evaluates lists lazily. ATS2 has the notation '''$delay''' for lazy evaluation of that kind. I considered using such methods, but decided against doing so.
What one is--I am certain--supposed to write is means for generating an arbitrary number of terms of a continued fraction, one term after another. It happens that, for a rational number, eventually all further terms are known to be infinite, and so need not be computed. The terms ''could'' be returned as a finite-length list. However, this will not be so when irrational numbers enter the picture. So one needs a way to generate ''any'' number of terms. And this is something that requires no "lazy" features of a language. It could be done about as easily in C as in ATS.
In the first example solution, 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">
Line 459 ⟶ 457:
{{out}}
<pre>
The continued fractions shown here are calculated by 'Euclidean division',
Line 626 ⟶ 624:
{{out}}
<pre>
1/2 => [0; 2]
3 => [3]
Line 638 ⟶ 636:
86764811216795659042036930840054034259385369935856288122043161670619721/27606985387162255149739023449108101809804435888681546220650096895197184 => [3; 7, 3943855055308893592819860492729728829972062269811649460092870985028169]
</pre>
===A practical implementation===
This example solution was written specifically with the idea of providing a general representation of possibly infinitely long continued fractions. Terms can be obtained arbitrarily, by their indices. One obtains '''Some term''' if the term is finite, or '''None()'' if the term is infinite.
One drawback is that, because a continued fraction is memoized, it may need to be updated. Therefore it must be stored in a mutable location, such as a '''var'''.
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
(*------------------------------------------------------------------*)
(* Continued fractions as processes for generating terms. The terms
are memoized and are accessed by their zero-based index. The terms
are represented as any one of the signed integer types for which
there is a typekind. *)
(* Notice that we do not use the ‘lazy evaluation’ features of ATS2.
I had considered using lazy streams, but they proved unsuitable.
What I do, instead, is force "cf" objects to be stored in mutable
locations. The object stored at the location changes as we memoize
terms. *)
abstype cf (tk : tkind) = ptr
typedef cf_generator (tk : tkind) =
() -<cloref1> Option (g0int tk)
extern fn {tk : tkind}
cf_make :
cf_generator tk -> cf tk
extern fn {tk : tkind}
{tki : tkind}
cf_get_at_guint :
{i : int}
(&cf tk >> _, g1uint (tki, i)) -> Option (g0int tk)
extern fn {tk : tkind}
{tki : tkind}
cf_get_at_gint :
{i : nat}
(&cf tk >> _, g1int (tki, i)) -> Option (g0int tk)
overload cf_get_at with cf_get_at_guint
overload cf_get_at with cf_get_at_gint
overload [] with cf_get_at
extern fn {tk : tkind}
cf2string_max_terms
(cf : &cf tk >> _,
max_terms : size_t)
: string
extern fn {tk : tkind}
cf2string_default_max_terms
(cf : &cf tk >> _)
: string
overload cf2string with cf2string_max_terms
overload cf2string with cf2string_default_max_terms
(* - - - - - - - - - - - - - *)
local
typedef _cf (tk : tkind, terminated : bool, m : int, n : int) =
[m <= n]
'{
terminated = bool terminated, (* No more terms? *)
m = size_t m, (* The number of terms computed so far. *)
n = size_t n, (* The size of memo storage.*)
memo = arrayref (g0int tk, n), (* Memoized terms. *)
gen = cf_generator tk (* A thunk to generate terms. *)
}
typedef _cf (tk : tkind, m : int) =
[terminated : bool]
[n : int | m <= n]
_cf (tk, terminated, m, n)
typedef _cf (tk : tkind) =
[m : int]
_cf (tk, m)
fn {tk : tkind}
_cf_get_more_terms
{terminated : bool}
{m : int}
{n : int}
{needed : int | m <= needed; needed <= n}
(cf : _cf (tk, terminated, m, n),
needed : size_t needed)
: [m1 : int | m <= m1; m1 <= needed]
[n1 : int | m1 <= n1]
_cf (tk, m1 < needed, m1, n1) =
let
prval () = lemma_g1uint_param (cf.m)
macdef memo = cf.memo
fun
loop {i : int | m <= i; i <= needed}
.<needed - i>.
(i : size_t i)
: [m1 : int | m <= m1; m1 <= needed]
[n1 : int | m1 <= n1]
_cf (tk, m1 < needed, m1, n1) =
if i = needed then
'{
terminated = false,
m = needed,
n = (cf.n),
memo = memo,
gen = (cf.gen)
}
else
begin
case+ (cf.gen) () of
| None () =>
'{
terminated = true,
m = i,
n = (cf.n),
memo = memo,
gen = (cf.gen)
}
| Some term =>
begin
memo[i] := term;
loop (succ i)
end
end
in
loop (cf.m)
end
fn {tk : tkind}
_cf_update {terminated : bool}
{m : int}
{n : int | m <= n}
{needed : int}
(cf : _cf (tk, terminated, m, n),
needed : size_t needed)
: [terminated1 : bool]
[m1 : int | m <= m1]
[n1 : int | m1 <= n1]
_cf (tk, terminated1, m1, n1) =
let
prval () = lemma_g1uint_param (cf.m)
macdef memo = cf.memo
macdef gen = cf.gen
in
if (cf.terminated) then
cf
else if needed <= (cf.m) then
cf
else if needed <= (cf.n) then
_cf_get_more_terms<tk> (cf, needed)
else
let (* Provides about 50% more room than is needed. *)
val n1 = needed + half needed
val memo1 = arrayref_make_elt (n1, g0i2i 0)
val () =
let
var i : [i : nat] size_t i
in
for (i := i2sz 0; i < (cf.m); i := succ i)
memo1[i] := memo[i]
end
val cf1 =
'{
terminated = false,
m = (cf.m),
n = n1,
memo = memo1,
gen = (cf.gen)
}
in
_cf_get_more_terms<tk> (cf1, needed)
end
end
in (* local *)
assume cf tk = _cf tk
implement {tk}
cf_make gen =
let
#ifndef CF_START_SIZE #then
#define CF_START_SIZE 8
#endif
in
'{
terminated = false,
m = i2sz 0,
n = i2sz CF_START_SIZE,
memo = arrayref_make_elt (i2sz CF_START_SIZE, g0i2i 0),
gen = gen
}
end
implement {tk} {tki}
cf_get_at_guint {i} (cf, i) =
let
prval () = lemma_g1uint_param i
val i : size_t i = g1u2u i
val cf1 = _cf_update<tk> (cf, succ i)
in
cf := cf1;
if i < (cf1.m) then
Some (arrayref_get_at<g0int tk> (cf1.memo, i))
else
None ()
end
implement {tk} {tki}
cf_get_at_gint (cf, i) =
cf_get_at_guint<tk><sizeknd> (cf, g1i2u i)
end (* local *)
implement {tk}
cf2string_max_terms (cf, max_terms) =
let
fun
loop (i : Size_t,
cf : &cf tk >> _,
sep : string,
accum : string)
: string =
if i = max_terms then
strptr2string (string_append (accum, ", ...]"))
else
begin
case+ cf[i] of
| None () =>
strptr2string (string_append (accum, "]"))
| Some term =>
let
val term_str = tostring_val<g0int tk> term
val accum =
strptr2string (string_append (accum, sep, term_str))
val sep = if sep = "[" then "; " else ", "
in
loop (succ i, cf, sep, accum)
end
end
in
loop (i2sz 0, cf, "[", "")
end
implement {tk}
cf2string_default_max_terms cf =
let
#ifndef DEFAULT_CF_MAX_TERMS #then
#define DEFAULT_CF_MAX_TERMS 20
#endif
in
cf2string_max_terms (cf, i2sz DEFAULT_CF_MAX_TERMS)
end
(*------------------------------------------------------------------*)
(* r2cf: transform a rational number to a continued fraction. *)
extern fn {tk : tkind}
r2cf :
(g0int tk, g0int tk) -> cf tk
(* - - - - - - - - - - - - - *)
implement {tk}
r2cf (n, d) =
let
val n = ref<g0int tk> n
val d = ref<g0int tk> d
fn
gen () :<cloref1> Option (g0int tk) =
if iseqz !d then
None ()
else
let
(* The method of rounding the quotient seems unimportant,
and so let us simply use the truncation towards zero
that is native to C. *)
val numer = !n
and denom = !d
val q = numer / denom
and r = numer mod denom
in
!n := denom;
!d := r;
Some q
end
in
cf_make gen
end
(*------------------------------------------------------------------*)
val some_rationals =
$list (@(1LL, 2LL),
@(3LL, 1LL),
@(23LL, 8LL),
@(13LL, 11LL),
@(22LL, 7LL),
@(~151LL, 77LL),
@(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))
implement
main0 () =
let
var p : List0 @(llint, llint)
in
for (p := some_rationals; ~list_is_nil p; p := list_tail p)
let
val @(n, d) = list_head<@(llint, llint)> p
var cf = r2cf (n, d)
in
println! (n, "/", d, " => ", cf2string cf)
end
end
(*------------------------------------------------------------------*)
</lang>
{{out}}
<pre>$ patscc -DATS_MEMALLOC_GCBDW -O2 -std=gnu2x continued-fraction-from-rational-3.dats -lgc && ./a.out
1/2 => [0; 2]
3/1 => [3]
23/8 => [2; 1, 7]
13/11 => [1; 5, 2]
22/7 => [3; 7]
-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, ...]
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}}==
| |||