Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Greatest element in list
  • Next by Date: Re: Import numbers and dates
  • Previous by thread: Eulerian numbers
  • Next by thread: Re: Eulerian numbers