Opened 9 years ago

Closed 7 years ago

# Universal cyclotomic field breaks for moderate order

Reported by: Owned by: mraum davidloeffler major sage-duplicate/invalid/wontfix number fields ucf, overflow stumpc5, mraum N/A assess performance impact

### Description

UniversalCyclotomicField? seeming is unable to handle moderate orders - even though I don't see how an overflow could occur when multiplying elements of order 245. Here is how I found the problem

```UCF.<E> = UniversalCyclotomicField()
K.<rho> = CyclotomicField(245)
h = K.random_element()
h_rho = rho.coordinates_in_terms_of_powers()(h)
h_ucf = sum( c * E(245, i) for (i, c) in enumerate(h_rho) )
h_ucf**2
```

The last line gives an OverflowError?:

```/home/martin/workspace/sage57/local/lib/python2.7/site-packages/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field.pyc in __pow__(self, k)
1506             else:
1507                 if k % 2 == 0:
-> 1508                     return (self*self).__pow__(k/2)
1509                 else:
1510                     return self * self.__pow__(k-1)

/home/martin/workspace/sage57/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__mul__ (sage/structure/element.c:14096)()

/home/martin/workspace/sage57/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement._mul_ (sage/structure/element.c:14222)()

/home/martin/workspace/sage57/local/lib/python2.7/site-packages/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field.pyc in _mul_(self, other)
1578             n1,n2 = self.field_order(),other.field_order()
1579             n = LCM_list([n1,n2])
-> 1580             return F._from_dict(push_down_cython(n,dict_multiplication(D_self, D_other, n1, n2, n)), remove_zeros=False)
1581
1582         def _sub_(self, other):

/home/martin/workspace/sage57/local/lib/python2.7/site-packages/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field_c.so in sage.rings.universal_cyclotomic_field.universal_cyclotomic_field_c.dict_multiplication (sage/rings/universal_cyclotomic_field/universal_cyclotomic_field_c.c:12372)()

/home/martin/workspace/sage57/local/lib/python2.7/site-packages/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field_c.so in sage.rings.universal_cyclotomic_field.universal_cyclotomic_field_c.dict_multiplication (sage/rings/universal_cyclotomic_field/universal_cyclotomic_field_c.c:11381)()

OverflowError: value too large to convert to int
```

The element which I have used concretely (but I have tried several random elements) is

```-2339/36*E(245) + 1/2*E(245)^2 - 155/48*E(245)^3 + 4*E(245)^4 + 3*E(245)^6 + 3/2*E(245)^8 - 9/2*E(245)^9 - 1/140*E(245)^11 + 1619/330*E(245)^12 + E(245)^13 + 10*E(245)^16 - 97/12*E(245)^17 - 25/6*E(245)^18 + 17/4*E(245)^19 + 49/2*E(245)^22 - 35*E(245)^23 + 27/4*E(245)^24 + 74/13*E(245)^26 + 3*E(245)^27 + 2*E(245)^28 + 1/5*E(245)^29 - 2*E(245)^31 - 9/4*E(245)^32 + 1/2*E(245)^33 - 20*E(245)^36 - 23/8*E(245)^38 + 11/4*E(245)^41 + 8/3*E(245)^42 - 5/2*E(245)^43 - E(245)^46 + 5*E(245)^47 - E(245)^48 + 1/2*E(245)^51 - 149/60*E(245)^52 - 35/6*E(245)^53 - 4/5*E(245)^56 - 6*E(245)^57 - 2*E(245)^58 + 21271/4466*E(245)^61 + 5*E(245)^62 + 5/2*E(245)^63 - 16/3*E(245)^66 + 5/6*E(245)^67 + 17/2*E(245)^68 - 5/2*E(245)^69 + 337/13*E(245)^71 - E(245)^72 - 3*E(245)^73 + 89/2*E(245)^74 + 2*E(245)^76 + 2*E(245)^77 + 25/2*E(245)^78 + 11/2*E(245)^79 - 7/4*E(245)^81 + 29/6*E(245)^82 + 123/244*E(245)^84 - 4/3*E(245)^86 - 13/12*E(245)^87 + 79/20*E(245)^89 - 1/3*E(245)^91 - 5/2*E(245)^92 - 49/4*E(245)^94 + 14/3*E(245)^96 + 6/5*E(245)^97 - 64*E(245)^99 - 2*E(245)^101 + 1/3*E(245)^104 + 1/2*E(245)^106 - 3/2*E(245)^107 - 141/140*E(245)^109 + 6*E(245)^111 - 3/2*E(245)^114 - 19/6*E(245)^116 + 35/6*E(245)^117 - 3/2*E(245)^118 - 1/2*E(245)^119 - 37/12*E(245)^122 - 4*E(245)^123 - 3*E(245)^124 - 5/2*E(245)^126 - 4*E(245)^127 - 1/2*E(245)^128 - 13/4*E(245)^129 + 11/2*E(245)^131 + 5/2*E(245)^133 - 1/2*E(245)^134 - 1/2*E(245)^136 + 19/4*E(245)^138 + 1/2*E(245)^139 - 2*E(245)^141 - 5*E(245)^143 - 7/2*E(245)^144 + E(245)^146 - 129/2*E(245)^148 - 383/2*E(245)^149 + 37*E(245)^151 + 3/2*E(245)^153 - 1/85*E(245)^156 - 1541/140*E(245)^158 + 83/22*E(245)^159 + E(245)^163 - 481/92*E(245)^164 + 11/2*E(245)^166 + 15/34*E(245)^167 + 2*E(245)^168 + 27*E(245)^169 - 2*E(245)^171 - E(245)^172 + 6*E(245)^173 + E(245)^174 - E(245)^176 + 4*E(245)^177 - 3*E(245)^178 - 11/4*E(245)^179 + 3/2*E(245)^182 - 5/2*E(245)^183 - 5/2*E(245)^184 + 61/12*E(245)^187 + 1/2*E(245)^188 - 1/3*E(245)^189 - 49/12*E(245)^192 - 5*E(245)^193 + 14/3*E(245)^194 - 66*E(245)^197 - 9/4*E(245)^199 + 3*E(245)^202 + 2*E(245)^203 + 3*E(245)^204 - 141/140*E(245)^207 + 105/22*E(245)^208 + 2*E(245)^209 + 2*E(245)^212 - 6*E(245)^213 - 13/6*E(245)^214 - 1/2*E(245)^216 + E(245)^217 + 53/2*E(245)^218 - 1/2*E(245)^219 + 19/3*E(245)^222 + E(245)^223 + 3*E(245)^226 - 25/12*E(245)^227 - 15/4*E(245)^228 + 9/2*E(245)^229 + 1/2*E(245)^231 - 4*E(245)^232 - 2*E(245)^233 - 9/4*E(245)^234 + 19/4*E(245)^236 + 5/2*E(245)^237 + 5/3*E(245)^238 - 4*E(245)^241 - 3*E(245)^242 + 17/3*E(245)^243 - E(245)^244
```

