On Mon, 31 Mar 2008, 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?
The operation f(x^k)/f(x) can be implemented in a rather pretty way. I don't
know if this would be useful elsewhere -- I'll try and hack this up tonight.
>
> 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!
>
> John
>
> --
> 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
-~----------~----~----~----~------~----~------~--~---
