Re: Eulerian numbers
- To: mathgroup at smc.vnet.net
- Subject: [mg30599] Re: [mg30570] Eulerian numbers
- From: Andrzej Kozlowski <andrzej at platon.c.u-tokyo.ac.jp>
- Date: Thu, 30 Aug 2001 03:51:53 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Actually both defintions of Eulerian numbers are due to Knuth. The one
that you are using is from "Concrete Mathematics" and the one
implemented in the Combinatorica package is from "The Art of Computer
Programming, Vol. 3.
This time, unlike in your original message, you changed the defintion of
myE so that it is using dynamic programming just as the Combinatorica
package does. It is indeed true that your function is faster but only
for small k. For example compare:
In[5]:=
Timing[myE[200,3]]
with Timing[Eulerian[200, 4]] and then
Timing[myE[200, 180]] with Timing[Eulerian[200, 181]] and so on.
The difference is of course entirely due to your having the additional
definition myE[n_, 0] = 1 and nothing to do with using a different
definition. If you add an extra line to the Combinatorica package so
that it's definition becomes:
In[1]:=
Eulerian[n_Integer,k_Integer] := Eulerian1[n,k]
In[2]:=
Eulerian1[0,k_] := If [k==1, 1, 0];
Eulerian1[n_,1]=1;
In[4]:=
Eulerian1[n_,k_] :=
Eulerian1[n,k] =k Eulerian1[n-1,k] + (n-k+1) Eulerian1[n-1,k-1];
you will see that its performance becomes identical to your myE.
Andrzej
On Thursday, August 30, 2001, at 04:16 AM, kaimano wrote:
> I must say one thing.
> I was study Eulerian numbers on the book Concrete Mathematics of Knuth.
> His definition is a little different from the definition of Eulerian in
> Combinatorica package.
> The Eulerian[n,k] of Combinatorica is the Eulerian[n,k-1] in the
> definition
> of Knuth.
> So I started by creating a function following the definition of Knuth.
> It was...
>
> In[1]:=
> myE[n_, k_] := myE[n, k] = (k + 1)*myE[n - 1, k] + (n - k)myE[n - 1,
> k - 1]
>
> In[2]:=
> myE[n_, 0] = 1;
> myE[0, k_] = If[k == 0, 1, 0];
>
> Now if you try myE[20,6] and myE[200,10] ( that are the same of
> Eulerian[20,7] and Eulerian[200,11] of Combinatorica ), you can see the
> difference in speed.
> I started with a fresh kernel.
>
> In[4]:=
> Timing[myE[20, 6]]
>
> Out[4]=
> {0.0166667 Second, 21598596303099900}
>
> In[5]:=
> Timing[myE[200, 10]]
>
> Out[5]=
> {0.466667 Second,
> 1899050754604760049211351181228068537387060655311436868149953520589342707921
> 5790445685705492689676781304076126272845459176625102391212461352771213219691
> 738709541822824645767929887525587548776228868638648561016}
>
> I'm working on a 300MHz G3 iBook.
> Now it's enough to define myEulerian[n_,k_] as myE[n,k-1]
> There's something I still don't understand.
>
> Tiziano Mosconi
>
>
>> Da: Andrzej Kozlowski <andrzej at tuins.ac.jp>
>> Data: Wed, 29 Aug 2001 21:48:41 +0900
>> A: kaimano <unrealkaiman at libero.it>
>> Cc: mathgroup at smc.vnet.net
>> Oggetto: Re: [mg30570] Eulerian numbers
>>
>> 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,\
>>
> 1899050754604760049211351181228068537387060655311436868149953520589342707921
> 57> \
>>
> 9044568570549268967678130407612627284545917662510239121246135277121321969173
> 87> \
>> 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
>>>
>>>
>>
>
>