Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Content added Content deleted
Line 293: | Line 293: | ||
=={{header|ATS}}== |
=={{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. |
|||
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. |
|||
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. |
|||
I hope the point is not that one must use lazy evaluation to do this algorithm! That is getting into programming language features rather than problem-solving. Rather, the point seems to write ''some'' method of producing the digits of the continued fraction. ''This process itself''--of producing "digits" of a continued fraction--will be regarded as the value of the number. For a rational number, the process terminates; for an irrational number, it does not. |
|||
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). |
|||
(I have, by the way, long viewed "a real number" as such a process. It does not matter whether or not the process involves continued fractions, as long as it produces an arbitrarily precise rational number.) |
|||
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"> |
<syntaxhighlight lang="ats"> |
||
Line 459: | Line 457: | ||
{{out}} |
{{out}} |
||
<pre> |
<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', |
The continued fractions shown here are calculated by 'Euclidean division', |
||
Line 626: | Line 624: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre>$ patscc -DATS_MEMALLOC_GCBDW `pkg-config --variable=PATSCCFLAGS ats2-xprelude` `pkg-config --cflags ats2-xprelude` -O2 -std=gnu2x continued-fraction-from-rational-2.dats `pkg-config --libs ats2-xprelude` -lgc -lm && ./a.out |
||
1/2 => [0; 2] |
1/2 => [0; 2] |
||
3 => [3] |
3 => [3] |
||
Line 638: | Line 636: | ||
86764811216795659042036930840054034259385369935856288122043161670619721/27606985387162255149739023449108101809804435888681546220650096895197184 => [3; 7, 3943855055308893592819860492729728829972062269811649460092870985028169] |
86764811216795659042036930840054034259385369935856288122043161670619721/27606985387162255149739023449108101809804435888681546220650096895197184 => [3; 7, 3943855055308893592819860492729728829972062269811649460092870985028169] |
||
</pre> |
</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}}== |
=={{header|C}}== |