
12

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.


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/enus/research/publication/divisionandmodulusforcomputerscientists/http://hisham.hm/2015/04/18/asmallpracticalexamplewhereluasbehaviorisbetterthancs/https://github.com/sp614x/optifine/issues/288etc. 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.


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.


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).


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 1based indexing is a good thing, forget I said anything. /s


> 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 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/asmallpracticalexamplewhereluasbehaviorisbetterthancs/(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/enus/research/publication/divisionandmodulusforcomputerscientists/> < https://www.microsoft.com/enus/research/publication/divisionandmodulusforcomputerscientists/>
>
> http://hisham.hm/2015/04/18/asmallpracticalexamplewhereluasbehaviorisbetterthancs/> < http://hisham.hm/2015/04/18/asmallpracticalexamplewhereluasbehaviorisbetterthancs/>
>
> 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.


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


>>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.


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

alex
http://unendli.ch/


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


> 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 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


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 welldefined, 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 wellstudied 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 DiffieHellman 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, ..., c1 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


Thank you for clarifying, guys!
Now I see that requirement of nonnegative remainder is quite practical
and wellbinded 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


It was thus said that the Great Martin once stated:
> Thank you for clarifying, guys!
>
> Now I see that requirement of nonnegative remainder is quite practical
> and wellbinded 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 modone 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)


20170209 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.


> 20170209 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 Tdefinition, Lua uses the
Fdefinition, 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
