Opened 9 years ago

Closed 7 years ago

#14240 closed defect (fixed)

Universal cyclotomic field breaks for moderate order

Reported by: mraum Owned by: davidloeffler
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: number fields Keywords: ucf, overflow
Cc: stumpc5, mraum Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues: assess performance impact
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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

Attachments (1)

14240-universal_cyclotomic_field_mpq.patch (6.5 KB) - added by mraum 9 years ago.

Download all attachments as: .zip

Change History (15)

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: 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

Replying to 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

comment:4 follow-up: 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

Replying to 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
    

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.