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/