changes to integer division & remainder

[Fergus Henderson]

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.