[m-rev.] for review: add some functions to integer.m and rational.m
Julien Fischer
juliensf at students.cs.mu.OZ.AU
Tue Dec 16 15:43:39 AEDT 2003
Estimated hours taken: 1.5
Branches: main
Add some functions to the integer and rational modules.
Clean up the code in these modules so it adheres more closely to
our current coding standards.
NEWS:
Mention these changes.
library/integer.m:
Shift the constant functions integer.zero/0 and integer.one/0
back into the interface. According to the log they were deleted
because they were not sufficiently useful. In my view the symbolic
names are preferable to writing them as integer(1) and integer(0).
Add a function version of integer.pow/3.
Shift a large comment that concerns implementation details and
possible improvements to the module from the interface into the
implementation.
(This avoids it being included in the library reference manual).
Various code cleanups, in particular fix spacing and
indentation throughout.
library/rational.m:
Add a function rational.rational/1 that converts an int to
a rational and function rational.from_integer/1 that does the
same with an integer.
For consistency with the above add a function rational.from_integers/2
and deprecate the version rational.rational_from_integers/2.
Remove the functions izero and ione from the implementation and
just call integer.zero/0 and integer.one/0 now that they are
exported from the integer module again.
Various code cleanups.
Julien.
Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.323
diff -u -r1.323 NEWS
--- NEWS 9 Dec 2003 15:03:00 -0000 1.323
+++ NEWS 16 Dec 2003 04:21:26 -0000
@@ -186,6 +186,13 @@
io.binary_input_stream/3
io.binary_output_stream/3
+* We've added some constant functions, integer.zero/0 and integer.one/0
+ to integer.m. We have also added a function version of integer.pow/3.
+
+* We've added some functions, rational.int/1, rational.from_integer/1
+ and rational.from_integers/2 to rational.m
+ The function rational.rational_from_integers/2 has been deprecated.
+
Changes to the extras distribution:
* Nothing yet.
Index: library/integer.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/integer.m,v
retrieving revision 1.10
diff -u -r1.10 integer.m
--- library/integer.m 17 Aug 2003 13:30:11 -0000 1.10
+++ library/integer.m 16 Dec 2003 04:07:55 -0000
@@ -13,69 +13,10 @@
% any number of digits, unlike an int, which is limited to the
% precision of the machine's int type, which is typically 32 bits.)
%
-% Note that all operators behave as the equivalent operators on ints do.
+% NOTE: All operators behave as the equivalent operators on ints do.
% This includes the division operators: / // rem div mod.
%
-% Possible improvements:
-%
-% 1) allow negative digits (-base+1 .. base-1) in lists of
-% digits and normalise only when printing. This would
-% probably simplify the division algorithm, also.
-% (djh: this is not really done although -ve integers include a list
-% of -ve digits for faster comparison and so that normal mercury
-% sorting produces an intuitive order)
-%
-% 2) alternatively, instead of using base=10000, use *all* the
-% bits in an int and make use of the properties of machine
-% arithmetic. Base 10000 doesn't use even half the bits
-% in an int, which is inefficient. (Base 2^14 would be
-% a little better but would require a slightly more
-% complex case conversion on reading and printing.)
-% (djh: this is done)
-%
-% 3) Use an O(n^(3/2)) algorithm for multiplying large
-% integers, rather than the current O(n^2) method.
-% There's an obvious divide-and-conquer technique,
-% Karatsuba multiplication.
-%
-% 4) We could overload operators so that we can have mixed operations
-% on ints and integers. For example, "integer(1)+3". This
-% would obviate most calls of integer().
-%
-% 5) Use double-ended lists rather than simple lists. This
-% would improve the efficiency of the division algorithm,
-% which reverse lists.
-% (djh: this is obsolete - digits lists are now in normal order)
-%
-% 6) Add bit operations (XOR, AND, OR, etc). We would treat
-% the integers as having a 2's complement bit representation.
-% This is easier to do if we use base 2^14 as mentioned above.
-% (djh: this is done: /\ \/ << >> xor \)
-%
-% 7) The implementation of `div' is slower than it need be.
-% (djh: this is much improved)
-%
-% 8) Fourier methods such as Schoenhage-Strassen and
-% multiplication via modular arithmetic are left as
-% exercises to the reader. 8^)
-%
-%
-% Of the above, 1) would have the best bang-for-buck, 5) would
-% benefit division and remainder operations quite a lot, and 3)
-% would benefit large multiplications (thousands of digits)
-% and is straightforward to implement.
-% (djh:
-% I'd like to see 1) done.
-% integers are now represented as
-% i(Length, Digits)
-% where Digits are no longer reversed.
-% The only penalty for not reversing is in multiplication
-% by the base which now entails walking to the end of the list
-% to append a 0.
-% Therefore I'd like to see:
-% 9) Allow empty tails for low end zeros.
-% Base multiplication is then an increment to Length.
-
+%-----------------------------------------------------------------------------%
:- module integer.
@@ -138,14 +79,82 @@
:- pred integer__pow(integer, integer, integer).
:- mode integer__pow(in, in, out) is det.
+:- func integer__pow(integer, integer) = integer.
:- func integer__float(integer) = float.
:- func integer__int(integer) = int.
+:- func integer__zero = integer.
+
+:- func integer__one = integer.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
:- implementation.
:- import_module require, list, char, std_util, int.
+% Possible improvements:
+%
+% 1) allow negative digits (-base+1 .. base-1) in lists of
+% digits and normalise only when printing. This would
+% probably simplify the division algorithm, also.
+% (djh: this is not really done although -ve integers include a list
+% of -ve digits for faster comparison and so that normal mercury
+% sorting produces an intuitive order)
+%
+% 2) alternatively, instead of using base=10000, use *all* the
+% bits in an int and make use of the properties of machine
+% arithmetic. Base 10000 doesn't use even half the bits
+% in an int, which is inefficient. (Base 2^14 would be
+% a little better but would require a slightly more
+% complex case conversion on reading and printing.)
+% (djh: this is done)
+%
+% 3) Use an O(n^(3/2)) algorithm for multiplying large
+% integers, rather than the current O(n^2) method.
+% There's an obvious divide-and-conquer technique,
+% Karatsuba multiplication.
+%
+% 4) We could overload operators so that we can have mixed operations
+% on ints and integers. For example, "integer(1)+3". This
+% would obviate most calls of integer().
+%
+% 5) Use double-ended lists rather than simple lists. This
+% would improve the efficiency of the division algorithm,
+% which reverse lists.
+% (djh: this is obsolete - digits lists are now in normal order)
+%
+% 6) Add bit operations (XOR, AND, OR, etc). We would treat
+% the integers as having a 2's complement bit representation.
+% This is easier to do if we use base 2^14 as mentioned above.
+% (djh: this is done: /\ \/ << >> xor \)
+%
+% 7) The implementation of `div' is slower than it need be.
+% (djh: this is much improved)
+%
+% 8) Fourier methods such as Schoenhage-Strassen and
+% multiplication via modular arithmetic are left as
+% exercises to the reader. 8^)
+%
+%
+% Of the above, 1) would have the best bang-for-buck, 5) would
+% benefit division and remainder operations quite a lot, and 3)
+% would benefit large multiplications (thousands of digits)
+% and is straightforward to implement.
+% (djh:
+% I'd like to see 1) done.
+% integers are now represented as
+% i(Length, Digits)
+% where Digits are no longer reversed.
+% The only penalty for not reversing is in multiplication
+% by the base which now entails walking to the end of the list
+% to append a 0.
+% Therefore I'd like to see:
+% 9) Allow empty tails for low end zeros.
+% Base multiplication is then an increment to Length.
+
:- type sign == int. % sign of integer and length of digit list
:- type digit == int. % base 2^14 digit
@@ -153,19 +162,31 @@
---> i(sign, list(digit)).
:- func base = int.
+
base = 16384. % 2^14
+
:- func basediv2 = int.
+
basediv2 = 8192.
:- func log2base = int.
+
log2base = 14.
+
:- func basemask = int.
+
basemask = 16383.
+
:- func highbitmask = int.
+
highbitmask = basediv2.
+
:- func lowbitmask = int.
+
lowbitmask = 1.
+
:- func evenmask = int.
+
evenmask = 16382.
'<'(X1, X2) :-
@@ -184,11 +205,9 @@
big_cmp(X1, X2) = C,
( C = (>) ; C = (=)).
-'+'(X1) =
- X1.
+'+'(X1) = X1.
-'-'(N) =
- big_neg(N).
+'-'(N) = big_neg(N).
X1 + X2 = big_plus(X1, X2).
@@ -204,27 +223,9 @@
X1 mod X2 = big_mod(X1, X2).
-X << I =
- (
- I > 0 ->
- big_left_shift(X, I)
- ;
- I < 0 ->
- X >> -I
- ;
- X
- ).
+X << I = ( I > 0 -> big_left_shift(X, I) ; I < 0 -> X >> -I ; X ).
-X >> I =
- (
- I < 0 ->
- X << -I
- ;
- I > 0 ->
- big_right_shift(X, I)
- ;
- X
- ).
+X >> I = ( I < 0 -> X << -I ; I > 0 -> big_right_shift(X, I) ; X ).
X1 /\ X2 =
(
@@ -279,16 +280,12 @@
integer__abs(N) = big_abs(N).
-
:- func big_abs(integer) = integer.
-big_abs(i(Sign, Ds)) =
- (Sign < 0 ->
- big_neg(i(Sign, Ds))
- ;
- i(Sign, Ds)
- ).
+
+big_abs(i(Sign, Ds)) = ( Sign < 0 -> big_neg(i(Sign, Ds)) ; i(Sign, Ds) ).
:- pred neg_list(list(int)::in, list(int)::out, list(int)::in) is det.
+
neg_list([]) -->
[].
neg_list([H | T]) -->
@@ -296,39 +293,41 @@
neg_list(T).
:- pred big_isnegative(integer::in) is semidet.
+
big_isnegative(i(Sign, _)) :-
Sign < 0.
:- pred big_iszero(integer::in) is semidet.
-big_iszero(i(0, [])).
+big_iszero(i(0, [])).
:- func big_neg(integer) = integer.
+
big_neg(i(S, Ds)) = i(-S, NewDs) :-
neg_list(Ds, NewDs, []).
:- func big_mul(integer, integer) = integer.
+
big_mul(I1, I2) =
big_sign(integer_signum(I1) * integer_signum(I2),
pos_mul(big_abs(I1), big_abs(I2))).
:- func big_sign(int, integer) = integer.
-big_sign(Sign, In) =
- (Sign < 0 ->
- big_neg(In)
- ;
- In
- ).
+
+big_sign(Sign, In) = ( Sign < 0 -> big_neg(In) ; In ).
:- func big_quot(integer, integer) = integer.
+
big_quot(X1, X2) = Q :-
big_quot_rem(X1, X2, Q, _R).
:- func big_rem(integer, integer) = integer.
+
big_rem(X1, X2) = R :-
big_quot_rem(X1, X2, _Q, R).
:- func big_div(integer, integer) = integer.
+
big_div(X, Y) = Div :-
big_quot_rem(X, Y, Trunc, Rem),
(integer_signum(Y) * integer_signum(Rem) < 0 ->
@@ -338,6 +337,7 @@
).
:- func big_mod(integer, integer) = integer.
+
big_mod(X, Y) = Mod :-
big_quot_rem(X, Y, _Trunc, Rem),
(integer_signum(Y) * integer_signum(Rem) < 0 ->
@@ -346,8 +346,8 @@
Mod = Rem
).
-
:- func big_right_shift(integer, int) = integer.
+
big_right_shift(X, I) =
(
big_iszero(X) ->
@@ -360,6 +360,7 @@
).
:- func pos_right_shift(integer, int) = integer.
+
pos_right_shift(i(Len, Digits), I) = Integer :-
Div = I div log2base,
(Div < Len ->
@@ -371,6 +372,7 @@
).
:- func rightshift(int, int, integer, int) = integer.
+
rightshift(_Mod, _InvMod, i(_Len, []), _Carry) = integer__zero.
rightshift(Mod, InvMod, i(Len, [H | T]), Carry) = Integer :-
(Len =< 0 ->
@@ -382,8 +384,8 @@
Integer = i(TailLen + 1, [NewH | NewTail])
).
-
:- func big_left_shift(integer, int) = integer.
+
big_left_shift(X, I) =
(
big_iszero(X) ->
@@ -395,27 +397,27 @@
pos_left_shift(X, I)
).
-
:- func pos_left_shift(integer, int) = integer.
+
pos_left_shift(i(Len, Digits), I) = Integer :-
Div = I div log2base,
Mod = I mod log2base,
NewLen = Len + Div,
leftshift(Mod, log2base - Mod, NewLen, Digits, Carry, NewDigits),
- (Carry = 0 ->
- Integer = i(NewLen, NewDigits)
+ ( Carry = 0 ->
+ Integer = i(NewLen, NewDigits)
;
Integer = i(NewLen + 1, [Carry | NewDigits])
).
-
:- pred leftshift(int::in, int::in, int::in, list(digit)::in,
- int::out, list(digit)::out) is det.
+ int::out, list(digit)::out) is det.
+
leftshift(_Mod, _InvMod, Len, [], Carry, DigitsOut) :-
Carry = 0,
zeros(Len, DigitsOut, []).
leftshift(Mod, InvMod, Len, [H | T], Carry, DigitsOut) :-
- (Len =< 0 ->
+ ( Len =< 0 ->
Carry = 0,
DigitsOut = []
;
@@ -425,6 +427,7 @@
).
:- pred zeros(int::in, list(digit)::out, list(digit)::in) is det.
+
zeros(Len) -->
({ Len > 0 } ->
[0],
@@ -434,9 +437,11 @@
).
:- func big_or(integer, integer) = integer.
+
big_or(X1, X2) = decap(or_pairs(X1, X2)).
:- func or_pairs(integer, integer) = integer.
+
or_pairs(i(L1, D1), i(L2, D2)) = Integer :-
(
L1 = L2 ->
@@ -454,16 +459,17 @@
).
:- func or_pairs_equal(list(digit), list(digit)) = list(digit).
+
or_pairs_equal([], _) = [].
or_pairs_equal([X | Xs], [Y | Ys]) = [X \/ Y | or_pairs_equal(Xs, Ys)].
or_pairs_equal([_ | _], []) = [].
-
-
:- func big_xor(integer, integer) = integer.
+
big_xor(X1, X2) = decap(xor_pairs(X1, X2)).
:- func xor_pairs(integer, integer) = integer.
+
xor_pairs(i(L1, D1), i(L2, D2)) = Integer :-
(
L1 = L2 ->
@@ -481,17 +487,18 @@
).
:- func xor_pairs_equal(list(digit), list(digit)) = list(digit).
+
xor_pairs_equal([], _) = [].
-xor_pairs_equal([X | Xs], [Y | Ys]) =
- [int__xor(X, Y) | xor_pairs_equal(Xs, Ys)].
xor_pairs_equal([_ | _], []) = [].
-
-
+xor_pairs_equal([X | Xs], [Y | Ys]) =
+ [int__xor(X, Y) | xor_pairs_equal(Xs, Ys)].
:- func big_and(integer, integer) = integer.
+
big_and(X1, X2) = decap(and_pairs(X1, X2)).
:- func and_pairs(integer, integer) = integer.
+
and_pairs(i(L1, D1), i(L2, D2)) = Integer :-
(
L1 = L2 ->
@@ -509,14 +516,17 @@
).
:- func and_pairs_equal(list(digit), list(digit)) = list(digit).
+
and_pairs_equal([], _) = [].
-and_pairs_equal([X | Xs], [Y | Ys]) = [X /\ Y | and_pairs_equal(Xs, Ys)].
and_pairs_equal([_ | _], []) = [].
+and_pairs_equal([X | Xs], [Y | Ys]) = [X /\ Y | and_pairs_equal(Xs, Ys)].
:- func big_and_not(integer, integer) = integer.
+
big_and_not(X1, X2) = decap(and_not_pairs(X1, X2)).
:- func and_not_pairs(integer, integer) = integer.
+
and_not_pairs(i(L1, D1), i(L2, D2)) = Integer :-
(
L1 = L2 ->
@@ -534,27 +544,29 @@
).
:- func and_not_pairs_equal(list(digit), list(digit)) = list(digit).
+
and_not_pairs_equal([], _) = [].
-and_not_pairs_equal([X | Xs], [Y | Ys]) =
- [X /\ \ Y | and_not_pairs_equal(Xs, Ys)].
and_not_pairs_equal([_ | _], []) = [].
-
+and_not_pairs_equal([X | Xs], [Y | Ys]) =
+ [X /\ \ Y | and_not_pairs_equal(Xs, Ys)].
:- func big_xor_not(integer, integer) = integer.
+
big_xor_not(X1, NotX2) =
\ big_and_not(big_or(X1, NotX2), big_and(X1, NotX2)).
-
:- func big_cmp(integer, integer) = comparison_result.
+
big_cmp(I1, I2) = Result :-
compare(Result, I1, I2).
-
:- func pos_cmp(integer, integer) = comparison_result.
+
pos_cmp(Xs, Ys) = Result :-
compare(Result, Xs, Ys).
:- func big_plus(integer, integer) = integer.
+
big_plus(I1, I2) = Sum :-
(
I1 = integer__zero ->
@@ -584,8 +596,7 @@
)
).
-integer(N) =
- int_to_integer(N).
+integer(N) = int_to_integer(N).
% Note: Since most machines use 2's complement arithmetic,
% INT_MIN is usually -INT_MAX-1, hence -INT_MIN will
@@ -595,7 +606,9 @@
% instead.
%
% XXX: What about machines that aren't 2's complement?
+
:- func int_to_integer(int) = integer.
+
int_to_integer(D) = Int :-
(
D = 0 ->
@@ -617,35 +630,25 @@
).
:- func shortint_to_integer(int) = integer.
-shortint_to_integer(D) =
- (
- D = 0 ->
- integer__zero
- ;
- D > 0 ->
- i(1, [D])
- ;
- i(-1, [D])
- ).
+
+shortint_to_integer(D) =
+ ( D = 0 -> integer__zero ; D > 0 -> i(1, [D]) ; i(-1, [D]) ).
:- func signum(int) = int.
-signum(N) = SN :-
- ( N < 0 ->
- SN = -1
- ; N = 0 ->
- SN = 0
- ;
- SN = 1
- ).
+
+signum(N) = ( N < 0 -> -1 ; N = 0 -> 0 ; 1 ).
:- func integer_signum(integer) = int.
+
integer_signum(i(Sign, _)) = signum(Sign).
:- func pos_int_to_digits(int) = integer.
+
pos_int_to_digits(D) =
pos_int_to_digits_2(D, integer__zero).
:- func pos_int_to_digits_2(int, integer) = integer.
+
pos_int_to_digits_2(D, Tail) = Result :-
(D = 0 ->
Result = Tail
@@ -656,6 +659,7 @@
).
:- func mul_base(integer) = integer.
+
mul_base(i(L, Ds)) = Result :-
(Ds = [] ->
Result = integer__zero
@@ -664,10 +668,12 @@
).
:- func mul_base_2(list(digit)) = list(digit).
+
mul_base_2([]) = [0].
mul_base_2([H | T]) = [H | mul_base_2(T)].
:- func mul_by_digit(digit, integer) = integer.
+
mul_by_digit(D, i(Len, Ds)) = Out :-
mul_by_digit_2(D, Mod, Ds, DsOut),
(Mod = 0 ->
@@ -676,40 +682,30 @@
Out = i(Len + 1, [Mod | DsOut])
).
-:- pred mul_by_digit_2(digit::in, digit::out,
- list(digit)::in, list(digit)::out)
- is det.
+:- pred mul_by_digit_2(digit::in, digit::out, list(digit)::in,
+ list(digit)::out) is det.
+
mul_by_digit_2(_, 0, [], []).
mul_by_digit_2(D, Div, [X | Xs], [Mod | NewXs]) :-
mul_by_digit_2(D, DivXs, Xs, NewXs),
chop(D * X + DivXs, Div, Mod).
+:- pred chop(int::in, digit::out, digit::out) is det.
-:- pred chop(int, digit, digit).
-:- mode chop(in, out, out) is det.
chop(N, Div, Mod) :-
- %Div = N div base,
- %Mod = N mod base.
Div = N >> log2base,
Mod = N /\ basemask.
:- func pos_plus(integer, integer) = integer.
+
pos_plus(i(L1, D1), i(L2, D2)) = Out :-
add_pairs(Div, i(L1, D1), i(L2, D2), Ds),
- (L1 > L2 ->
- Len = L1
- ;
- Len = L2
- ),
- (Div = 0 ->
- Out = i(Len, Ds)
- ;
- Out = i(Len + 1, [Div | Ds])
- ).
+ Len = ( L1 > L2 -> L1 ; L2 ),
+ Out = ( Div = 0 -> i(Len, Ds) ; i(Len + 1, [Div | Ds]) ).
:- pred add_pairs(digit::out, integer::in, integer::in,
- list(digit)::out)
- is det.
+ list(digit)::out) is det.
+
add_pairs(Div, i(L1, D1), i(L2, D2), Ds) :-
(
L1 = L2 ->
@@ -729,32 +725,24 @@
).
:- pred add_pairs_equal(digit::out, list(digit)::in, list(digit)::in,
- list(digit)::out)
- is det.
+ list(digit)::out) is det.
+
add_pairs_equal(0, [], _, []).
+add_pairs_equal(0, [_ | _], [], []).
add_pairs_equal(Div, [X | Xs], [Y | Ys], [Mod | TailDs]) :-
add_pairs_equal(DivTail, Xs, Ys, TailDs),
chop(X + Y + DivTail, Div, Mod).
-add_pairs_equal(0, [_ | _], [], []).
-
:- func pos_minus(integer, integer) = integer.
+
pos_minus(i(L1, D1), i(L2, D2)) = Out :-
diff_pairs(Mod, i(L1, D1), i(L2, D2), Ds),
- (L1 > L2 ->
- Len = L1
- ;
- Len = L2
- ),
- (Mod = 0 ->
- Out = decap(i(Len, Ds))
- ;
- Out = i(Len + 1, [Mod | Ds])
- ).
+ Len = ( L1 > L2 -> L1 ; L2 ),
+ Out = ( Mod = 0 -> decap(i(Len, Ds)) ; i(Len + 1, [Mod | Ds]) ).
:- pred diff_pairs(digit::out, integer::in, integer::in,
- list(digit)::out)
- is det.
+ list(digit)::out) is det.
+
diff_pairs(Div, i(L1, D1), i(L2, D2), Ds) :-
(
L1 = L2 ->
@@ -769,16 +757,16 @@
).
:- pred diff_pairs_equal(digit::out, list(digit)::in, list(digit)::in,
- list(digit)::out)
- is det.
+ list(digit)::out) is det.
+
diff_pairs_equal(0, [], _, []).
+diff_pairs_equal(0, [_ | _], [], []).
diff_pairs_equal(Div, [X | Xs], [Y | Ys], [Mod | TailDs]) :-
diff_pairs_equal(DivTail, Xs, Ys, TailDs),
chop(X - Y + DivTail, Div, Mod).
-diff_pairs_equal(0, [_ | _], [], []).
-
:- func pos_mul(integer, integer) = integer.
+
pos_mul(i(L1, Ds1), i(L2, Ds2)) =
(L1 < L2 ->
pos_mul_list(Ds1, integer__zero, i(L2, Ds2))
@@ -787,16 +775,14 @@
).
:- func pos_mul_list(list(digit), integer, integer) = integer.
+
pos_mul_list([], Carry, _Y) = Carry.
pos_mul_list([X|Xs], Carry, Y) =
pos_mul_list(Xs, pos_plus(mul_base(Carry), mul_by_digit(X, Y)), Y).
+:- pred big_quot_rem(integer::in, integer::in, integer::out,
+ integer::out) is det.
-
-
-
-:- pred big_quot_rem(integer, integer, integer, integer).
-:- mode big_quot_rem(in, in, out, out) is det.
big_quot_rem(N1, N2, Qt, Rm) :-
(
big_iszero(N2) ->
@@ -826,8 +812,9 @@
%
% [*] Knuth, Semi-numerical algorithms.
%
-:- pred quot_rem(integer, integer, integer, integer).
-:- mode quot_rem(in, in, out, out) is det.
+
+:- pred quot_rem(integer::in, integer::in, integer::out, integer::out) is det.
+
quot_rem(U, V, Qt, Rm) :-
(U = i(_, [UI]), V = i(_, [VI]) ->
Qt = shortint_to_integer(UI // VI),
@@ -846,8 +833,9 @@
Qt = decap(QtZeros)
).
-:- pred quot_rem_2(integer, integer, integer, integer, integer).
-:- mode quot_rem_2(in, in, in, out, out) is det.
+:- pred quot_rem_2(integer::in, integer::in, integer::in, integer::out,
+ integer::out) is det.
+
quot_rem_2(Ur, U, V, Qt, Rm) :-
(pos_lt(Ur, V) ->
(
@@ -892,55 +880,52 @@
).
:- func length(integer) = int.
+
length(i(L, _)) = L.
:- func decap(integer) = integer.
+
decap(i(_, [])) = integer__zero.
-decap(i(L, [H | T])) =
- (H = 0 ->
- decap(i(L - 1, T))
- ;
- i(L, [H | T])
- ).
+decap(i(L, [H | T])) = ( H = 0 -> decap(i(L - 1, T)) ; i(L, [H | T]) ).
:- func head(integer) = digit.
-head(I) = H :-
- (I = i(_, [Hd|_T]) ->
- H = Hd
- ;
- error("integer__head: []")
- ).
+
+head(I) = (I = i(_, [Hd|_T]) -> Hd ; func_error("integer__head: []") ).
:- func head_tail(integer) = digit.
-head_tail(I) = HT :-
- (I = i(_, [_ | [HT1 | _]]) ->
- HT = HT1
- ;
- error("integer__tail: []")
- ).
+
+head_tail(I) =
+ (I = i(_, [_ | [HT | _]]) ->
+ HT
+ ;
+ func_error("integer__tail: []")
+ ).
:- func tail(integer) = integer.
-tail(I) = T :-
+
+tail(I) =
(I = i(L, [_ | Tail]) ->
- T = i(L - 1, Tail)
+ i(L - 1, Tail)
;
- error("integer__tail: []")
+ func_error("integer__tail: []")
).
:- func integer_append(integer, digit) = integer.
+
integer_append(i(L, List), Digit) = i(L + 1, NewList) :-
list__append(List, [Digit], NewList).
-
:- func integer_prepend(digit, integer) = integer.
-integer_prepend(Digit, i(L, List)) = i(L + 1, [Digit | List]).
+integer_prepend(Digit, i(L, List)) = i(L + 1, [Digit | List]).
:- func div_by_digit(digit, integer) = integer.
+
div_by_digit(_D, i(_, [])) = integer__zero.
div_by_digit(D, i(_, [X|Xs])) = div_by_digit_1(X, Xs, D).
:- func div_by_digit_1(digit, list(digit), digit) = integer.
+
div_by_digit_1(X, [], D) = Integer :-
Q = X div D,
(Q = 0 ->
@@ -958,22 +943,24 @@
).
:- func div_by_digit_2(digit, list(digit), digit) = integer.
+
div_by_digit_2(X, [], D) = i(1, [X div D]).
div_by_digit_2(X, [H|T], D) = i(Len + 1, [X div D | Tail]) :-
i(Len, Tail) = div_by_digit_2((X rem D) * base + H, T, D).
+:- pred pos_lt(integer::in, integer::in) is semidet.
-:- pred pos_lt(integer, integer).
-:- mode pos_lt(in, in) is semidet.
pos_lt(Xs, Ys) :-
(<) = pos_cmp(Xs, Ys).
-:- pred pos_geq(integer, integer).
-:- mode pos_geq(in, in) is semidet.
+:- pred pos_geq(integer::in, integer::in) is semidet.
+
pos_geq(Xs, Ys) :-
C = pos_cmp(Xs, Ys),
( C = (>) ; C = (=) ).
+integer__pow(A, N) = P :-
+ integer__pow(A, N, P).
integer__pow(A, N, P) :-
( big_isnegative(N) ->
@@ -983,6 +970,7 @@
).
:- func big_pow(integer, integer) = integer.
+
big_pow(A, N) =
(
N = integer__zero ->
@@ -1004,6 +992,7 @@
).
:- func bits_pow_head(int, integer) = integer.
+
bits_pow_head(H, A) =
(
H = 0 ->
@@ -1016,11 +1005,13 @@
).
:- func bits_pow_list(list(int), integer, integer) = integer.
+
bits_pow_list([], _, Accum) = Accum.
bits_pow_list([H | T], A, Accum) =
bits_pow_list(T, A, bits_pow(log2base, H, A, Accum)).
:- func bits_pow(int, int, integer, integer) = integer.
+
bits_pow(Shifts, H, A, Accum) =
(
Shifts =< 0 ->
@@ -1032,23 +1023,19 @@
big_sqr(bits_pow(Shifts - 1, H >> 1, A, Accum))
).
-
:- func big_sqr(integer) = integer.
-big_sqr(A) = A * A.
+big_sqr(A) = A * A.
-%:- func integer__float(integer) = float.
integer__float(i(_, List)) = float_list(FBase, 0.0, List) :-
int__to_float(base, FBase).
:- func float_list(float, float, list(int)) = float.
-float_list(_, Accum, []) = Accum.
-float_list(FBase, Accum, [H | T]) =
- float_list(FBase, Accum * FBase + FH, T) :-
- int__to_float(H, FH).
+float_list(_, Accum, []) = Accum.
+float_list(FBase, Accum, [H | T]) = float_list(FBase, Accum * FBase + FH, T) :-
+ int__to_float(H, FH).
-%:- func integer__int(integer) = int.
integer__int(Integer) = Int :-
( Integer >= integer(int__min_int), Integer =< integer(int__max_int) ->
Integer = i(_Sign, List),
@@ -1057,41 +1044,39 @@
error("integer__int: domain error (conversion would overflow)")
).
-
:- func int_list(list(int), int) = int.
+
int_list([], Accum) = Accum.
int_list([H|T], Accum) = int_list(T, Accum * base + H).
-:- func integer__zero = integer.
integer__zero = i(0, []).
-:- func integer__one = integer.
integer__one = i(1, [1]).
-%===========================================================================
-% Reading
+%-----------------------------------------------------------------------------%
+%
+% Converting strings to integers.
+%
-%:- func integer__from_string(string) = integer.
-%:- mode integer__from_string(in) = out is semidet.
integer__from_string(S) = Big :-
string__to_char_list(S, Cs),
string_to_integer(Cs) = Big.
:- func string_to_integer(list(char)) = integer.
:- mode string_to_integer(in) = out is semidet.
-string_to_integer(CCs) = Result :-
- CCs = [C|Cs],
- (C = ('-') ->
- Result = big_sign(-1, string_to_integer(Cs))
+
+string_to_integer(CCs @ [C | Cs]) =
+ ( C = ('-') ->
+ big_sign(-1, string_to_integer(Cs))
;
- Result = string_to_integer_acc(CCs, integer__zero)
+ string_to_integer_acc(CCs, integer__zero)
).
-
:- func string_to_integer_acc(list(char), integer) = integer.
:- mode string_to_integer_acc(in, in) = out is semidet.
+
string_to_integer_acc([], Acc) = Acc.
-string_to_integer_acc([C|Cs], Acc) = Result :-
+string_to_integer_acc([C | Cs], Acc) = Result :-
(char__is_digit(C) ->
char__to_int(C, D1),
char__to_int('0', Z),
@@ -1102,11 +1087,11 @@
fail
).
+%-----------------------------------------------------------------------------%
+%
+% Converting integers to strings.
+%
-%===========================================================================
-% Writing
-
-%:- func integer__to_string(integer) = string.
integer__to_string(i(Sign, Ds)) = Str :-
(Sign < 0 ->
Sgn = "-",
@@ -1117,9 +1102,8 @@
),
string__append(Sgn, digits_to_string(AbsDs), Str).
-
-
:- func digits_to_string(list(digit)) = string.
+
digits_to_string(DDs) = Str :-
(DDs = [] ->
Str = "0"
@@ -1135,9 +1119,9 @@
)
).
-:- pred digits_to_strings(list(digit)::in,
- list(string)::out, list(string)::in)
- is det.
+:- pred digits_to_strings(list(digit)::in, list(string)::out,
+ list(string)::in) is det.
+
digits_to_strings([]) -->
[].
digits_to_strings([H | T]) -->
@@ -1147,37 +1131,43 @@
:- pred printbase_rep(integer::in, list(digit)::in, integer::out)
is det.
+
printbase_rep(Base, Digits, printbase_rep_1(Digits, Base, integer__zero)).
:- func printbase_rep_1(list(digit), integer, integer) = integer.
+
printbase_rep_1([], _Base, Carry) = Carry.
printbase_rep_1([X|Xs], Base, Carry) =
printbase_rep_1(Xs, Base,
printbase_pos_plus(printbase_pos_mul(Base, Carry),
printbase_pos_int_to_digits(X))).
+:- pred digit_to_string(digit::in, string::out) is det.
-:- pred digit_to_string(digit, string).
-:- mode digit_to_string(in, out) is det.
digit_to_string(D, S) :-
string__int_to_string(D, S1),
string__pad_left(S1, '0', log10printbase, S).
-
-%=========================================================
+%-----------------------------------------------------------------------------%
+%
% Essentially duplicated code to work in base `printbase' follows
+%
:- func printbase = int.
+
printbase = 10000.
:- func log10printbase = int.
+
log10printbase = 4.
:- func printbase_pos_int_to_digits(int) = integer.
-printbase_pos_int_to_digits(D) =
- printbase_pos_int_to_digits_2(D, integer__zero).
+
+printbase_pos_int_to_digits(D) =
+ printbase_pos_int_to_digits_2(D, integer__zero).
:- func printbase_pos_int_to_digits_2(int, integer) = integer.
+
printbase_pos_int_to_digits_2(D, Tail) = Result :-
(D = 0 ->
Result = Tail
@@ -1185,52 +1175,39 @@
Tail = i(Length, Digits),
printbase_chop(D, Div, Mod),
Result = printbase_pos_int_to_digits_2(Div,
- i(Length + 1, [Mod | Digits]))
+ i(Length + 1, [Mod | Digits]))
).
+:- pred printbase_chop(int::in, digit::out, digit::out) is det.
-:- pred printbase_chop(int, digit, digit).
-:- mode printbase_chop(in, out, out) is det.
printbase_chop(N, Div, Mod) :-
Mod = N mod printbase,
Div = N div printbase.
-
:- func printbase_mul_by_digit(digit, integer) = integer.
+
printbase_mul_by_digit(D, i(Len, Ds)) = Out :-
printbase_mul_by_digit_2(D, Div, Ds, DsOut),
- (Div = 0 ->
- Out = i(Len, DsOut)
- ;
- Out = i(Len + 1, [Div | DsOut])
- ).
+ Out = ( Div = 0 -> i(Len, DsOut) ; i(Len + 1, [Div | DsOut]) ).
:- pred printbase_mul_by_digit_2(digit::in, digit::out,
- list(digit)::in, list(digit)::out)
- is det.
+ list(digit)::in, list(digit)::out) is det.
+
printbase_mul_by_digit_2(_, 0, [], []).
printbase_mul_by_digit_2(D, Div, [X | Xs], [Mod | NewXs]) :-
printbase_mul_by_digit_2(D, DivXs, Xs, NewXs),
printbase_chop(D * X + DivXs, Div, Mod).
-
:- func printbase_pos_plus(integer, integer) = integer.
+
printbase_pos_plus(i(L1, D1), i(L2, D2)) = Out :-
printbase_add_pairs(Div, i(L1, D1), i(L2, D2), Ds),
- (L1 > L2 ->
- Len = L1
- ;
- Len = L2
- ),
- (Div = 0 ->
- Out = i(Len, Ds)
- ;
- Out = i(Len + 1, [Div | Ds])
- ).
+ Len = ( L1 > L2 -> L1 ; L2 ),
+ Out = ( Div = 0 -> i(Len, Ds) ; i(Len + 1, [Div | Ds]) ).
:- pred printbase_add_pairs(digit::out, integer::in, integer::in,
- list(digit)::out)
- is det.
+ list(digit)::out) is det.
+
printbase_add_pairs(Div, i(L1, D1), i(L2, D2), Ds) :-
(
L1 = L2 ->
@@ -1250,16 +1227,16 @@
).
:- pred printbase_add_pairs_equal(digit::out, list(digit)::in, list(digit)::in,
- list(digit)::out)
- is det.
+ list(digit)::out) is det.
+
printbase_add_pairs_equal(0, [], _, []).
+printbase_add_pairs_equal(0, [_ | _], [], []).
printbase_add_pairs_equal(Div, [X | Xs], [Y | Ys], [Mod | TailDs]) :-
printbase_add_pairs_equal(DivTail, Xs, Ys, TailDs),
printbase_chop(X + Y + DivTail, Div, Mod).
-printbase_add_pairs_equal(0, [_ | _], [], []).
-
:- func printbase_pos_mul(integer, integer) = integer.
+
printbase_pos_mul(i(L1, Ds1), i(L2, Ds2)) =
(L1 < L2 ->
printbase_pos_mul_list(Ds1, integer__zero, i(L2, Ds2))
@@ -1268,10 +1245,12 @@
).
:- func printbase_pos_mul_list(list(digit), integer, integer) = integer.
+
printbase_pos_mul_list([], Carry, _Y) = Carry.
printbase_pos_mul_list([X|Xs], Carry, Y) =
- printbase_pos_mul_list(Xs,
- printbase_pos_plus(mul_base(Carry),
- printbase_mul_by_digit(X, Y)),
- Y).
+ printbase_pos_mul_list(Xs, printbase_pos_plus(mul_base(Carry),
+ printbase_mul_by_digit(X, Y)), Y).
+%-----------------------------------------------------------------------------%
+:- end_module integer.
+%-----------------------------------------------------------------------------%
Index: library/rational.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/rational.m,v
retrieving revision 1.5
diff -u -r1.5 rational.m
--- library/rational.m 26 May 2003 09:00:30 -0000 1.5
+++ library/rational.m 16 Dec 2003 03:52:04 -0000
@@ -9,6 +9,8 @@
%
% Implements a rational number type and a set of basic operations on
% rational numbers.
+%
+%-----------------------------------------------------------------------------%
:- module rational.
@@ -30,10 +32,17 @@
:- pred rational:'>='(rational, rational).
:- mode rational:'>='(in, in) is semidet.
+:- func rational__rational(int) = rational.
-:- func rational(int, int) = rational.
+:- func rational__rational(int, int) = rational.
-:- func rational_from_integers(integer, integer) = rational.
+:- func rational__from_integer(integer) = rational.
+
+:- func rational__from_integers(integer, integer) = rational.
+
+ % New programs should use rational.from_integers/2.
+:- pragma obsolete(rational_from_integers/2).
+:- func rational__rational_from_integers(integer, integer) = rational.
% :- func float(rational) = float.
@@ -55,10 +64,12 @@
:- func rational__abs(rational) = rational.
-:- func one = rational.
+:- func rational__one = rational.
-:- func zero = rational.
+:- func rational__zero = rational.
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
:- implementation.
@@ -99,7 +110,13 @@
Cmp = cmp(R1, R2),
(Cmp = greaterthan ; Cmp = equal).
-rational(Num, Den) = rational_norm(integer(Num), integer(Den)).
+rational__rational(Int) = rational_norm(integer(Int), integer__one).
+
+rational__rational(Num, Den) = rational_norm(integer(Num), integer(Den)).
+
+rational__from_integer(Integer) = rational_norm(Integer, integer__one).
+
+rational__from_integers(Num, Den) = rational_norm(Num, Den).
rational_from_integers(Num, Den) = rational_norm(Num, Den).
@@ -108,88 +125,82 @@
% rational__float(r(Num, Den)) =
% float:'/'(integer__float(Num), integer__float(Den)).
-one = r(integer(1), integer(1)).
+rational__one = r(integer(1), integer(1)).
-zero = r(integer(0), integer(1)).
+rational__zero = r(integer(0), integer(1)).
rational:'+'(Rat) = Rat.
rational:'-'(r(Num, Den)) = r(-Num, Den).
rational:'+'(r(An, Ad), r(Bn, Bd)) = rational_norm(Numer, M) :-
- Numer = An * CA + Bn * CB,
M = lcm(Ad, Bd),
CA = M // Ad,
- CB = M // Bd.
+ CB = M // Bd,
+ Numer = An * CA + Bn * CB.
-rational:'-'(R1, R2) =
- R1 + (-R2).
+rational:'-'(R1, R2) = R1 + (-R2).
% XXX: need we call rational_norm here?
rational:'*'(r(An, Ad), r(Bn, Bd)) = rational_norm(Numer, Denom) :-
- Numer = (An//G1) * (Bn//G2),
- Denom = (Ad//G2) * (Bd//G1),
G1 = gcd(An, Bd),
- G2 = gcd(Ad, Bn).
+ G2 = gcd(Ad, Bn),
+ Numer = (An // G1) * (Bn // G2),
+ Denom = (Ad // G2) * (Bd // G1).
-rational:'/'(R1, R2) =
- R1 * inverse(R2).
+rational:'/'(R1, R2) = R1 * inverse(R2).
:- func inverse(rational) = rational.
-inverse(r(Num, Den)) = Rat :-
- ( Num = izero ->
- error("rational__inverse: division by zero")
+
+inverse(r(Num, Den)) =
+ ( Num = integer__zero ->
+ func_error("rational__inverse: division by zero")
;
- Rat = r(signum(Num)*Den, abs(Num))
+ r(signum(Num) * Den, integer__abs(Num))
).
rational__numer(r(Num, _)) = Num.
rational__denom(r(_, Den)) = Den.
-rational__abs(r(Num, Den)) = r(abs(Num), Den).
+rational__abs(r(Num, Den)) = r(integer__abs(Num), Den).
:- func rational_norm(integer, integer) = rational.
+
rational_norm(Num, Den) = Rat :-
- ( Den = izero ->
+ ( Den = integer__zero ->
error("rational__rational_norm: division by zero")
- ; Num = izero ->
- Rat = r(izero, ione)
+ ; Num = integer__zero ->
+ Rat = r(integer__zero, integer__one)
;
- Rat = r(Num2//G, Den2//G),
+ G = gcd(Num, Den),
Num2 = Num * signum(Den),
- Den2 = abs(Den),
- G = gcd(Num, Den)
+ Den2 = integer__abs(Den),
+ Rat = r(Num2 // G, Den2 // G)
).
:- func gcd(integer, integer) = integer.
-gcd(A, B) =
- gcd_2(abs(A), abs(B)).
+
+gcd(A, B) = gcd_2(integer__abs(A), integer__abs(B)).
:- func gcd_2(integer, integer) = integer.
-gcd_2(A, B) =
- ( B = izero -> A
- ; gcd_2(B, A rem B)
- ).
+
+gcd_2(A, B) = ( B = integer__zero -> A ; gcd_2(B, A rem B) ).
:- func lcm(integer, integer) = integer.
+
lcm(A, B) =
- ( A = izero -> izero
- ; B = izero -> izero
- ; abs((A // gcd(A, B)) * B)
+ ( A = integer__zero -> integer__zero
+ ; B = integer__zero -> integer__zero
+ ; integer__abs((A // gcd(A, B)) * B)
).
-:- func izero = integer.
-izero = integer(0).
-
-:- func ione = integer.
-ione = integer(1).
-
:- func signum(integer) = integer.
+
signum(N) =
- ( N = izero -> izero
- ; N < izero -> -ione
- ; ione
+ ( N = integer__zero -> integer__zero
+ ; N < integer__zero -> -integer__one
+ ; integer__one
).
:- type comparison
@@ -198,6 +209,7 @@
; greaterthan.
:- func cmp(rational, rational) = comparison.
+
cmp(R1, R2) = Cmp :-
Diff = R1 - R2,
( is_zero(Diff) ->
@@ -208,14 +220,15 @@
Cmp = greaterthan
).
-:- pred is_zero(rational).
-:- mode is_zero(in) is semidet.
-is_zero(r(Num, _)) :-
- Num = izero.
+:- pred is_zero(rational::in) is semidet.
+
+is_zero(r(integer__zero, _)).
+
+:- pred is_negative(rational::in) is semidet.
-:- pred is_negative(rational).
-:- mode is_negative(in) is semidet.
is_negative(r(Num, _)) :-
- Zero = izero,
- Num < Zero.
+ Num < integer__zero.
+%------------------------------------------------------------------------------%
+:- end_module rational.
+%------------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list