knapjack

Not really, but all the talk about Singularity got me poking around
and I came across this:

------

How are the functions DIV and MOD defined?

The following answers are given by the Internal Working Document on
the Common Language Infrastructure (CLI).

result = value1 DIV value2 satisfies the following conditions:
|result| = |value1| / |value2|, and
sign(result) = +, if sign(value1) = sign(value2)
sign(result) = - , if sign(value1) # sign(value2)

result = value1 MOD value2 satisfies the following conditions:
result = value1 - value2 * (value1 DIV value2), and
0 <= |result| < |value2|, and
sign(result) = sign(value1)

Please note that this definition of DIV and MOD differs from the
definition given in [M. Reiser, N. Wirth. Programming in Oberon. p.
36]:
x = (x DIV y) * y + (x MOD y), and
0 <= (x MOD y) < y

( from http://www.bluebottle.ethz.ch/oberon...html#ad_DivMod )

------

I kind of collect random, older computer science texts, so I cracked
open The Nature of Computation by Pohl and Shaw, which yields:

"x MOD y = x - (x ÷ y) * y, where ÷ indicates integer division (i.e..
fractions are disregarded; equivalently, the result of the division is
truncated)."

So, what *is* -5 MOD 3?

-Jack

cross

Well, in general, it depends.

Do you care whether the result a set or an integer? The definitions due
to Wirth et al are the former, while the MS definition appears to be the
latter.

Regardless, all these definitions are problematic. No where does it say
they're defined only on Z*; what if Y is 0?

- Dan C.

cross

Hmm, I guess on further reflection I ought to explain what I mean by
this before someone jumps all over me.

The definition as per Wirth et al gives you a positive generator for an
equivalence class on Z, whereas the microsoft definition gives you the
definition of the division function extended to all of Z, which yields
an integer; the former definition is probably more comfortable for a
mathematician, and more what one would expect. The latter is more
comfortable for someone who just wants to write a program. In neither
case does this have much to do with the actual implementation (that is
to say, it's not like DIV actually gives you back an object
representing the set of all integers congruent to 0 modulo some integer
in Pascal), but only how that language interprets the definitions.


This is still a problem. You really want a function f: Z x Z* -> Z,
not f: Z x Z -> Z; that is, for f(x, y) = x div y, y should be non-zero.
Otherwise, it would be an absurdity.

- Dan C.

cross

Are you sure? It looks to me more than it'd be +1. Wirth's definition
above would tend to indicate that x MOD y is always positive, unless I'm
reading it wrong, or that's not the whole story (and I confess I'm too
lazy to look up the definitions in context). If I'm right, that would
also imply that x DIV y tends more wards negative infinity than zero
for negative numerators.

- Dan C.

blstuart

In message <20051216050830.GE15067@augusta.math.psu.edu>, Dan Cross writes:


This also matches Knuth's in Vol 1. He states it as:

x mod y = x - y * floor( x / y )

and then observes that the mod follows the sign of y and that
the magnitude of the mod is strictly less than that of y.

Brian L. Stuart

bruce.ellis

any C standard since forever has stated clearly that the


On 12/16/05, Dan Cross <cross@math.psu.edu> wrote:

cross

This has nothing to do with it. You're looking for a single definitive
definition of something that has no single definitive definition.


Well, one would hope so! But then you have to wonder why `size' would
have occasion to be negative in such an example. And even if it was,
why you couldn't work with absolute values and keep track of the signs
yourself. Like what Bruce said.


n-bit binary *integers* are members of Z (where Z is the set of all
integers: their representation doesn't matter). But that's beside the
point. In either case, you will get a single value back. The question
is whether that value represents a congruence class or a single integer.
If you restrict your domain to non-negative integers, in this context,
it doesn't matter; you get something that's more or less the same thing
for your purposes. If you allow negative integers, that's when the
differences become significant. As Bruce said, I think it best to avoid the situation.

Well, at least one compiler is sane.

- Dan C.

brantley

0 <= (x MOD y) < y or y < (x MOD y) <= 0

-- `Programming in Oberon,' M. Reiser and N. Wirth, Page 36.
(which is available as a pdf from the web)

bruce.ellis

Sorry - I thought we were talking about C. Does plan9 have an
Oberon environment these days?

brucee

rsc

Actually, they were talking about Microsoft's CLI and Oberon.
You're the one who brought up C.

Russ