Re: Multinomial coefficients evaluation
- To: mathgroup at smc.vnet.net
- Subject: [mg68133] Re: [mg68105] Multinomial coefficients evaluation
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 25 Jul 2006 04:01:32 -0400 (EDT)
- References: <200607240455.AAA25326@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Michal Kvasnicka wrote:
> Why is function Multinomial so slower than its direct definition??? See
> attached notebook with three equivalent ways of the simple multinomial
> series expansion.
>
> Michal Kvasnicka
It isn't.
What you had, slightly altered for readability and checking of results:
n = 100;
Timing[s1 = Sum[Multinomial[n1,n2,n3]*a1^n1*a2^n2*a3^n3 /.
n3 -> n-n1-n2, {n1,0,n}, {n2,0,n-n1}];]
Timing[s2 = Sum[((n1+n2+n3)!/(n1!*n2!*n3!))*a1^n1*a2^n2*a3^n3 /.
n3 -> n-n1-n2, {n1,0,n}, {n2,0,n-n1}];]
Timing[s3 = Expand[(a1 + a2 + a3)^n];]
On my machine these take about 2.5, 0.42, and 0.04 seconds respectively.
The last is quite fast among other reasons because Expand is free to
take variouas steps that avoid the Mathematica evaluator for Plus.
The real question is why the second is substantially faster than the
first. The speed bump is in evaluation Multinomial[n1,n2,n3] for
symbolic n3. Direct multinomial expansion, avoiding excess symbolic
evaluations, would be along the lines below.
In[5]:= Timing[s1 =
Sum[Multinomial[n1,n2,n-n1-n2]*a1^n1*a2^n2*a3^(n-n1-n2),
{n1,0,n}, {n2,0,n-n1}];]
Out[5]= {0.140009, Null}
In[6]:= Timing[s2 =
Sum[(n!/(n1!*n2!*(n-n1-n2)!))*a1^n1*a2^n2*a3^(n-n1-n2),
{n1,0,n}, {n2,0,n-n1}];]
Out[6]= {0.15601, Null}
In[7]:= s1===s2
Out[7]= True
Daniel Lichtblau
Wolfram Research
- References:
- Multinomial coefficients evaluation
- From: "Michal Kvasnicka" <michal.kvasnicka@quick.nOsPam.cz>
- Multinomial coefficients evaluation