Re: Constant divisions, remainders

torbenm@diku.dk (Torben AEgidius Mogensen) writes:
>I think the round-to-zero rule for div and signed mod are relics from ones
>complement computers, and should be laid to rest.


henry@zoo.toronto.edu (Henry Spencer) writes:
|> Actually, I seem to recall that it is specifically a relic of FORTRAN,
|> which made a fairly arbitrary decision for the sake of well-defined
|> behavior, and has been too influential for machine designers to ignore
|> ever since.


Probably not. Truncation toward zero is the simplest rule when you're
using singed-magnitude arithmetic. Since most floating- point is signed
magnitude, and since many implementations - even today - use the
floating-point instructions to perform their integer divide.


There are actually several different divide functions which are useful.
It would be nice if all were supported. There are so many because
integers, and even integers modulo a power of two, do not form a quotient
ring. This means that divide on the integers is inherently inexact. To
give a formal meaning to divide, you must make some choices.


      Definitions:


          |i| is the absolute value function.


          sign(i) = 0 if i==0; i/|i| otherwise.


      Divides:


          floor(n,d) = max integer k <= n/d
          ceiling(n,d) = min integer >= n/d
          trunc(n,d) = floor(|n|,|d|) * sign(n) * sign(d)
          round(n,d) = largest integer k for which |k-n/d| <= 1/2
          mdiv(n,d) = floor(n,d) if d is positive, ceiling(n,d) otherwise


These are *some* of the divide operations that might be useful. The first
four (floor, ceiling, trunc, and round) are quite common. I put in the
last one (mdiv) since it is the one which corresponds to the version of
the mod function which mathematicians like (where the answer is always
positive). Speaking of which, all of these division functions correspond
to a different remainder function:


          rem(n,d) = n - divide(n,d) * d


Where `divide' is whatever form of division you decide to select. If you
use mdiv() from above as your divide, then the rem() function is the
mathematical modulus. Whichever divide you choose to support, the
corresponding remainder function should be available as well - and
vice-versa.


To be honest, I find floor() to be the most natural division rule.
--
J. Giles
--

Return to the comp.compilers page.
Search the comp.compilers archives again.