Opened 12 years ago

Closed 8 years ago

#2956 closed defect (fixed)

generic multivariate polynomials are buggy on exponent overflow

Reported by: cwitty Owned by: malb
Priority: major Milestone: sage-5.0
Component: basic arithmetic Keywords: sd35.5
Cc: mjo Merged in: sage-5.0.beta0
Authors: Michael Orlitzky Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Long exponents are silently truncated to word-size exponents:

sage: K.<x,y> = AA[]
sage: x^(2^64 + 12345)
x^12345

In one test, I also saw a crash, but I can't reproduce it.

sage: K.<x,y> = ZZ[]
sage: (x^12345)^54321


------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occured in SAGE.
...

(The crash was on 32-bit x86 Debian testing. The first test fails with the same answer on both 32-bit and 64-bit x86.)

Attachments (1)

sage-trac_2956.patch (1.3 KB) - added by mjo 8 years ago.
Updated patch, should also work on x32.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 12 years ago by was

  • Milestone changed from sage-3.0 to sage-3.0.1

comment:2 follow-up: Changed 11 years ago by zimmerma

For the 2nd example, I do not get a crash, but a funny result with 3.1.4 on a 32-bit computer:

sage: K.<x,y> = ZZ[]
sage: (x^12345)^54321
x^28393*y^10232

Note that y does not appear in the input!

Possible explanation: 12345*54321 = 10232*216+28393. Apparently the low 16 bits are used to store the exponent of x, and the upper 16 bits for the exponent of y, but no check for overflow is done!!!

comment:3 in reply to: ↑ 2 Changed 11 years ago by zimmerma

Replying to zimmerma:

I realize this was already noticed by Carl in #2957.

comment:4 Changed 11 years ago by malb

  • Owner changed from somebody to malb
  • Status changed from new to assigned

comment:5 Changed 8 years ago by mjo

  • Authors set to Michael Orlitzky
  • Cc mjo added
  • Report Upstream set to N/A
  • Status changed from new to needs_review

I think these are both fixed, so I've added doctests. I have only tested on x64: I think the first example should overflow on both, the second should work on both. But a reviewer should give it a try on x32.

comment:6 follow-up: Changed 8 years ago by zimmerma

  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to needs_work
  • Work issues set to adapt for x32

I tried on a 32-bit machine with vanilla 4.7.2. The first doctest is ok, for the second one I get:

sage: (x^12345)^54321
...
OverflowError: Exponent overflow (670592745).

thus the patch needs work.

Paul Zimmermann

comment:7 in reply to: ↑ 6 Changed 8 years ago by mjo

Hmm, I wonder how big we can make the exponent. I was guessing (2^31 - 1), but 670592745 is way smaller than that.

Since the crash was on a 32-bit machine, we can assume (i.e. hope) that it was due to the overflow. With that in mind, maybe we should just ignore the output with "..." and consider the test a success if it doesn't crash?

comment:8 Changed 8 years ago by mjo

  • Status changed from needs_work to needs_review

Changed 8 years ago by mjo

Updated patch, should also work on x32.

comment:9 Changed 8 years ago by zimmerma

  • Keywords sd35.5 added

comment:10 Changed 8 years ago by zimmerma

note: for K.<x,y> = AA[] the maximum exponent seems to be 2147483647 both on 32- and 64-bit, while for K.<x,y> = ZZ[] on 32-bit the maximum is 32768, and on 64-bit it is 1073741824.

Paul

comment:11 Changed 8 years ago by zimmerma

both doctests now pass on x32. I'm running the doctests on x32.

Paul

comment:12 Changed 8 years ago by zimmerma

my installation of Sage on x32 was corrupted, I will try again with sage.4.8.alpha6.

Paul

comment:13 Changed 8 years ago by zimmerma

  • Status changed from needs_review to positive_review
  • Work issues adapt for x32 deleted

I confirm all doctests pass on x32 (I got one failure in rings/real_mpfi.pyx but this was due to the spkg from #12171 I had installed). Thus positive review.

Paul

comment:14 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.8 to sage-5.0

comment:15 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.