Re: Efficiency question

*To*: mathgroup at smc.vnet.net*Subject*: [mg34707] Re: [mg34680] Efficiency question*From*: Andrzej Kozlowski <andrzej at platon.c.u-tokyo.ac.jp>*Date*: Sat, 1 Jun 2002 04:29:23 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

First of all your aim is (probably) impossible, or ought to be. If you can write a function that is faster than a built in function while retaining the same level of generality, then it means either that the built-in function is either very badly programmed or is based on an inferior algorithm (of course this may be true if you use a newly discovered algorithm that has not yet been implemented in Mathematica). Otherwise compiled kernel functions enjoy an unbeatable advantage. I can't see any significant improvements, as far as efficiency is concerned, which can be made in your code, but the following version is shorter and slightly faster (on my machine anyway). h[n_] := With[{list = Transpose[FactorInteger[n]][[1]]}, Fold[PolynomialQuotient[#1 /. z -> z^#2, #1, z] &, z - 1, list] /. z -> z^(n/Apply[Times, list])] Andrzej Kozlowski Toyama International University JAPAN htt On Friday, May 31, 2002, at 05:29 PM, Ryan Shannon wrote: > I'm trying to write a function that computes cyclotomic polynomials > faster that Mathematica's built in function, and the best I get is > slower than > it by a factor of three. Can anybody point out any improvements? > > ************************************************************************* > **** > > In[4]:= > \!\(f[n_] := > Module[{list, a = z - 1}, \[IndentingNewLine]list = > Map[First, > FactorInteger[ > n]]; \[IndentingNewLine]q := \((a = > PolynomialQuotient[a /. z \[Rule] z\^#, a, > z])\) &; \[IndentingNewLine]Map[q, > list]; \[IndentingNewLine]a /. > z \[Rule] z\^\(n/Apply[Times, list]\)]\) > > In[5]:= > Timing[Table[f[n],{n,2,2000}];] > > Out[5]= > {40.999 Second,Null} > > In[6]:= > Timing[Table[Cyclotomic[n,z],{n,2,2000}];] > > Out[6]= > {7.141 Second,Null} > > ********************************************************************** > > That function reads like this... > > f[n_]:=Module[{list,a=z-1}, > list=Map[First,FactorInteger[n]]; > q:=(a=PolynomialQuotient[a/.z->z^#,a,z])&; > Map[q,list]; > a/.z->z^(n/Apply[Times,list])] > > On the same note, what are some good resources for learning to program > Mathematica as efficiently as possible (books, websites...)? > > Thanks! > > Ryan Shannon > > > p://platon.c.u-tokyo.ac.jp/andrzej/