Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Continued fraction/Arithmetic/Construct from rational number (view source)
Revision as of 17:32, 28 February 2023
, 1 year ago→{{header|Mercury}}
Line 3,232:
=={{header|Mercury}}==
===A straightforward implementation===
{{works with|Mercury|22.01.1}}
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------
Line 3,365 ⟶ 3,366:
31428571/10000000 => [3; 7, 476190, 3]
314285714/100000000 => [3; 7, 7142857]</pre>
===An implementation using lazy lists===
{{trans|Haskell}}
{{works with|Mercury|22.01.1}}
This version has the advantage that it memoizes terms in a form that is efficient for sequential access.
I used arbitrary-precision numbers so I could plug in some big numbers.
<syntaxhighlight lang="mercury">
%%%-------------------------------------------------------------------
:- module continued_fraction_from_rational_lazy.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module exception.
:- import_module integer. % Arbitrary-precision integers.
:- import_module lazy. % Lazy evaluation.
:- import_module list.
:- import_module string.
%% NOTE: There IS a "rational" module, for arbitrary-precision
%% rational numbers, but I wrote this example for plain "integer"
%% type. One could easily add "rational" support.
%%%-------------------------------------------------------------------
%%%
%%% The following lazy list implementation is suggested in the Mercury
%%% Library Reference.
%%%
:- type lazy_list(T)
---> lazy_list(lazy(list_cell(T))).
:- type list_cell(T)
---> cons(T, lazy_list(T))
; nil.
:- type cf == lazy_list(integer).
%%%-------------------------------------------------------------------
%%%
%%% r2cf takes numerator and denominator of a fraction, and returns a
%%% continued fraction as a lazy list of terms.
%%%
:- func r2cf(integer, integer) = cf.
r2cf(Numerator, Denominator) = CF :-
(if (Denominator = zero)
then (CF = lazy_list(val(nil)))
else (CF = lazy_list(val(cons(Quotient, Tail))),
Tail = r2cf(Denominator, Remainder),
%% What follows is division with truncation towards zero.
divide_with_rem(Numerator, Denominator,
Quotient, Remainder))).
%%%-------------------------------------------------------------------
%%%
%%% cf2string and cf2string_with_max_terms convert a continued
%%% fraction to a printable string.
%%%
:- func cf2string(cf) = string.
cf2string(CF) = cf2string_with_max_terms(CF, integer(1000)).
:- func cf2string_with_max_terms(cf, integer) = string.
cf2string_with_max_terms(CF, MaxTerms) = S :-
S = cf2string_loop(CF, MaxTerms, zero, "[").
:- func cf2string_loop(cf, integer, integer, string) = string.
cf2string_loop(CF, MaxTerms, I, Accum) = S :-
(CF = lazy_list(ValCell),
force(ValCell) = Cell,
(if (Cell = cons(Term, Tail))
then (if (I = MaxTerms) then (S = Accum ++ ",...]")
else ((Separator = (if (I = zero) then ""
else if (I = one) then ";"
else ",")),
TermStr = to_string(Term),
S = cf2string_loop(Tail, MaxTerms, I + one,
Accum ++ Separator ++ TermStr)))
else (S = Accum ++ "]"))).
%%%-------------------------------------------------------------------
%%%
%%% example takes a fraction, as a string, or as separate numerator
%%% and denominator strings, and prints a line of output.
%%%
:- pred example(string::in, io::di, io::uo) is det.
:- pred example(string::in, string::in, io::di, io::uo) is det.
example(Fraction, !IO) :-
split_at_char(('/'), Fraction) = Split,
(if (Split = [Numerator])
then example_(Fraction, Numerator, "1", !IO)
else if (Split = [Numerator, Denominator])
then example_(Fraction, Numerator, Denominator, !IO)
else throw("Not an integer or fraction: \"" ++ Fraction ++ "\"")).
example(Numerator, Denominator, !IO) :-
example_(Numerator ++ "/" ++ Denominator,
Numerator, Denominator, !IO).
:- pred example_(string::in, string::in, string::in, io::di, io::uo)
is det.
example_(Fraction, Numerator, Denominator, !IO) :-
(N = integer.det_from_string(Numerator)),
(D = integer.det_from_string(Denominator)),
print(Fraction, !IO),
print(" => ", !IO),
print(cf2string(r2cf(N, D)), !IO),
nl(!IO).
%%%-------------------------------------------------------------------
main(!IO) :-
example("1/2", !IO),
example("3", !IO),
example("23/8", !IO),
example("13/11", !IO),
example("22/7", !IO),
example("-151/77", !IO),
%% I made "example" overloaded, so it can take separate numerator
%% and denominator strings.
example("151", "-77", !IO),
example("14142/10000", !IO),
example("141421/100000", !IO),
example("1414214/1000000", !IO),
example("14142136/10000000", !IO),
%% Decimal expansion of sqrt(2): see https://oeis.org/A002193
example("141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", !IO),
example("31/10", !IO),
example("314/100", !IO),
example("3142/1000", !IO),
example("31428/10000", !IO),
example("314285/100000", !IO),
example("3142857/1000000", !IO),
example("31428571/10000000", !IO),
example("314285714/100000000", !IO),
%% Decimal expansion of pi: see https://oeis.org/A000796
example("314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", !IO),
true.
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
</syntaxhighlight>
{{out}}
<pre>$ mmc continued_fraction_from_rational_lazy.m && ./continued_fraction_from_rational_lazy
1/2 => [0;2]
3 => [3]
23/8 => [2;1,7]
13/11 => [1;5,2]
22/7 => [3;7]
-151/77 => [-1;-1,-24,-1,-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]
141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [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,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,5,1,8,3,1,2,2,1,6,2,2,3,1,2,3,1,1,39,1,3,1,2,4,10,1,6,1,30,5,2,1,1,1,1,1,32,1,4,18,124,3,2,1,1,8,1,1,1,6,15,2,3,2,7,1,4,9,2,7,1,1,1,1,1,2,1,10,1,31,5,1,1,1,7,1,14,10,3,11,1,2,1,65,4,9,2,3,2,2,9,1,1,2,1,1,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]
314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214/100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 => [3;7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1,15,3,13,1,4,2,6,6,99,1,2,2,6,3,5,1,1,6,8,1,7,1,2,3,7,1,2,1,1,12,1,1,1,3,1,1,8,1,1,2,1,6,1,1,5,2,2,3,1,2,4,4,16,1,161,45,1,22,1,2,2,1,4,1,2,24,1,2,1,3,1,2,1,1,10,2,8,2,1,4,1,1,2,3,6,8,1,1,1,7,1,1,1,1,21,1,2,1,2,1,1,21,1,6,1,2,2,1,1,2,5,2,3,2,9,3,3,2,2,1,1,3,7,3,1,8,36,20,6,17,15,1,2,5,1,4,9,6,26,1,1,1,7,1,79,4,1,1,10,4,5,1,1,55,8,1,4,4,10,5,3,1,2,6,1,2,1,1,2,1,20,3,1,1,2,3]</pre>
=={{header|Modula-2}}==
| |||