changes to integer division & remainder

Fergus Henderson fjh at cs.mu.oz.au
Wed Mar 19 07:58:19 AEDT 1997


Hi Tom,

Can you please review this diff?

(I haven't committed it yet.  There doesn't seem to be any ordering of
commits that would allow this to bootstrap automatically, so I think
I'll have to handle it manually.)

-----------------------------------------------------------------------------

Clean up the handlng of integer division and remainder.

library/int.m:
	Add a new function `div'.  The idea is that `div' is the same
	as `//', except that `div' will round toward minus infinity, whereas
	`//' will round toward zero.  `div' is more well-behaved, `//'
	is more efficient.

	Change the behaviour of `mod' so that it is remainder after `div'
	rather than remainder after `//'.  This makes it more well-behaved,
	but less efficient.

	Add a new function `rem', which is the new name for what `mod'
	used to do (i.e. remainder after `//').

compiler/llds.m:
	Add some comments about the `/' and `mod' llds operators.
	(The `mod' llds operator should probably be renamed `rem',
	but I haven't done that yet.)

compiler/code_util.m:
	Recognize `int:rem', rather than `int:mod', as the llds `mod'
	operator.

tests/hard_coded/division_test.m:
	Add some test cases for `div', `mod', `//', and `rem' on
	negative numbers.


--- int.m	Sat Mar  1 01:25:52 1997
+++ int.m.new	Wed Mar  5 01:07:08 1997
@@ -84,16 +84,30 @@
 :- mode uo  - in  = in  is det.
 :- mode in  - uo  = in  is det.
 
-	% modulus (or is it remainder?)
-:- func int mod int = int.
-:- mode in  mod in  = uo  is det.
+	% flooring integer division
+	% truncates towards minus infinity, e.g. (-10) // 3 = (-4).
+:- func div(int, int) = int.
+:- mode div(in, in) = uo is det.
 
 	% truncating integer division
-	% should truncate toward zero
-	% (if it doesn't, file a bug report)
+	% truncates towards zero, e.g. (-10) // 3 = (-3).
+	% `div' has nicer mathematical properties for negative operands,
+	% but `//' is typically more efficient.
 :- func int // int = int.
 :- mode in  // in  = uo  is det.
 
+	% modulus
+	% X mod Y = X - (X div Y) * Y
+:- func int mod int = int.
+:- mode in  mod in  = uo  is det.
+
+	% remainder
+	% X rem Y = X - (X // Y) * Y
+	% `mod' has nicer mathematical properties for negative X,
+	% but `rem' is typically more efficient.
+:- func int rem int = int.
+:- mode in rem in = uo is det.
+
 	% left shift
 :- func int << int = int.
 :- mode in  << in  = uo  is det.
@@ -192,8 +206,20 @@
 :- implementation.
 :- import_module require.
 
-% The arithmetic and comparison operators are recognized by
+% Most of the arithmetic and comparison operators are recognized by
 % the compiler as builtins, so we don't need to define them here.
+
+X div Y = Div :-
+	Trunc = X // Y,
+	(if X // Y >= 0 then
+		Div = Trunc
+	else if X rem Y = 0 then
+		Div = Trunc
+	else
+		Div = Trunc - 1
+	).
+
+X mod Y = X - (X div Y) * Y.
 
 int__abs(Num, Abs) :-
 	(
Index: compiler/code_util.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/code_util.m,v
retrieving revision 1.83
diff -u -r1.83 code_util.m
--- code_util.m	1997/03/18 13:49:59	1.83
+++ code_util.m	1997/03/18 13:50:57
@@ -407,7 +407,7 @@
 	no, yes(Y - binop((/), var(X), var(Z)))).
 code_util__translate_builtin_2("int", "builtin_mod", 10000, [X, Y, Z],
 	no, yes(Z - binop((mod), var(X), var(Y)))).
-code_util__translate_builtin_2("int", "mod", 10000, [X, Y, Z],
+code_util__translate_builtin_2("int", "rem", 10000, [X, Y, Z],
 	no, yes(Z - binop((mod), var(X), var(Y)))).
 code_util__translate_builtin_2("int", "builtin_left_shift", 10000, [X, Y, Z],
 	no, yes(Z - binop((<<), var(X), var(Y)))).
Index: compiler/llds.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/llds.m,v
retrieving revision 1.202
diff -u -r1.202 llds.m
--- llds.m	1997/03/06 05:09:16	1.202
+++ llds.m	1997/03/16 05:14:51
@@ -413,8 +413,10 @@
 	--->	(+)	% integer arithmetic
 	;	(-)
 	;	(*)
-	;	(/)
-	;	(mod)
+	;	(/)	% integer division
+			% assumed to truncate toward zero
+	;	(mod)	% remainder (w.r.t. truncating integer division)
+			% XXX `mod' should be renamed `rem'
 	;	(<<)	% left shift
 	;	(>>)	% right shift
 	;	(&)	% bitwise and
-----------------------------------------------------------------------------
tests/hard_coded/division_test.m
-----------------------------------------------------------------------------
% test the handling of `//', rem, div, and mod.
% the first pair should truncate towards zero.
% the second pair should truncate towards negative infinity.

:- module division_test.
:- interface.
:- import_module io.

:- pred main(io__state::di, io__state::uo) is det.

:- implementation.
:- import_module int.

main -->
	(
		{ quot_test(7, 2, 3, 1) },		% 7 / 2 = 3 + 1/2
		{ quot_test(100, 13, 7, 9) }		% 100 / 13 = 7 + 9/13
	->
		io__write_string("`//' test succeeded\n")
	;
		io__write_string("`//' test failed\n")
	),
	(
		{ rem_test(7, 2, 3, 1) },		% 7 / 2 = 3 + 1/2
		{ rem_test(100, 13, 7, 9) }		% 100 / 13 = 7 + 9/13
	->
		io__write_string("rem test succeeded\n")
	;
		io__write_string("rem test failed\n")
	),
	(
		{ div_test(7, 2, 3, 1) },		% 7 / 2 = 3 + 1/2
		{ div_test(100, 13, 7, 9) }		% 100 / 13 = 7 + 9/13
	->
		io__write_string("div test succeeded\n")
	;
		io__write_string("div test failed\n")
	),
	(
		{ mod_test(7, 2, 3, 1) },		% 7 / 2 = 3 + 1/2
		{ mod_test(100, 13, 7, 9) }		% 100 / 13 = 7 + 9/13
	->
		io__write_string("mod test succeeded\n")
	;
		io__write_string("mod test failed\n")
	).

:- pred quot_test(int::in, int::in, int::in, int::in) is semidet.
quot_test(Num, Div, Quot, _Rem) :-
	Num // Div = Quot,
	(-Num) // Div = -Quot,
	(-Num) // (-Div) = Quot,
	Num // (-Div) = -Quot.

:- pred rem_test(int::in, int::in, int::in, int::in) is semidet.
rem_test(Num, Div, _Quot, Rem) :-
	Num rem Div = Rem,
	(-Num) rem Div = -Rem,
	(-Num) rem (-Div) = -Rem,
	Num rem (-Div) = Rem.

:- pred div_test(int::in, int::in, int::in, int::in) is semidet.
div_test(Num, Div, Quot, _Rem) :-
	Num // Div = Quot,
	(-Num) // Div = -Quot - 1,
	(-Num) // (-Div) = Quot,
	Num // (-Div) = -Quot - 1.

:- pred mod_test(int::in, int::in, int::in, int::in) is semidet.
mod_test(Num, Div, _Quot, Rem) :-
	Num mod Div = Rem,
	(-Num) mod Div = Num - Rem,
	(-Num) mod (-Div) = Rem,
	Num mod (-Div) = Num - Rem.
-----------------------------------------------------------------------------
tests/hard_coded/division_test.exp
-----------------------------------------------------------------------------
`//' test succeeded
rem test succeeded
div test succeeded
mod test succeeded
-----------------------------------------------------------------------------

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.



More information about the developers mailing list