Universal cyclotomic field breaks for moderate order

[sagetrac-mraum]

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

CC: @stumpc5 @sagetrac-mraum

Component: number fields

Keywords: ucf, overflow

Work Issues: assess performance impact

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

[nbruin]

comment:1

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.

[sagetrac-mraum]

comment:2

Attachment: 14240-universal_cyclotomic_field_mpq.patch.gz

[stumpc5]

comment:3

Replying to @sagetrac-mraum:

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

[sagetrac-mraum]

comment:4

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.

[stumpc5]

comment:5

Replying to @sagetrac-mraum:

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
  

[rwst]

Work Issues: assess performance impact

[videlec]

comment:11

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

[fchapoton]

comment:12

now works with the libgap version.