Continued fraction/Arithmetic/Construct from rational number: Difference between revisions
Content added Content deleted
Line 3,232: | Line 3,232: | ||
=={{header|Mercury}}== |
=={{header|Mercury}}== |
||
===A straightforward implementation=== |
|||
{{works with|Mercury|22.01.1}} |
{{works with|Mercury|22.01.1}} |
||
<syntaxhighlight lang="mercury">%%%------------------------------------------------------------------- |
<syntaxhighlight lang="mercury">%%%------------------------------------------------------------------- |
||
Line 3,365: | Line 3,366: | ||
31428571/10000000 => [3; 7, 476190, 3] |
31428571/10000000 => [3; 7, 476190, 3] |
||
314285714/100000000 => [3; 7, 7142857]</pre> |
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}}== |
=={{header|Modula-2}}== |