Wrong result due to integer overflow (in pynac?)

[DaveWitteMorris]

Volker Braun pointed out in #31479 comment:12 that sage gives the following wrong answer on a 32-bit machine after the bug-fix patch of #31479 is applied:

sage: a,b,c,d = var("a b c d")
sage: ((a + b + c)^30 * (3*b + d - 5/d)^3).expand().subs(a=0,b=2,c=-1)
d^3 + 18*d^2 + 1739461754973*d - 8697308774865/d + 450/d^2 - 125/d^3 + 36

This answer is congruent modulo 2^32 to d^3 + 18*d^2 + 93*d - 465/d + 450/d^2 - 125/d^3 + 36, which is the correct answer, so it seems clear that the problem comes from an integer overflow error. Perhaps the overflow error can also be produced on a 64-bit machine.

Depends on #31694

Component: symbolics

Keywords: integer overflow, pynac

Author: Dave Morris, Matthias Koeppe

Branch/Commit: eba0a9c

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/31585

[mkoeppe]

comment:1

Moving to 9.4, as 9.3 has been released.

[DaveWitteMorris]

comment:2

I reproduced the bug by installing sage in a 32-bit debian virtual machine, and found a much simpler example of the overflow:

sage: (2*x).subs(x=-2^31)
0

More generally:

sage: for n in range(10):
....:     print(n, (n*x).subs(x=-2^31)/2^31)
0 0
1 -1
2 0
3 -1
4 0
5 -1
6 0
7 -1
8 0
9 -1

[DaveWitteMorris]

Author: Dave Morris

[DaveWitteMorris]

comment:3

I think the problem is an incorrect calculation of absolute value:

sage: abs(x).subs(x=-2^31)
-2147483648

To decide whether a multiplication might cause an overflow, pynac compares the absolute values of the factors to a certain bound. In the example of comment:2, the absolute value of a factor is negative, so it is less than the bound, even though the factor is actually very large.

And I think the incorrect absolute value comes from the C++ std::labs function. The documentation of that function says "If the result cannot be represented as a long int (such as labs(LONG_MIN) in an implementation with two's complement signed values), it causes undefined behavior."

I should be able to write a pynac patch soon that tests my theory. Even if it isn't the bug we are looking for, this bug in the absolute value needs to be fixed.

[DaveWitteMorris]

comment:4

The same problem comes up in pynac's numeric::negative method, so that will need to be fixed too:

sage: (-x).subs(x=-2^31)
-2147483648

[DaveWitteMorris]

comment:5

Here is a crash that is caused by the overflow when -2^31 is divided by -1:

sage: (1 - 2^31*x)*x
    <snip>
Unhandled SIGFPE: An unhandled floating point exception occurred. ...

Patches to fix all of these should be coming soon.

[DaveWitteMorris]

Branch: public/31585

[DaveWitteMorris]

comment:7

The pynac bugs on this ticket do not currently affect 64-bit sage. (This is because pynac does not store -2^63 as a long integer, even though it could fit into that space on a 64-bit machine.) However, they will affect 64-bit machines after the branch on #31986 is merged. (See the explanation and examples there.) Hence, a 64-bit user can test the PR of this ticket by first merging the branch of #31986 (and executing sage -f pynac), and replacing -2^31 with -2^63, as in the examples in the description of #31986.

Followup tickets: #31984 and #31986.

I will try to post this (and my other pynac patches) to the pynac github repository soon. My previous attempts failed because I know almost nothing about git, but now I understand that I need a fork, instead of a clone, so I hope to be successful.

---

New commits:

f1a99fa	trac 31585 pynac overflow patch
3fcf072	add doctests
fdde3d9	update pynac patch level

[DaveWitteMorris]

Commit: fdde3d9

[DaveWitteMorris]

comment:8

I think this pynac patch also fixes #25688.

[tscrim]

comment:9

Merge conflict

[DaveWitteMorris]

Changed branch from public/31585 to public/31585r1

[DaveWitteMorris]

comment:11

Rebased on 9.4b3.

---

New commits:

ecb99c8	trac 31585 pynac overflow patch
2d04fa4	add doctests
5a340ce	update pynac patch level

[DaveWitteMorris]

Changed commit from fdde3d9 to 5a340ce

[mkoeppe]

comment:12

PR to pynac please

[DaveWitteMorris]

comment:13

Yes, I will try.

[sagetrac-git]

Changed commit from 5a340ce to 627ec10

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

627ec10

also fix /=

[DaveWitteMorris]

comment:15

I previously neglected to fix the /= operator, which can also overflow.

I created pynac PR #378. It's my first PR to anywhere other than the trac server, so please let me know if I goofed anything up.

[dimpase]

comment:25

running GH Actions tests on this https://github.com/sagemath/sagetrac-mirror/actions/runs/978774922
(basically to test #31694)

[mkoeppe]

comment:26

PR with standard-conforming code at pynac/pynac#379

[sagetrac-git]

Changed commit from a081808 to 5d89a50

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5d89a50

trying pynac PR 379

[dimpase]

comment:29

tests at https://github.com/sagemath/sagetrac-mirror/actions/runs/982168057

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3c75f53

correct patch suffix

[sagetrac-git]

Changed commit from 5d89a50 to 3c75f53

[dimpase]

comment:31

update - https://github.com/sagemath/sagetrac-mirror/actions/runs/982441436

---

New commits:

3c75f53

correct patch suffix

[mkoeppe]

Changed branch from u/dimpase/31585r1 to u/mkoeppe/31585r1

[mkoeppe]

Changed commit from 3c75f53 to a8e82dd

[mkoeppe]

New commits:

c9c50e3	build/pkgs/pynac: Upgrade to 0.7.29
f1d83c3	Merge #31694
a8e82dd	add doctests - cf #31585

[sagetrac-git]

Changed commit from a8e82dd to eba0a9c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

eba0a9c

build/bin/write-dockerfile.sh: Disable the gfan testsuite (does not terminate on 32bit)

[mkoeppe]

Changed author from Dave Morris to Dave Morris, Matthias Koeppe

[dimpase]

comment:36

tests run on https://github.com/sagemath/sagetrac-mirror/actions/runs/986545913

[dimpase]

comment:37

lgtm

[mkoeppe]

comment:38

Thanks!

[vbraun]

Changed branch from u/mkoeppe/31585r1 to eba0a9c