How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the Mercury programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the Mercury programming language
Table of Contents
Problem Statement
The purpose of this task is to write a function
r 2 c f
(
i n t
{\displaystyle {\mathit {r2cf}}(\mathrm {int} }
N
1
,
i n t
{\displaystyle N_{1},\mathrm {int} }
N
2
)
{\displaystyle N_{2})}
, or
r 2 c f
(
F r a c t i o n
{\displaystyle {\mathit {r2cf}}(\mathrm {Fraction} }
N )
{\displaystyle N)}
, which will output a continued fraction assuming: The function should output its results one digit at a time each time it is called, in a manner sometimes described as lazy evaluation. To achieve this it must determine: the integer part; and remainder part, of
N
1
{\displaystyle N_{1}}
divided by
N
2
{\displaystyle N_{2}}
. It then sets
N
1
{\displaystyle N_{1}}
to
N
2
{\displaystyle N_{2}}
and
N
2
{\displaystyle N_{2}}
to the determined remainder part. It then outputs the determined integer part. It does this until
a b s
(
N
2
)
{\displaystyle \mathrm {abs} (N_{2})}
is zero. Demonstrate the function by outputing the continued fraction for:
2
{\displaystyle {\sqrt {2}}}
should approach
[ 1 ; 2 , 2 , 2 , 2 , … ]
{\displaystyle [1;2,2,2,2,\ldots ]}
try ever closer rational approximations until boredom gets the better of you: Try : Observe how this rational number behaves differently to
2
{\displaystyle {\sqrt {2}}}
and convince yourself that, in the same way as
3.7
{\displaystyle 3.7}
may be represented as
3.70
{\displaystyle 3.70}
when an extra decimal place is required,
[ 3 ; 7 ]
{\displaystyle [3;7]}
may be represented as
[ 3 ; 7 , ∞ ]
{\displaystyle [3;7,\infty ]}
when an extra term is required.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Continued fraction/Arithmetic/Construct from rational number step by step in the Mercury programming language
Source code in the mercury programming language
%%%-------------------------------------------------------------------
:- module continued_fraction_from_rational.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module int.
:- import_module list.
:- import_module string.
%%%-------------------------------------------------------------------
%%%
%%% ‘r2cf’ is a predicate, not a function. If it succeeds, it
%%% calculates not only the next digit, but the next starting
%%% fraction. If it fails, we are done.
%%%
:- pred r2cf(int::in, int::out, int::in, int::out, int::out)
is semidet.
r2cf(!N1, !N2, Digit) :-
(Dividend = !.N1),
(Divisor = !.N2),
(Divisor \= 0), % Fail if we have reached the end.
(!:N1 = Divisor), % The next Dividend.
(!:N2 = Dividend mod Divisor), % Floor division. The next divisor.
(Digit = Dividend div Divisor). % Floor division. The next digit.
%%%-------------------------------------------------------------------
%%%
%%% ‘r2cf_digits’ takes numerator and denominator of a rational
%%% number, and returns a list of continued fraction digits.
%%%
:- func r2cf_digits(int, int) = list(int).
:- pred r2cf_digits_loop(int::in, int::in,
list(int)::in, list(int)::out) is det.
r2cf_digits(N1, N2) = Digit_list :-
r2cf_digits_loop(N1, N2, [], Digit_list).
r2cf_digits_loop(N1, N2, !Digit_list) :-
(if r2cf(N1, N1_next, N2, N2_next, Digit)
then r2cf_digits_loop(N1_next, N2_next,
[Digit | !.Digit_list],
!:Digit_list)
else (!:Digit_list = reverse(!.Digit_list))).
%%%-------------------------------------------------------------------
%%%
%%% ‘print_cf’ prints a continued fraction nicely.
%%%
:- pred print_cf(list(int)::in, io::di, io::uo) is det.
:- pred print_cf_loop(list(int)::in, string::in, io::di, io::uo)
is det.
print_cf(Digit_list, !IO) :-
print_cf_loop(Digit_list, "[", !IO).
print_cf_loop(Digit_list, Sep, !IO) :-
(if (Digit_list = [Digit | More_digits])
then (print(Sep, !IO),
print(Digit, !IO),
(if (Sep = "[")
then print_cf_loop(More_digits, "; ", !IO)
else print_cf_loop(More_digits, ", ", !IO)))
else print("]", !IO)).
%%%-------------------------------------------------------------------
%%%
%%% ‘example’ takes numerator and denominator of a rational number,
%%% and prints a line of output.
%%%
:- pred example(int::in, int::in, io::di, io::uo) is det.
example(N1, N2, !IO) :-
print(N1, !IO),
print("/", !IO),
print(N2, !IO),
print(" => ", !IO),
print_cf(r2cf_digits(N1, N2), !IO),
nl(!IO).
%%%-------------------------------------------------------------------
main(!IO) :-
example(1, 2, !IO),
example(3, 1, !IO),
example(23, 8, !IO),
example(13, 11, !IO),
example(22, 7, !IO),
example(-151, 77, !IO),
example(14142, 10000, !IO),
example(141421, 100000, !IO),
example(1414214, 1000000, !IO),
example(14142136, 10000000, !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),
true.
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:
%%%-------------------------------------------------------------------
:- 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(delay((func) = nil)))
else (CF = lazy_list(delay(Cons)),
((func) = Cell :-
(Cell = cons(Quotient, r2cf(Denominator, Remainder)),
%% What follows is division with truncation towards zero.
divide_with_rem(Numerator, Denominator,
Quotient, Remainder))) = Cons)).
%%%-------------------------------------------------------------------
%%%
%%% 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:
You may also check:How to resolve the algorithm Golden ratio/Convergence step by step in the M4 programming language
You may also check:How to resolve the algorithm Averages/Arithmetic mean step by step in the V (Vlang) programming language
You may also check:How to resolve the algorithm Apply a callback to an array step by step in the Sparkling programming language
You may also check:How to resolve the algorithm Distribution of 0 digits in factorial series step by step in the Phix programming language
You may also check:How to resolve the algorithm Primality by Wilson's theorem step by step in the C++ programming language