# Ticket #2957(closed defect: fixed)

Opened 5 years ago

## [with patch, positive review] Singular multivariate polynomials are buggy on exponent overflow

Reported by: Owned by: cwitty somebody major sage-3.3 basic arithmetic

### Description

On 64-bit x86, exponents truncate to 32 bits:

```sage: K.<x,y> = QQ[]
sage: ((x^12345)^54321)^12345
x^2065457633
sage: 12345*54321*12345
8278467437025
sage: (12345*54321*12345) % 2^32
2065457633
```

On 32-bit x86, exponents truncate to 16 bits, and overflow from one variable to another (!!!):

```sage: K.<x,y> = QQ[]
sage: (x^12345)^54321
x^28393*y^10232
sage: (12345*54321) // 2^16
10232
sage: (12345*54321) % 2^16
28393
```

## Change History

### comment:1 Changed 5 years ago by was

• Milestone changed from sage-3.0 to sage-3.0.1

### comment:2 Changed 4 years ago by malb

I'm going to upload a fix in a sec, but it comes at a cost:

## Before

```sage: P.<x,y> = PolynomialRing(QQ)
sage: %timeit x*y
1000000 loops, best of 3: 288 ns per loop

sage: f = x + 1
sage: g = y + 1
sage: %timeit f*g
1000000 loops, best of 3: 462 ns per loop
```

## After

```sage: P.<x,y> = PolynomialRing(QQ)
sage: %timeit x*y
1000000 loops, best of 3: 314 ns per loop

sage: f = x + 1
sage: g = y + 1
sage: %timeit f*g
1000000 loops, best of 3: 501 ns per loop
```

### comment:3 Changed 4 years ago by malb

• Summary changed from Singular multivariate polynomials are buggy on exponent overflow to [with patch, needs review] Singular multivariate polynomials are buggy on exponent overflow

### comment:4 Changed 4 years ago by malb

I just replaced the existing patch with a new one which improves performance. Burcin spotted earlier, that I forgot to assign a type to max_exponent_size. With that, the timing difference is in the range of the normal noise.

### comment:5 Changed 4 years ago by burcin

• Summary changed from [with patch, needs review] Singular multivariate polynomials are buggy on exponent overflow to [with patch, needs work] Singular multivariate polynomials are buggy on exponent overflow

We already discussed this with malb, boothby and was extensively. Here are the points here for reference:

• the return value of the function p_GetMaxExp is an unsigned long, fixing this should let one remove the esum < 0 check
• max_exponent_size in multi_polynomial_libsingular.pyx should be declared an unsigned long
• adding an unlikely hint for esum > max_exponent_size might reduce the speed regression even further

Boothby also remarked that checking for total degree before the degree of each variable might help. Looking at the code again, I think we only check the total degree.

### comment:6 Changed 4 years ago by malb

• Summary changed from [with patch, needs work] Singular multivariate polynomials are buggy on exponent overflow to [with patch, needs review] Singular multivariate polynomials are buggy on exponent overflow

### comment:7 Changed 4 years ago by burcin

• Summary changed from [with patch, needs review] Singular multivariate polynomials are buggy on exponent overflow to [with patch, positive review pending changes] Singular multivariate polynomials are buggy on exponent overflow

The _imul_ method also needs the check.

### comment:8 Changed 4 years ago by malb

• Summary changed from [with patch, positive review pending changes] Singular multivariate polynomials are buggy on exponent overflow to [with patch, positive review] Singular multivariate polynomials are buggy on exponent overflow

Burcin agrees that this is a positive review now.

### comment:9 Changed 4 years ago by mabshoff

• Status changed from new to closed
• Resolution set to fixed
• Milestone changed from sage-3.4.1 to sage-3.3

Merged in Sage 3.3.alpha3.

Cheers,

Michael

Note: See TracTickets for help on using tickets.