On Mar 31, 2008, at 3:43 PM, John Cremona 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!
Perhaps if you have a bound for the size of the coefficients you
could do a modular approach. Work mod N where the coefficients are
guaranteed to be at most N. Usually I guess N will fit into a single
word, so the polynomial arithmetic will be much faster than working
over ZZ.
david
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
