Integer division stuff

[woody%Romeo at cit-hamlet.arpa]

/* Tom Duff <alice!td at csvax.caltech.edu> writes */

> Pardon my flamage,

  That's all right, I have a fire extinguisher :-)

[ commenting on note that (-a)/b == -(a/b) is wrong ]
> Wrong!  That's the definition.  It can't be incorrect.  It might be
> different from what a number theorist wants, but by no stretch of the
> imagination can it be called incorrect.

*** long math discussion warning! ***

  It is true that for all real numbers x and y, (-x)/y == -(x/y).  This is
a natural consequence of the fact that when you take x and divide it by
y, you get a result that is a real.  And since we have the distributive
property on addition and multiplication:

  (-x)/y = (0-x)/y = (0/y) - (x/y) = 0 - (x/y) = -(x/y).

  But with integers, you do have a problem which throws the whole ball of wax
into disarray:  it is NOT true that for all integers x and y, the result
x/y is an integer.  (Say, x = 1 and y = 2.  1/2 is not an integer.)  Thus,
WE ARE NOT GUARENTEED THAT (-x)/y == -(x/y), if x and y are integers.
The reason why is that if we restrict our thinking to integers, the quantity
(x/y) may not even be defined.  [We're talking about integers now.]

  Since we don't have real division on integers (meaning that for integers
x and y,  c = x .DIV. y doesn't guarentee c * y == x), we must come up with
something useful.  So, we come up with this thing called integer division,
which mirrors closely division on reals (or rationals), and we do this by
rounding off the result of x/y (as reals) to a convenient integer.
  But which way do we round?  Well, we could (as they do in abstract algaebra)
define
          c = x / y   iff  there exists r such that
     (1)  0 < r <= y
and  (2)  c * y + r == x

  which gives us one way to round off (and as a natural consequence, has some
real nifty properties which allow us to [as an example] figure out nice
encryption algorithms, discover the minimal number of steps to take to
go from one place to another in a circular linked list, or how far to
move a line pointer in a text editor forwards (or backwards) in an array
so that some particular word lands on the screen.)
  We could also, on the other hand, define

         c = x / y  such that   (-x)/y = -(x/y)

  which gives us another way to round off.
  (For the record, I can't think of any useful things you would want to
do with integers using the second property that you really should do with
real numbers instead.)

*** end long math discussion warning ***

>>Whether CS people should even be *allowed* to make such mathematical 
>>decisions is another question.  In C on UNIX, for example, one has
>>log(-x) == log(x)....
> This sort of nonsense makes me wonder whether the writer should be allowed
> to make *any* sort of decision at all

  You know, I once believed (before I got to Caltech) that discussions about
language definitions and errors took place without personal insults, or
insulting those about them.  *sigh*  Now I know better.

> No plausable definition of the log function will let you use it to take
> cube roots of arbitrary reals in this manner

  Of course not, but shouldn't the program at least give you some sort of
"Illegal function call" or "Illegal data value" error when you give it a
negative number?  It'd sure make debugging code easier (for when you 
accidently pass a negative number when you didn't want to).

> On a higher level of discourse, this writer (Matthew P Whiner) seems to
> think that mathematicians enjoy some sort of moral and intellectual
> superiority to engineers and computer scientists.  Usually, this attitude
> is a symtom of envy, since mathematicians are so hard to employ, and have
> a hard time raising grant money.

  Two comments:
  (1) Mathematicians have been dreaming about these sort of things for a long
time; what mathematicians have to say is more or less self-consistant.  More
self-consistant than saying (-x/y) = -(x/y) without remembering that this
works only for reals, and must be expressly defined for it to work for 
integers.
  (2) About that inferiority complex thing you mentioned:  Pfffffffft!

> It is better to remain silent and be thought a fool than to speak up
> and remove all doubt.

  I may be a fool for trying to clear up some factual errors, but at least
I'm havin' fun.     ;-)

         - William Woody
           A satisfied mathematician/computer science type.
      NET  WOODY%ROMEO at HAMLET.CALTECH.EDU
   USMAIL  1-54 Lloyd; Caltech
           Pasadena, CA 91126