### comment:1 Changed 9 years ago by nbruin

I think the code tries to put denominators in `cdef int` which of course quickly goes wrong:

```sage: UCF.<E> = UniversalCyclotomicField()
sage: (1/(2**31-1)*E(2,1)+E(3,2))**2
OverflowError: value too large to convert to int
```

especially if you clear denominator by taking an `LCM` of a (long) list of rational coefficients.

### comment:2 follow-up: ↓ 3 Changed 9 years ago by mraum

• Status changed from new to needs_review

### comment:3 in reply to: ↑ 2 Changed 9 years ago by stumpc5

Thanks for providing a patch, and for cleaning some of my rudimentary coding in cython!

Have you done some tests do check how your changes influenced the performance? I can do some tests, but I think it would also be good to check if there are no new memory leaks in the code...

Cheers, Christian

### comment:4 follow-up: ↓ 5 Changed 9 years ago by mraum

You can check whether malloc's and free's match and whether for each init there is one clear.

I haven't tested performance, but since I consider the previous version as partially incorrect (it fails to work for the very common example given in the description), this is not so much a matter for me. If you want such test, I can provided them at some point in summer.

### comment:5 in reply to: ↑ 4 Changed 9 years ago by stumpc5

I haven't tested performance.

Here are some tests; I for myself don't care that the performance goes down quite a bit - maybe someone can do a similar test to see if the difference is indeed that big (the tests can only be performed if #14497 is applied). But I would prefer to avoid it, if easily possible.

• without the patch
```sage: UCF.<E> = UniversalCyclotomicField()
sage: %timeit UCF.random_element(150)
1000 loops, best of 3: 422 us per loop

sage: %timeit UCF.random_element(150)^2
1000 loops, best of 3: 1.14 ms per loop

sage: %timeit UCF.random_element(151)
1000 loops, best of 3: 960 us per loop

sage: %timeit UCF.random_element(151)^2
100 loops, best of 3: 3.37 ms per loop
```
• with the patch
```sage: UCF.<E> = UniversalCyclotomicField()
sage: %timeit UCF.random_element(150)
1000 loops, best of 3: 423 us per loop

sage: %timeit UCF.random_element(150)^2
1000 loops, best of 3: 1.51 ms per loop

sage: %timeit UCF.random_element(151)
1000 loops, best of 3: 980 us per loop

sage: %timeit UCF.random_element(151)^2
100 loops, best of 3: 8.88 ms per loop
```

### comment:6 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:7 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:8 Changed 8 years ago by rws

• Status changed from needs_review to needs_work
• Work issues set to assess performance impact

### comment:9 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:10 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:11 Changed 7 years ago by vdelecroix

Hello,

In #18152, I reimplemented the universal cyclotomic field using libgap (faster and more reliable). In that version the issue disappears. My goal would be to close this ticket as "won't fix" as soon as #18152 would be reviewed.

Vincent

### comment:12 Changed 7 years ago by chapoton

• Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
• Status changed from needs_work to needs_review

now works with the libgap version.

### comment:13 Changed 7 years ago by mmezzarobba

• Status changed from needs_review to positive_review

### comment:14 Changed 7 years ago by vbraun

• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.