Re^2: Getting Binomial Distribution under Math::Pari (log) and Combinatorial Method

When speed matters (apart from ability to deal with *BIG* number), the performance are:

                 Rate  binomial_log binomial_pari binomial_comb
binomial_log   6164/s            --          -61%          -87%
binomial_pari 15709/s          155%            --          -66%
binomial_comb 45985/s          646%          193%            --
[download]

Regards,
Edward

Comment on Re^2: Getting Binomial Distribution under Math::Pari (log) and Combinatorial Method Download Code

Replies are listed 'Best First'.
Re^3: Getting Binomial Distribution under Math::Pari (log) and Combinatorial Method by tilly (Archbishop) on Mar 24, 2005 at 03:08 UTC
If you just want an approximation, then performance may be better still if you use the fact that from Stirling's formula the log of n! is approximately `log(n*n exp(-n) * sqrt(2PIn)) = nlog(n) - n + (log(2 + log(PI) + log(n))/2` [download] Plug that into the fact that n choose m is n!/(m!(n-m)!) and you can come up with a good approximation that uses Perl's native arithmetic. This approximation may well turn out to be the fastest approach for large numbers. Update: From Mathworld I just found out that a significantly better approximation of n! is `sqrt(2nPI + 1/3)n*n/exp(n)`. Algebraically this is less convenient, but the improved accuracy may matter for whatever you're trying to do.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: Getting Binomial Distribution under Math::Pari (log) and Combinatorial Method
by tilly (Archbishop) on Mar 24, 2005 at 03:08 UTC

log(n**n * exp(-n) * sqrt(2*PI*n))
  = n*log(n) - n + (log(2 + log(PI) + log(n))/2
[download]

This approximation may well turn out to be the fastest approach for large numbers.

Update: From Mathworld I just found out that a significantly better approximation of n! is sqrt(2*n*PI + 1/3)*n**n/exp(n). Algebraically this is less convenient, but the improved accuracy may matter for whatever you're trying to do.

[reply]
[d/l]
[select]