[comp.lang.c] modulo/remainder: it's all division

dgh@validgh.com (David G. Hough on validgh) (09/02/90)

As should be clear from reading the "MOD-function , comments needed!"
thread, there's a fair bit of confusion about these issues.   They all
really boil down to: how should x/y be defined when x and y are
integers, not necessarily positive?

In general what we want from a mod-like or remainder-like function is
that if m = mod(x,y) then x and m differ by an integral multiple of y,
and among the infinite such m, we'd normally want one of the smallest
magnitude but of appropriate sign.  There's three schools of thought
that, if not correct, can at least be self-consistent; note that x, y,
and m need not be integral; they all satisfy m = x - y * (integral
value rounded from x/y) :

what I call MATHEMATICAL m = mod(x,y)
	x/y is rounded toward negative infinity to an integral value
	the sign of m agrees with the sign of y 
	|m| < |y| 
	roundoff must occur for some floating-point x and y

what I call ARITHMETIC m = mod(x,y)
	x/y is rounded toward zero to an integral value 
	the sign of m agrees with the sign of x 
	|m| < |y| and |m| <= |x| 
	no roundoff need occur in floating-point arithmetic

what I call IEEE 754 m = mod(x,y)
	x/y is rounded to the nearest integral value, halfway cases are
		rounded to even 
	the sign of m need not agree with either x or y 
	|m| < 0.5*|y| and |m| <= |x| 
	no roundoff need occur in floating-point arithmetic

[y = 0 or infinity require special consideration because x/y does.]

I suspect that as a practical matter negative moduli y
are extremely rare and the thought that has gone into various arguments
about what to do about them was not well spent.

Hardware should implement the second or third alternative to avoid
roundoff error in floating-point computations.

Program language committees have goofed things up in various ways.  The
definition of integral division and mod should be consistent and
defined for all x and y.

A defensive programmer would have to assume that goofiness will
continue to occur, however.   To be really maximally portably
defensive, never use a negative x or y as arguments;  then check the
sign of the answer you get to see if it's right for what you want to
do.  Add +y or -y to switch the sign as needed.  All this defensiveness
is expensive, however.

The third (IEEE 754) alternative is designed to return the smallest
possible magnitude result, which is what is desired in argument range
reduction in elementary transcendental functions.   But nowadays not
too many people would be satisfied with storage-precision range
reduction (e.g. computed 53-bit sin/cos/tan with only a 53-bit
approximation to pi) so I would say that particular argument for IEEE
remainder has outlived its usefulness, and an arithmetic-style
remainder would be just as meritorious.   Neither can be justified as
single floating-point op codes on a RISC architecture because the
worst-case execution time is too long - hundreds or thousands of cycles
- and these instructions aren't used often enough.

There are lots of codes in number theory (some with considerable
Federal funding) that depend a lot on integer remainder/mod type
operations that definitely benefit from instruction set support.
-- 

David Hough

dgh@validgh.com		uunet!validgh!dgh	na.hough@na-net.stanford.edu