Re: Eulerian numbers

*To*: mathgroup at smc.vnet.net*Subject*: [mg30579] Re: [mg30570] Eulerian numbers*From*: Andrzej Kozlowski <andrzej at tuins.ac.jp>*Date*: Thu, 30 Aug 2001 03:51:25 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Hm, yours is one of the most puzzling messages I have seen for a long time. The reason is that I just can't believe in your results. On my computer your myEulerian function is vastly slower than that of the Combinatorica package and moreover reason and mathematics suggest that it ought to be so. So something really odd must have happened to produce your results. Let me just demonstrate what happens on my machine. Here is your definition: In[1]:= myEulerian[n_, k_] := k*myEulerian[n - 1, k] + (n - k + 1)myEulerian[n - 1, k - 1]; In[2]:= myEulerian[n_, 1] = 1;myEulerian[0, k_] = If[k == 1, 1, 0]; I do not want even to try to compute your example using your function because on my Machine (400 megahertz PowerBook G4) it will take ages to accomplish this. So let's just use a much smaller case: In[3]:= Timing[myEulerian[20,7]] Out[3]= {4.48 Second,21598596303099900} Now let's try the Combinatorica package: In[4]:= << DiscreteMath`Combinatorica` In[5]:= Timing[Eulerian[20,7]] Out[5]= {0.04 Second,21598596303099900} That's more than 100 times faster. The Combinatorica function has no problem with your original case: In[7]:= Timing[Eulerian[200,11]] Out[7]= {7.18 Second,\ 189905075460476004921135118122806853738706065531143686814995352058934270792157\ 904456857054926896767813040761262728454591766251023912124613527712132196917387\ 09541822824645767929887525587548776228868638648561016} As I said, I doubt your function can manage this in any time that I would care to wait. Moreover, the reasons for this are clear. The Combinatorica defintion uses dynamic programming while your function does not. So in this cost of problem the combinatorica function ought to be vastly faster. The extra definition you have for myEulerian[n_, 1] plays no role. I suggest you carefully repeat your test, starting with a fresh kernel and see what happens. If you still get the same result then...??? Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ On Wednesday, August 29, 2001, at 02:40 PM, kaimano wrote: > I was studying Eulerian numbers and after having defined my own > function I > saw something very strange about the computational time > > Here is my definition....( i know, it lacks the control of the > parameters to > be integers... ) > > myEulerian[n_, k_] := k*myEulerian[n - 1, k] + (n - k + > 1)myEulerian[n - 1, > k - 1]; > myEulerian[n_, 1] = 1;myEulerian[0, k_] = If[k == 1, 1, 0]; > > and here is an example. > > myEulerian[5, 3] > > 66 > > after that I imported the package Combinatorica to make a comparison > with > the function Eulerian[...] defined in it. > > << DiscreteMath`Combinatorica` > > Timing[Eulerian[200, 11]] > > {4.41667 Second, > 1899050754604760049211351181228068537387060655311436868149953520589342707921 > 57\ > 9044568570549268967678130407612627284545917662510239121246135277121321969173 > 87\ > 09541822824645767929887525587548776228868638648561016} > > Timing[myEulerian[200, 11]] > > {0.466667 Second, > 1899050754604760049211351181228068537387060655311436868149953520589342707921 > 57\ > 9044568570549268967678130407612627284545917662510239121246135277121321969173 > 87\ > 09541822824645767929887525587548776228868638648561016} > > With my surprise my function is much faster. > How can this be? > I gave a look inside the Combinatorica.m package and found the > definition of > Eulerian. > > Eulerian[n_Integer, k_Integer] := Eulerian1[n, k] > Eulerian1[0, k_Integer] := If[k == 1, 1, 0] > Eulerian1[n_Integer, k_Integer] := > Eulerian1[n, k] = k Eulerian1[n - 1, k] + (n - k + 1) Eulerian1[n - 1, > k - > 1] > > Why does it lack a definition like > > Eulerian1[n_, 1] = 1; > > that would speed up a lot the program? > Am I not seeing other difficulties? > > Thanks > > Tiziano Mosconi > >