That's all very impressive! All that's left from my original observation is this: Let r be the radical of n (= product of distinct primes dividing n) and m=n/r. Then the n'th cyclo poly is f(x^m) where f is the r'th cyclo poly.
So my suggestion had been to first implement the function for square-free numbers, then combine that with the "trivial" substitution of x^m for x. But then I discovered that this was not trivial when applied to actual polynomials. If Robert B's code would simlify for square-free arguments there may still be some gain from this, but it is so fast now that perhaps this is asking too much. John On 01/04/2008, David Harvey <[EMAIL PROTECTED]> wrote: > > > On Mar 31, 2008, at 8:18 PM, Robert Bradshaw wrote: > > >> By the way, I just did some cyclotomic polynomial benchmarking > >> in on Intel Core 2 Duo 2.6Ghz laptop. Here are the results: > >> > >> n | Sage 2.11 | newcyc at #2654 | PARI | Magma > >> 10^5 | 1.29 | 0.37 | 1.24 | 0.02 > >> 10^6 | ? | 32.89 | 123.8 | 0.20 > >> 10^7 | ? | ? | ? | 2.37 > >> > >> Magma crushes everything else yet again... > > > > Fixed up the ZZ[x] constructor, now we crush Magma (I don't feel bad > > taking credit 'cause I wrote the original cyclotomic coefficient > > code). > > > > sage: time f = cyclotomic_polynomial(10^5) > > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s > > Wall time: 0.00 > > sage: time f = cyclotomic_polynomial(10^6) > > CPU times: user 0.01 s, sys: 0.01 s, total: 0.02 s > > Wall time: 0.02 > > sage: time f = cyclotomic_polynomial(10^7) > > CPU times: user 0.15 s, sys: 0.08 s, total: 0.22 s > > Wall time: 0.24 > > > > sage: time f = cyclotomic_polynomial(next_prime(10^5)) > > CPU times: user 0.05 s, sys: 0.01 s, total: 0.05 s > > Wall time: 0.06 > > sage: time f = cyclotomic_polynomial(ZZ.random_element(10^5, 10^6)) > > CPU times: user 0.02 s, sys: 0.00 s, total: 0.03 s > > Wall time: 0.06 > > > > http://trac.sagemath.org/sage_trac/ticket/2654 > > > mate that's awesome. > > > david > > > > > > -- John Cremona --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
