Modulo of negative numbers (2011)

https://torstencurdt.com/tech/posts/modulo-of-negative-numbers/

by rbanffy • 3 years ago

55 46 3 years ago

rurban• 3 years ago

perl started this bizarre interpretation of mod, some followed. The rest stayed with the POSIX libc definition.

gerikson• 3 years ago

According to the Wikipedia page (linked in the article), Perl uses the floored definition of mod, which is promoted by Knuth, and also used by APL, Fortran and Common Lisp.

https://en.wikipedia.org/wiki/Modulo

kevin_thibedeau• 3 years ago

Ada had both before Perl existed.

alphazard• 3 years ago

This is mostly just an issue of calling what is really a remainder operator "mod".

The clearest solution is to disambiguate the two as Zig does.

Aardwolf3• 3 years ago

The one that returns a negative value for negative first argument has never done anything useful for me, and always made things that are actually useful harder to do.

The only useful behavior is that crossing 0 does not change the pattern. Change my mind.

Skeime2• 3 years ago

But it’s faster! Don’t you prefer a solution that is correct half the time over a slow solution that is correct all the time?

Aardwolf3• 3 years ago

Is it really faster? If you want to modulo with powers of 2, you can use bit-and with a power of two minus 1, that has the good behavior and is definitely faster than what the one outputting negative values does.

Or do you mean if based on integer division? I don't know what is fastest to implement in hardware for that one to be honest.

thaumasiotes3• 3 years ago

All of them are correct. There isn't a language in the table that will give you false information.

ajuc• 3 years ago

Same. Imagine we defined substraction in a way that requires almost all the users to check if arguments are positive. It's insane.

plasticeagle• 3 years ago

I know this is a typo, but I'm imagining that substraction is a form of abstraction where you take things away to make them simpler to understand.

nh23423fefe5• 3 years ago

I could imagine 2 use cases

divMod is for when you want Z_n, you actually care about the equivalence classes and their "canonical" representative.

quotRem is for symmetry. The values of the remainders are the same, but you get some sign flip for free if you want it.

So for example. Suppose you had some number of hours and you wanted to "convert to days", if you want symmetric outputs then quotRem will do that and divMod won't.

     36 hours divMod  24(hours/day) =  1d + 12h
    -36 hours divMod  24(hours/day) = -2d + 12h
     36 hours quotRem 24(hours/day) =  1d + 12h
    -36 hours quotRem 24(hours/day) = -1d - 12h

obviously the information is the same. 12 = -12 (mod 24) but the form is different.

Chinjut• 3 years ago

When do you ever want that symmetry?

thaumasiotes3• 3 years ago

Your terminology is a little weird. The idea that 0 <= remainder < divisor is part of the Division Algorithm, not modular arithmetic. And modular arithmetic, unlike remainders, is completely fine with negative numbers. But you're calling the function that gives you a correct remainder "divMod" and the one that only holds itself to modular equivalence "quotRem".

If you divide -13 by 3, the "quotient" is -5 and the "remainder" is 2.

croes• 3 years ago

Shouldn't be (x \ y) * y + (x mod y) = x?

With \ as integer division

rightbyte2• 3 years ago

The four different integer mod types gives me a headache. I just can't understand them or remember the difference.

I solve the problem by never using mod or division for that matter with negative numbers.

nh23423fefe5• 3 years ago

It's easy to remember if you apply the operation to whole number line instead of trying to remember the cases.

There are only 2 cases either you truncate to zero or you floor to negative infinity.

The zero behavior breaks the symmetry to help remember.

    n * truncate(a/n) + rem(a,n) = a
    n * floor(a/n) + mod(a,n) = a

Now suppose that "a" is any real, a/n shared by both. however truncate and floor will do different things to the negatives.

    truncate "moves" numbers to zero
    ..............................................................
    >>.>>.>>.>>.>>.>>.>>.>>.>>.>>0<<.<<.<<.<<.<<.<<.<<.<<.<<.<<.<<

    while floor "moves" number to -inf
    ..............................................................
    <<.<<.<<.<<.<<.<<.<<.<<.<<.<<0<<.<<.<<.<<.<<.<<.<<.<<.<<.<<.<<

when we then multiply by n its clear the positive "a" is the same however for negative a floor < truncate and so mod is positive while rem is negative

    for a < 0 : floor (a/n) < truncate(a/n) unless n divides a then they are =

