[ruby-talk:14823] Re: Integer division oddness

"Mike T. Miller" <[e-mail]> writes:

>In partial answer to my own post, I just found this
>link: http://xenia.media.mit.edu/~bdenckla/thesis/texts/htthe/node13.html

>It still seems wrong to me.  Which is right? -1 or -2?
>I guess it boils down to whether or not you believe that the
>modulus can be negative.

As has been pointed out earlier by Ben, it depends.
If you talk to language designers they would say both are right.
If you talk to a mathematician she would say -2 is right.

To fully answer the question about '%' you have to look at the other side of
the coin at its sibling operation '/' .

No matter what language you use the following should -always- hold:

            x == y(x/y) + x%y

and hence x%y will always be x - y(x/y)

Language designers choose the behavior of '%' in conjunction with what they
want '/' to mean.  When the signs of x and y are the same there is no
ambiguity about x/y.  But what about when they differ?

 -10/3  == -3.3333333

Which way do you convert to an integer?

Mathematicians would take the 'floor' function --- floor(n) is the largest
integer < n.  floor(3.9) = 3 floor(-3.2) = -4.  While most earlier language
implementors would truncate.

Over the ages, mathematicians haven't worried too much about efficiency ;-).
As it turns out calculating the floor is a little bit more expensive than
just truncating the fractional part.

[Intuitively when you take the 'floor' you move left on the number line to
the first integer.  When truncation you move towards 0.]

Hence most programming languages have defined x/y as truncating.
Consequentially -10 % 9 becomes -1 in such languages.  In such languages '%'
should really be called the remainder operation (K&R still calls it
'modulus' while Java has made the right choice in calling it 'remainder').

As Matju points out, for just about all Math applications you really need
the true 'modulo' operation. Which a Math person would explicitly define
such that: 

            x == y*floor(x/y) + x%y   [/ being real division]

[I've got a 'true_mod' defined in my private C library defined in a manner
similar to Ruby's definition]

The above equation using 'floor' can be generalized to all numbers, not just
integers as in C/Java.  Scheme and  Common Lisp are two other languages that
have had it right for quite some time.

Regards,

Raja