Re: [Boost-users] Generating Multinomial Random Numbers

Subject: Re: [Boost-users] Generating Multinomial Random Numbers
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2011-02-11 10:53:45

AMDG

On 2/11/2011 7:16 AM, Stephan Kitchovitch wrote:
>> The binomial_distribution implementation in the current release is very
> slow for large n.
>> I've written a replacement that should be reasonably fast.  It will be
> released in 1.47.
>
> Do you know for roughly what range of n the binomial_distribution provided
> becomes very slow?

It's O(n).

> It would be useful to know whether computing for, say, n
> approx. 10 or 100 would be efficient.

10 is probably not too bad.  The algorithm used is

bernoulli_distribution<> bernoulli(p);
int result = 0;
for(int i = 0; i < n; ++i)
   if(bernoulli(eng)) ++result;

> I need to generate from a multinomial for a stochastic simulation. n is
> unlikely to be very large, however this generation (as well as some based on
> the gamma distribution) will need to be done at every time step and
> thousands of simulations would need to be executed. For this reason I would
> like to make this generation step as efficient as possible.
>

I'd suggest:
a) Write a function that generates multinomial variates,
    using the current binomial_distribution.
b) If that turns out to be too slow, try the new
    implementation.  It should be a drop-in replacement.
c) If it's still too slow, worry about it then.

> Will it be a while before version 1.47 is released?
>

~ 3 months.  1.46 is in beta, and we have quarterly
releases.

In Christ,
Steven Watanabe