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

Created on 25 Oct 2019  路  2Comments  路  Source: nim-lang/Nim

Function mod returns the wrong result.

Nim versions affected by the bug: >= 1.0

Example

echo -3 mod 7

Current Output

Expected Output

Possible Solution

rollback mod operation to 0.20.2 version

Showstopper
Source
picture snjax

Most helpful comment

again? https://github.com/nim-lang/Nim/issues/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 (https://github.com/status-im/nim-stint/pull/91) but those regressions, bugs and flawed tests (https://github.com/nim-lang/Nim/issues/11138, https://github.com/nim-lang/Nim/issues/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



md5-05dd26910fa572f695ec65e43a1f68b7

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

picture mratsim on 25 Oct 2019
👍4

All 2 comments

An easier example to see the buggy behaviour:

echo -3 mod 5
echo -13 mod 5

-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

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

narimiran picture narimiran on 25 Oct 2019

again? https://github.com/nim-lang/Nim/issues/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 (https://github.com/status-im/nim-stint/pull/91) but those regressions, bugs and flawed tests (https://github.com/nim-lang/Nim/issues/11138, https://github.com/nim-lang/Nim/issues/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



md5-05dd26910fa572f695ec65e43a1f68b7

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

mratsim picture mratsim on 25 Oct 2019
👍4
Was this page helpful?
0 / 5 - 0 ratings

Related issues

teroz picture teroz  路  3Comments
timotheecour picture timotheecour  路  3Comments
liquid600pgm picture liquid600pgm  路  3Comments
awr1 picture awr1  路  3Comments
timotheecour picture timotheecour  路  3Comments