The other case is for negative n, but that just flips the division and multiplication twice which has the effect of changing floor to ceiling and truncate to zero be truncate away from zero which flips the mod sign, but leaves rem alone, because its symmetric about zero.

Groxx• 3 years ago

There are only two cases... except when there are four, as the article covers. With wildly different conclusions by different languages, so there is no one interpretation / sane mental model that can be applied.

Mod is "fun". I agree, I simply avoid negative numbers entirely, and handle them more explicitly when needed. That way it's language independent.

FabHK• 3 years ago

Julia has functions divrem and fldmod that each return the quotient and remainder, with one or the other convention.

michae2• 3 years ago

Scheme also distinguishes between the cases using separate remainder and modulo functions.

https://www.scheme.com/tspl4/objects.html#./objects:s98

nayuki• 3 years ago

Rust has x.rem_euclid(y), which differs from the % operator. See https://doc.rust-lang.org/std/primitive.i32.html#method.rem_... .

Full demo: https://play.rust-lang.org/?version=stable&mode=debug&editio...

Haskell has separate mod and rem functions too.

Above and below the heading "Even or Odd", the <pre> blocks suffer from "scrollbar blindness" on Windows. https://web.archive.org/web/20200827132812/https://svenkadak...

orlp2• 3 years ago

Rust's rem_euclid is still wrong for negative moduli. To see why, remember that we want n = remainder + quotient * divisor. Now look at the horrible mess that is div_euclid:

In other words, the result is self / rhs rounded to the integer q such that self >= q * rhs. If self > 0, this is equal to round towards zero (the default in Rust); if self < 0, this is equal to round towards +/- infinity.

Python gets it right. Division is simply flooring division, and modulo is defined to satisfy n = remainder + quotient * divisor. That immediately gets you all the nice behavior such as (-1) % 10 = 9, and 1 % -10 = -9.

nextaccountic2• 3 years ago

Can you clarify why is Rust's div_euclid and rem_euclid are incorrect? For reference, here's what Rust prints for this https://play.rust-lang.org/?version=stable&mode=debug&editio...

    fn main() {
        dbg!(1_i32.rem_euclid(-10));
        dbg!(-1_i32.rem_euclid(10));    
    }

    [src/main.rs:2] 1_i32.rem_euclid(-10) = 1
    [src/main.rs:3] -1_i32.rem_euclid(10) = -1

I found only this issue https://github.com/rust-lang/rust/issues/87970 but has no details

Here's the discussion that lead to the implementation of those functions, from more recent to least recent,

* the tracking issue https://github.com/rust-lang/rust/issues/49048

* the RFC https://github.com/rust-lang/rfcs/pull/2169

* the internals discussion https://internals.rust-lang.org/t/mathematical-modulo-operat...

It's baffling that Rust got this wrong..

hyperthesis• 3 years ago

I've been using this style, in TFA as

  ((a % b) + b) % b

It feels like there should be a nicer way (apart from the conditional one), but I can't think of it. Can you prove there isn't one?

layer8• 3 years ago

Just as a caveat, ((a % b) + b) can overflow. For example, with 32-bit signed integer arithmetic, mod(1000000000, 2000000000) using that formula will yield -1294967296 instead of 1000000000.

klabb3• 3 years ago

It may also be expensive, since % has the cost of division, and there are two of them..

wolfi1• 3 years ago

-2 and 1 are mod 3 essentially the same. I don't see here the problem except of course someone didn't expect this result and used it for indexing

qsort• 3 years ago

Sure, but then why if:

  -13 \equiv 5 \pmod 3

it is the case that:

  > -13 % 3 === 5 % 3
  false

I think it's better to use a convention where for all a, b, m, if a and b are congruent mod m, then a%m === b%m

bajsejohannes• 3 years ago

But 13 is also equivalent to -2 and 1, mod 3. Why are you doing the modulo operation in the first place?

From a mathematical standpoint, I've never seen a use for returning -2 here. I want something unique for the group, so I can ask e.g. `x mod 3 == y mod 3` and have it work regardless of whether x or/and y are negative.

jhncls• 3 years ago

Your safest bet would be `(x - y) mod 3 == 0`. Of course, that doesn't solve the case when you want to bin the values.

whoomp12342• 3 years ago

why would we have any different behavior from division? seems like some languages got it wrong

Modulo of negative numbers (2011)

Related Stories