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/

```

• Prev by Date: RE: Re: Function as an argument of the function
• Next by Date: puzzling difference in speed
• Previous by thread: Re: Re: Pb Limit ArcTan to : - Infinity
• Next by thread: Re: Efficiency question