Low level arithmetics bug: -3 mod 7 == 3

[snjax]

Function mod returns the wrong result.

Nim versions affected by the bug: >= 1.0

Example

echo -3 mod 7

Current Output

3

Expected Output

-3

Possible Solution

rollback mod operation to 0.20.2 version

[narimiran]

An easier example to see the buggy behaviour:

echo -3 mod 5
echo -13 mod 5

3
-3

Another example:

echo ( 7 mod  5)
echo (-7 mod  5)
echo ( 7 mod -5)
echo (-7 mod -5)
echo "----"
echo ( 2 mod  5)
echo (-2 mod  5)
echo ( 2 mod -5)
echo (-2 mod -5)

2
-2
2
-2
----
2
2
2
2

---

I can confirm all these worked correctly in 0.20.x version.

[mratsim]

again? #12332

Seems like I jumped the gun. This is actually more intricate see C vs Python below.

---

It is very important for us that we can trust all Nim low-level operators to do give the same results at runtime, during constant folding and in the VM.

We implemented an anti-regression suite in stint (status-im/nim-stint#91) but those regressions, bugs and flawed tests (#11138, #9572) are very time-consuming.

This is a necessary condition to build healthy big int libraries, crypto libraries and number theory related libraries in Nim.

I suggest we have an extensive run-time, compile-time and semantic fold test suite for basic operators.

---

C output:

C uses the underlying hardware convention. On x86_64, the sign of the remainder is the sign of the dividend.

#include <stdio.h>
#include <stdint.h>

int main(int argc, char *argv[])
{
  int64_t dividend, divisor;

  dividend = -3;
  divisor = 5;
  printf("%d mod %d = %d\n", dividend, divisor, dividend % divisor);

  dividend = -13;
  divisor = 5;
  printf("%d mod %d = %d\n", dividend, divisor, dividend % divisor);

  printf("----------------------------------------------------------\n");
  printf("%d mod %d = %d\n",  7,  5,  7 %  5);
  printf("%d mod %d = %d\n", -7,  5, -7 %  5);
  printf("%d mod %d = %d\n",  7, -5,  7 % -5);
  printf("%d mod %d = %d\n", -7, -5, -7 % -5);
  printf("----\n");
  printf("%d mod %d = %d\n",  2,  5,  2 %  5);
  printf("%d mod %d = %d\n", -2,  5, -2 %  5);
  printf("%d mod %d = %d\n",  2, -5,  2 % -5);
  printf("%d mod %d = %d\n", -2, -5, -2 % -5);
}

-3 mod 5 = -3
-13 mod 5 = -3
----------------------------------------------------------
7 mod 5 = 2
-7 mod 5 = -2
7 mod -5 = 2
-7 mod -5 = -2
----
2 mod 5 = 2
-2 mod 5 = -2
2 mod -5 = 2
-2 mod -5 = -2

Python output:

Python has the convention that remainder is non-negative

print(f"-3 mod 5 = {-3 % 5}")
print(f"-13 mod 5 = {-13 % 5}")
print("----------------------------------------------------------")
print(f" 7 mod  5 = { 7 %  5}")
print(f"-7 mod  5 = {-7 %  5}")
print(f" 7 mod -5 = { 7 % -5}")
print(f"-7 mod -5 = {-7 % -5}")
print("----")
print(f" 2 mod  5 = { 2 %  5}")
print(f"-2 mod  5 = {-2 %  5}")
print(f" 2 mod -5 = { 2 % -5}")
print(f"-2 mod -5 = {-2 % -5}")

-3 mod 5 = 2
-13 mod 5 = 2
----------------------------------------------------------
 7 mod  5 = 2
-7 mod  5 = 3
 7 mod -5 = -3
-7 mod -5 = -2
----
 2 mod  5 = 2
-2 mod  5 = 3
 2 mod -5 = -3
-2 mod -5 = -2

---

I suggest we choose the same convention as C and assembly.

Note that once a convention is chosen, the output of div and mod must respect the equation A = quotient * B + remainder with A mod B = remainder and A div B = quotient

---

Important notice

As mentioned mod and div in C are "implementation-defined" by the hardware. We should just mention that in the VM for modulo/remainder operations we follow x86 convention.