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
>
>