On Mar 31, 2008, at 3:09 PM, William Stein wrote:
> On Mon, Mar 31, 2008 at 12:43 PM, John Cremona
> <[EMAIL PROTECTED]> wrote:
> >
> > There was some discussion a week or so ago about a more efficient
> > implentation of cyclotomic polynomials, which led to trac#2654. I
> > have tried various alternatives of the prototype code posted there,
> > finding that the speed varied enormously as a result of
> > trivial-seeming changes.
> >
> > The key operation needed is to replace f(x) by f(x^m) for various
> > positive integers m, where f is an integer polynomial. Doing
> > {{{
> > f = f(x**m)
> > }}}
> > was very slow, especially for large m. Faster is to apply this
> function:
> > {{{
> > def powsub(f,m):
> > assert m>0
> > if m==1: return f
> > g={}
> > d=f.dict()
> > for i in d:
> > g[m*i]=d[i]
> > return f.parent()(g)
> > }}}
> >
> > Is there a better way? And is this operation needed elsewhere, in
> > which case the function should be available generally?
> >
> > I thought of using sparse polynomials, but the algorithm also needs
> > exact polynomial division whcih (as far as I can see) is not
> available
> > for sparse integer polys.
> >
> > Suggestions welcome, so we can put a decent patch in for this
> > important function!
> >
>
> Hi John,
>
> Sure a special function to compute f(x^n) quickly seems like a good
> idea.
I will second this.
> 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
It's not computing the coefficients that's expensive, it's creating
the polynomial.
sage: import sage.rings.polynomial.cyclotomic as c
sage: time L = c.cyclotomic_coeffs(10^5)
CPU time: 0.00 s, Wall time: 0.00 s
sage: time L = c.cyclotomic_coeffs(10^6)
CPU time: 0.03 s, Wall time: 0.03 s
sage: time L = c.cyclotomic_coeffs(10^7)
CPU time: 0.25 s, Wall time: 0.25 s
This is better than Magma. This is still clearly a bug, an I am
writing a patch to address this.
- Robert
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
