Modulo operator produces incorrect results with negative operand(s).

classic Classic list List threaded Threaded
21 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Modulo operator produces incorrect results with negative operand(s).

Milo Christiansen
In Lua 5.3 "-3%5 == 2", according to my programmers calculator and several other programing languages I tried this expression in, the real result is -3.

On the other hand "5%-3 == 2", so maybe the result is correct, and the bug is simply reversed operands if one is negative?

I discovered this because I am adding tests (based on the official Lua tests) to my Go Lua VM, and one of the tests failed because the incorrect result is coded into the test.
Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Soni "They/Them" L.
On 24/01/17 09:21 PM, Milo Christiansen wrote:

> In Lua 5.3 "-3%5 == 2", according to my programmers calculator and
> several other programing languages I tried this expression in, the
> real result is -3.
>
> On the other hand "5%-3 == 2", so maybe the result is correct, and the
> bug is simply reversed operands if one is negative?
>
> I discovered this because I am adding tests (based on the official Lua
> tests) to my Go Lua VM, and one of the tests failed because the
> incorrect result is coded into the test.

First of all your modulo is not my modulo (or at least this was a thing
back in C89... looks like it isn't in C99+).

Secondly, -3%5 == 2 because floor(-3/5) = -1, and (-1)*5+2 = -5+2 = -3.

See also:

https://www.microsoft.com/en-us/research/publication/division-and-modulus-for-computer-scientists/

http://hisham.hm/2015/04/18/a-small-practical-example-where-luas-behavior-is-better-than-cs/

https://github.com/sp614x/optifine/issues/288

etc. This is an endless argument.

Thirdly, in case you're still reading this for some unknown reason, RTFM
always applies:

http://www.lua.org/manual/5.3/manual.html#3.4.1

"Modulo is defined as the remainder of a division that rounds the
quotient towards minus infinity (floor division)."

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.


Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Rain Gloom
In reply to this post by Milo Christiansen
The choice of sign seems to vary pretty widely, so IMHO portable code should not depend on it. Since Lua has implementations in many languages and aims to be fast it would be an unreasonable tradeoff to make the underlying operation conform to the original C implementation. Modulo is already among the slower operations, so the extra overhead is not necessarily worth it.

On Tue, Jan 24, 2017 at 11:21 PM, Milo Christiansen <[hidden email]> wrote:
In Lua 5.3 "-3%5 == 2", according to my programmers calculator and several other programing languages I tried this expression in, the real result is -3.

On the other hand "5%-3 == 2", so maybe the result is correct, and the bug is simply reversed operands if one is negative?

I discovered this because I am adding tests (based on the official Lua tests) to my Go Lua VM, and one of the tests failed because the incorrect result is coded into the test.

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Milo Christiansen
In reply to this post by Soni "They/Them" L.
Hmmm... So why does my programmers calculator, Go, JavaScript, etc, etc all return -3 in this case?

Personally I think it's a bug, as "2" is not the correct result for that expression (in any language but Lua it seems).

On Tue, Jan 24, 2017 at 6:40 PM, Soni L. <[hidden email]> wrote:
On 24/01/17 09:21 PM, Milo Christiansen wrote:
In Lua 5.3 "-3%5 == 2", according to my programmers calculator and several other programing languages I tried this expression in, the real result is -3.

On the other hand "5%-3 == 2", so maybe the result is correct, and the bug is simply reversed operands if one is negative?

I discovered this because I am adding tests (based on the official Lua tests) to my Go Lua VM, and one of the tests failed because the incorrect result is coded into the test.

First of all your modulo is not my modulo (or at least this was a thing back in C89... looks like it isn't in C99+).

Secondly, -3%5 == 2 because floor(-3/5) = -1, and (-1)*5+2 = -5+2 = -3.

See also:

https://www.microsoft.com/en-us/research/publication/division-and-modulus-for-computer-scientists/

http://hisham.hm/2015/04/18/a-small-practical-example-where-luas-behavior-is-better-than-cs/

https://github.com/sp614x/optifine/issues/288

etc. This is an endless argument.

Thirdly, in case you're still reading this for some unknown reason, RTFM always applies:

http://www.lua.org/manual/5.3/manual.html#3.4.1

"Modulo is defined as the remainder of a division that rounds the quotient towards minus infinity (floor division)."

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.



Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Milo Christiansen
The way Lua does it may not be 100% wrong, but it is not the way an experienced programmer will expect it to work. IMHO this adds an unnecessary little speed bump in the way of good workflow.

Wait, what am I saying, this is a language that thinks 1-based indexing is a good thing, forget I said anything. /s

On Tue, Jan 24, 2017 at 6:47 PM, Milo Christiansen <[hidden email]> wrote:
Hmmm... So why does my programmers calculator, Go, JavaScript, etc, etc all return -3 in this case?

Personally I think it's a bug, as "2" is not the correct result for that expression (in any language but Lua it seems).

On Tue, Jan 24, 2017 at 6:40 PM, Soni L. <[hidden email]> wrote:
On 24/01/17 09:21 PM, Milo Christiansen wrote:
In Lua 5.3 "-3%5 == 2", according to my programmers calculator and several other programing languages I tried this expression in, the real result is -3.

On the other hand "5%-3 == 2", so maybe the result is correct, and the bug is simply reversed operands if one is negative?

I discovered this because I am adding tests (based on the official Lua tests) to my Go Lua VM, and one of the tests failed because the incorrect result is coded into the test.

First of all your modulo is not my modulo (or at least this was a thing back in C89... looks like it isn't in C99+).

Secondly, -3%5 == 2 because floor(-3/5) = -1, and (-1)*5+2 = -5+2 = -3.

See also:

https://www.microsoft.com/en-us/research/publication/division-and-modulus-for-computer-scientists/

http://hisham.hm/2015/04/18/a-small-practical-example-where-luas-behavior-is-better-than-cs/

https://github.com/sp614x/optifine/issues/288

etc. This is an endless argument.

Thirdly, in case you're still reading this for some unknown reason, RTFM always applies:

http://www.lua.org/manual/5.3/manual.html#3.4.1

"Modulo is defined as the remainder of a division that rounds the quotient towards minus infinity (floor division)."

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.




Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Rain Gloom
In reply to this post by Milo Christiansen
> in any language
Did you look at the wikipedia page?
For instance in C++ it is implementation defined.
IMHO C's definition makes the most sense mathematically.

As far as my first semester discrete math knowledge goes, this is the relevant equation:
ka + r = n && 0 <= r < n
where a and n are constants
The important part is 0 <= r. This makes the solution unique for signed integers too and is what C seems to be based on.

On Tue, Jan 24, 2017 at 11:47 PM, Milo Christiansen <[hidden email]> wrote:
Hmmm... So why does my programmers calculator, Go, JavaScript, etc, etc all return -3 in this case?

Personally I think it's a bug, as "2" is not the correct result for that expression (in any language but Lua it seems).

On Tue, Jan 24, 2017 at 6:40 PM, Soni L. <[hidden email]> wrote:
On 24/01/17 09:21 PM, Milo Christiansen wrote:
In Lua 5.3 "-3%5 == 2", according to my programmers calculator and several other programing languages I tried this expression in, the real result is -3.

On the other hand "5%-3 == 2", so maybe the result is correct, and the bug is simply reversed operands if one is negative?

I discovered this because I am adding tests (based on the official Lua tests) to my Go Lua VM, and one of the tests failed because the incorrect result is coded into the test.

First of all your modulo is not my modulo (or at least this was a thing back in C89... looks like it isn't in C99+).

Secondly, -3%5 == 2 because floor(-3/5) = -1, and (-1)*5+2 = -5+2 = -3.

See also:

https://www.microsoft.com/en-us/research/publication/division-and-modulus-for-computer-scientists/

http://hisham.hm/2015/04/18/a-small-practical-example-where-luas-behavior-is-better-than-cs/

https://github.com/sp614x/optifine/issues/288

etc. This is an endless argument.

Thirdly, in case you're still reading this for some unknown reason, RTFM always applies:

http://www.lua.org/manual/5.3/manual.html#3.4.1

"Modulo is defined as the remainder of a division that rounds the quotient towards minus infinity (floor division)."

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.




Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Soni "They/Them" L.
In reply to this post by Milo Christiansen
On 24/01/17 09:47 PM, Milo Christiansen wrote:
> Hmmm... So why does my programmers calculator, Go, JavaScript, etc,
> etc all return -3 in this case?
>
> Personally I think it's a bug, as "2" is not the correct result for
> that expression (in any language but Lua it seems).

Don't top post. And read this:
http://hisham.hm/2015/04/18/a-small-practical-example-where-luas-behavior-is-better-than-cs/
(That's from the LuaRocks developer, I think. So they kinda know what
they're saying.)

And check mailing list archives. This isn't the first time this has come up.

>
> On Tue, Jan 24, 2017 at 6:40 PM, Soni L. <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     On 24/01/17 09:21 PM, Milo Christiansen wrote:
>
>         In Lua 5.3 "-3%5 == 2", according to my programmers calculator
>         and several other programing languages I tried this expression
>         in, the real result is -3.
>
>         On the other hand "5%-3 == 2", so maybe the result is correct,
>         and the bug is simply reversed operands if one is negative?
>
>         I discovered this because I am adding tests (based on the
>         official Lua tests) to my Go Lua VM, and one of the tests
>         failed because the incorrect result is coded into the test.
>
>
>     First of all your modulo is not my modulo (or at least this was a
>     thing back in C89... looks like it isn't in C99+).
>
>     Secondly, -3%5 == 2 because floor(-3/5) = -1, and (-1)*5+2 = -5+2
>     = -3.
>
>     See also:
>
>     https://www.microsoft.com/en-us/research/publication/division-and-modulus-for-computer-scientists/
>     <https://www.microsoft.com/en-us/research/publication/division-and-modulus-for-computer-scientists/>
>
>     http://hisham.hm/2015/04/18/a-small-practical-example-where-luas-behavior-is-better-than-cs/
>     <http://hisham.hm/2015/04/18/a-small-practical-example-where-luas-behavior-is-better-than-cs/>
>
>     https://github.com/sp614x/optifine/issues/288
>     <https://github.com/sp614x/optifine/issues/288>
>
>     etc. This is an endless argument.
>
>     Thirdly, in case you're still reading this for some unknown
>     reason, RTFM always applies:
>
>     http://www.lua.org/manual/5.3/manual.html#3.4.1
>     <http://www.lua.org/manual/5.3/manual.html#3.4.1>
>
>     "Modulo is defined as the remainder of a division that rounds the
>     quotient towards minus infinity (floor division)."
>
>     --
>     Disclaimer: these emails may be made public at any given time,
>     with or without reason. If you don't agree with this, DO NOT REPLY.
>
>
>

--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.


Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Dirk Laurie-2
In reply to this post by Milo Christiansen
<troll_alert>
> Wait, what am I saying, this is a language that thinks 1-based indexing is a
> good thing, forget I said anything. /s
</troll_alert>

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Kaj Eijlers
In reply to this post by Milo Christiansen
>>The way Lua does it may not be 100% wrong, but it is not the way an experienced programmer will expect it to work. 

I disagree, an experienced programmer knows it varies across languages, and can even vary across implementations of those languages and thus safeguards against it.

Knowing that it isn't what you'd expect is really all the info you need. It's why you program, to be in control. Complaining about it is unlikely to solve it.
Reply | Threaded
Open this post in threaded view
|

Re: Re: Modulo operator produces incorrect results with negative operand(s).

Alex Queiroz
In reply to this post by Milo Christiansen
Hallo,

On 25/01/17 00:54, Milo Christiansen wrote:
>
> Wait, what am I saying, this is a language that thinks 1-based indexing
> is a good thing, forget I said anything. /s
>

Already forgotten.

--
-alex
http://unendli.ch/

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negativeoperand(s).

Tony Papadimitriou
In reply to this post by Milo Christiansen
>Wait, what am I saying, this is a language that thinks 1-based indexing is a good thing, forget I said anything. /s
 
Yes, what exactly are you saying? This *IS* a great thing!  And Lua isn’t the only language to do it right.
(Yet another C-derived language infested programmer I suppose... Do you also count your fingers from 0 to 9?)
 
I expect your ‘friends’ will soon voice their support for you...
Reply | Threaded
Open this post in threaded view
|

Re: Re: Modulo operator produces incorrect results with negative operand(s).

chris beck
In reply to this post by Alex Queiroz
> Hmmm... So why does my programmers calculator, Go, JavaScript, etc, etc all return -3 in this case?
>
> Personally I think it's a bug, as "2" is not the correct result for that expression (in any language but Lua it seems).

For what it's worth, among anyone who was a math major or took a course in algebra in college, the congruence class of -2 mod 5 is 3, and the idea that modulo should ever return negative numbers is an aberration inflicted on us by the makers of C some four decades ago. Just because everyone else timidly decided to follow in C's footsteps doesn't mean that this is the right thing to do, or even that it makes any sense at all.

Chris

On Wed, Jan 25, 2017 at 3:28 AM, Alex Silva <[hidden email]> wrote:
Hallo,

On 25/01/17 00:54, Milo Christiansen wrote:
>
> Wait, what am I saying, this is a language that thinks 1-based indexing
> is a good thing, forget I said anything. /s
>

Already forgotten.

--
-alex
http://unendli.ch/


Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Martin
On 02/08/2017 02:40 PM, chris beck wrote:
>> Hmmm... So why does my programmers calculator, Go, JavaScript, etc,
> etc all return -3 in this case?
>>
>> Personally I think it's a bug, as "2" is not the correct result for
> that expression (in any language but Lua it seems).
>
> For what it's worth, among anyone who was a math major or took a course
> in algebra in college, the congruence class of -2 mod 5 is 3
[snip]

It depends on additional restrictions of mod() results.

Gerenally

mod(n, m) is some function like
  : get x, y such that
  :   x * m + y == n,
  :   int(x), int(y), abs(y) < abs(m)
  : return y

And further restrictions possible:
  : x = min(possible x) // x leftmost from zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (1)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  0 *  5 +  2 =>  2

  : x = max(possible x) // x rightmost from zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (2)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  1 *  5 + -3 => -3

  : y = min(possible y) // y leftmost from zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (3)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  1 *  5 + -3 => -3

  : y = max(possible y) // y rightmost from zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (4)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  0 *  5 +  2 =>  2

And even more:
  : x = min(abs(possible x)) // x towards zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (5)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  0 *  5 +  2 =>  2

  : x = max(abs(possible x)) // x away zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (6)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  1 *  5 + -3 => -3

  : y = min(abs(possible y)) // y towards zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (7)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  0 *  5 +  2 =>  2

  : y = max(abs(possible y)) // y away zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (8)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  1 *  5 + -3 => -3

  /*
    Due some reason results of (5) and (7) are equal.
    Same for results (6) and (8).
  */

So at least six different variants possible. Which one you prefer and why?

-- Martin

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

chris beck
In number theory and algebra, the notation and concepts are sometimes developed as follows:

The first concept is divisibility. a | b is a proposition, representing that the integer a divides the integer b. In C you would usually write this test as (a % b == 0), but for purposes of math, you'd define an study | before talking about modulo probably. For instance, you can see that | defines a partial order on the integers. So, if a | b and b | c, then a | c. Also a | a, and if both a | b and b | a, then a = b.

The second concept is congruence modulo a number. In math it's usually notated:

a = b mod c

except instead of using =, you would use 3 lines, for instance, unicode 2261.

Here "mod" is not a binary operator being applied to b. It's rather a qualifier which modifies the meaning of =, you should [parse this basically as a special ternary operator. However, usually c is not changing. It might have been better if we notated thins like this

a =_c b

where c is a subscript modfying the equals symbol.

The meaning of this notation is, c | (a - b)
that is, that c divides the difference of a and b.

For any number a, the "congruence class " of a modulo c is the set of all b which is it is congruent to. Congruence is an equivalence relation: It's always the case that a = a mod c, because 0 is divisible by every number. Also, if a = b mod c then b = a mod c, and if a = b mod d and b = c mod d, then it's easy to see a = c mod d.

So, for any fixed number c, the set of all integers is partitioned into a collection of disjoint sets, the congruence classes modulo c. There are exactly c such classes, corresponding to the integers between 0 and c. Every other number is congruent to one of those -- you can figure out which one by taking the remainder after dividing by c, which is the conventional definition of "modulo".

One of the basic ideas of algebra is that just as we can add and multiply two numbers, it turns out that we can add and multiply two congruence classes, and the result will be unambiguously a congruence class. This is a bit counterintuitive at first. To do it, we simply take any element of the first congruence class, and any element of the second congruence class, add or multiply them as required, then compute the congruence class of the result. Naively, different choices could lead to different outcomes, so this wouldn't be well-defined, but it turns out that it always produces the same answer.

Let's introduce some new notation: Say that a mod c is a binary operation which takes two integers, and produces a set of integers, the congruence class of a mod c. This map is well-studied in group theory -- it is the canonical map from the integers Z to the quotient group Z / cZ. (The quotient group Z / cZ is the group whose elements are the congruence classes of Z mod c.)

If we do it that way, then we can reinterpret the standard notation "a = b mod c" as a succinct way of writing "a mod c = b mod c", that is, a and b are congruent if they correspond to the same congruence class.

Then, the most important properties of congruence and modulo can be written as follows:

(a + b) mod c = (a mod c) + (b mod c)
(a * b) mod c = (a mod c) * (b mod c)

These identities are extremely important, they enable computational shortcuts when you only care about the answer modulo some number. For instance, suppose I have some polynomial x^2 + 100x - 57, and I want to evaluate it mod 5 at some value x = 1701. Because of these identities, I can always reduce the input and any intermediate result mod 5 eagerly throughout the computation, without changing the final result. So

(1701)^2 + 100*1701 - 57 mod 5

= ((1701 mod 5)^2 mod 5) + (100 * 1701 mod 5) - 57 mod 5
= 1 + 0 - 2 mod 5 = - 1 mod 5 = 4 mod 5

This basic idea underlies important algorithms like fast exponentiation by repeated squaring. It's used essentially in Diffie-Hellman key exchange for instance, and it has numerous other applications in computer science.

In group theory and algebra, the quotient group construction is greatly generalized, and applies to lots of other situations. "Properly", algebraists think of "modulo" as yielding a congruence class, not a particular number.

In some arguments it is necessary to find "congruence class representatives", so you might say, the numbers 0, ..., c-1 are a set of representatives for the congruence classes mod c, and you might want a map that maps a number to its unique congruence class representative.

The modulo operation which appears in programming languages is an example of such a map, it's certianly useful. It produces for each number the remainder after division, which is in particular a "simpler" member of the congruence class.

But note that, unfortunately, the way that it is implemented in C gives unfortunate semantics.

For instance, it's easy to see that 1 is congruent to -1 modulo 2, because they differ by 2.

But if I write it in C, as `1 % 2 == -1 % 2`, I might get false instead of true, because the result for the first may be positive while the result for the second may be negative.

That's stupid and serves no useful purpose. Modulo would be far more natural and useful if (a % c == b % c) meant the same thing as "a is congruent to b mod c". Instead, I have to write ((a - b % c) == 0). Modulo should return the same value for any two numbers which are congruent, computing a *unique* set of congruence representatives. When it can return any value between -c and c that's just an unfortunate design flaw.

I believe that this behavior creates subtle bugs and problems in real programs, and might prevent the compiler from making some natural transformations that could be useful to make. For instance, it would be great if ((x * y + z * w) %) could be analyzed and rewritten based on the standard modulo identities, but usually, the possibility of negative values in modulo means that this is not exactly the same as ((x * y) % p + (z * w) % p) % p, so even if the compiler could generate better code for one form, or exploit knowedge that z or w = 0 mod p for instance, to simplify the expression, it will usually be afraid to do so.

So, in summary, it would be far far better if (a % b) is always at least 0 and less than b, and undefined / an error for b = 0, or negative b. It's not an "advantage" or "more natural" to return negative values when a is negative. This is because in the modular ring "Z / bZ", there really aren't any negative numbers. Every negative number is congruent to a positive number, and you can't separate them usefully into two distinct groups like you can with the integers and the rationals and so on. There are no "inequalities" in modular arithmetic, nor any negative numbers, at least not with any useful or interesting algebraic structure. It would be cleaner, simpler, more elegant, and probably more useful and efficient if modulo never returned negative numbers.

Best,
Chris

On Thu, Feb 9, 2017 at 6:18 AM, Martin <[hidden email]> wrote:
On 02/08/2017 02:40 PM, chris beck wrote:
>> Hmmm... So why does my programmers calculator, Go, JavaScript, etc,
> etc all return -3 in this case?
>>
>> Personally I think it's a bug, as "2" is not the correct result for
> that expression (in any language but Lua it seems).
>
> For what it's worth, among anyone who was a math major or took a course
> in algebra in college, the congruence class of -2 mod 5 is 3
[snip]

It depends on additional restrictions of mod() results.

Gerenally

mod(n, m) is some function like
  : get x, y such that
  :   x * m + y == n,
  :   int(x), int(y), abs(y) < abs(m)
  : return y

And further restrictions possible:
  : x = min(possible x) // x leftmost from zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (1)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  0 *  5 +  2 =>  2

  : x = max(possible x) // x rightmost from zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (2)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  1 *  5 + -3 => -3

  : y = min(possible y) // y leftmost from zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (3)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  1 *  5 + -3 => -3

  : y = max(possible y) // y rightmost from zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (4)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  0 *  5 +  2 =>  2

And even more:
  : x = min(abs(possible x)) // x towards zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (5)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  0 *  5 +  2 =>  2

  : x = max(abs(possible x)) // x away zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (6)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  1 *  5 + -3 => -3

  : y = min(abs(possible y)) // y towards zero
  => mod(-2, -5):  0 * -5 + -2 => -2         (7)
  => mod( 2, -5):  0 * -5 +  2 =>  2
  => mod(-2,  5):  0 *  5 + -2 => -2
  => mod( 2,  5):  0 *  5 +  2 =>  2

  : y = max(abs(possible y)) // y away zero
  => mod(-2, -5):  1 * -5 +  3 =>  3         (8)
  => mod( 2, -5): -1 * -5 + -3 => -3
  => mod(-2,  5): -1 *  5 +  3 =>  3
  => mod( 2,  5):  1 *  5 + -3 => -3

  /*
    Due some reason results of (5) and (7) are equal.
    Same for results (6) and (8).
  */

So at least six different variants possible. Which one you prefer and why?

-- Martin


Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Doug Currie
In reply to this post by Martin
On Thu, Feb 9, 2017 at 6:18 AM, Martin <[hidden email]> wrote:

So at least six different variants possible. Which one you prefer and why?

The division and modulo operations should come in pairs so that 

D = d “ (D div d) + (D mod d)

The two obvious candidates for div are floor and truncate. Lua chooses floor. Common Lisp provides floor, truncate, ceiling, and round, with corresponding quotients and remainders.

Folks interested in this topic should take a look at "The Euclidean Definition of the Functions div and mod" by Raymond T. Boute, University of Nijmegen, ACM Transactions on Programming Languages and Systems, Vol 14, No. 2, April 1992. Its abstract:

The definitions of the functions div and mod in the computer science literature and in programming languages are either similar to the Algol or Pascal definition (which is shown to be an unfortunate choice) or based on division by truncation (T-definition) or division by flooring as defined by Knuth (F-definition). The differences between various definitions that are in common usage are discussed, and an additional one is proposed, which is based on Euclid’s theorem and therefore is called the Euclidean definition (E-definition). Its distinguishing feature is that 0 <= D mod d < abs(d) irrespective of the signs of D and d. It is argued that the E- and F-definitions are superior to all other ones in regularity and useful mathematical properties and hence deserve serious consideration as the standard convention at the applications and language level. It is also shown that these definitions are the most suitable ones for describing number representation systems and the realization of arithmetic operations at the architecture and hardware level.
 
e

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Martin
Thank you for clarifying, guys!

Now I see that requirement of non-negative remainder is quite practical
and well-binded with mathematical rings of natural numbers.

Sadly (as I understand from similar discussions before) Lua
implementation is heavily linked with ANSI C and Roberto generally not
willing to introduce changes in logic that is different from ANSI C.

Although I consider "%" and math.mod() behavior change worth it.

-- Martin

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Sean Conner
It was thus said that the Great Martin once stated:

> Thank you for clarifying, guys!
>
> Now I see that requirement of non-negative remainder is quite practical
> and well-binded with mathematical rings of natural numbers.
>
> Sadly (as I understand from similar discussions before) Lua
> implementation is heavily linked with ANSI C and Roberto generally not
> willing to introduce changes in logic that is different from ANSI C.
>
> Although I consider "%" and math.mod() behavior change worth it.

  Further fuel for the fire.  I did three different versions of mod---one in
assembly (x86 32bit), C (x86 32bit) and Lua 5.3 (x86 32bit).  The results:

[spc]lucy:/tmp>./mod 7 3
A: 2 1
C: 2 1
L: 2 1
[spc]lucy:/tmp>./mod -7 3
A: -2 -1
C: -2 -1
L: -3 2
[spc]lucy:/tmp>./mod 7 -3
A: -2 1
C: -2 1
L: -3 -2
[spc]lucy:/tmp>./mod -7 -3
A: 2 -1
C: 2 -1
L: 2 -1
[spc]lucy:/tmp>

  -spc (Make of that what you will)

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Dirk Laurie-2
In reply to this post by Martin
2017-02-09 15:02 GMT+02:00 Martin <[hidden email]>:

> Sadly (as I understand from similar discussions before) Lua
> implementation is heavily linked with ANSI C and Roberto generally not
> willing to introduce changes in logic that is different from ANSI C.

Roberto might like to speak for himself on this, but IMHO the above
comment oversimplifies his position.

Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Viacheslav Usov
In reply to this post by Martin
On Thu, Feb 9, 2017 at 2:02 PM, Martin <[hidden email]> wrote:

> Sadly (as I understand from similar discussions before) Lua implementation is heavily linked with ANSI C and Roberto generally not willing to introduce changes in logic that is different from ANSI C.

ANSI C usually means C89, where the division and modulo operators were implementation defined when either operand were negative. In Lua, on the other hand, these are not implementation defined. In more modern C standard, these are also not implementation defined, albeit different from Lua. So, in this particular case, Lua does not follow "ANSI" C at all.

Cheers,
V.
Reply | Threaded
Open this post in threaded view
|

Re: Modulo operator produces incorrect results with negative operand(s).

Roberto Ierusalimschy
In reply to this post by Dirk Laurie-2
> 2017-02-09 15:02 GMT+02:00 Martin <[hidden email]>:
>
> > Sadly (as I understand from similar discussions before) Lua
> > implementation is heavily linked with ANSI C and Roberto generally not
> > willing to introduce changes in logic that is different from ANSI C.
>
> Roberto might like to speak for himself on this, but IMHO the above
> comment oversimplifies his position.

As Viacheslav pointed out, the comment does not make sense here, as the
discussion started exactly because Lua *is* different from ANSI C in
this particular logic corner. Anyway...

First, the fact that the Lua implementation is heavily linked
with ANSI C does not imply at all that the Lua specification is
linked with ANSI C.

Second, anyone willing to discuss this subject should read the paper
mentioned by Doug ("The Euclidean Definition of the Functions div and
mod"). Unlike C, which currently uses the T-definition, Lua uses the
F-definition, which is one of the definitions that the paper argues to
be "superior to all other ones in regularity and useful mathematical
properties".

-- Roberto

12