Re: [boost] [random] A much faster Poisson variate generation

Subject: Re: [boost] [random] A much faster Poisson variate generation
From: Ross Levine (ross.levine_at_[hidden])
Date: 2008-12-31 15:28:06

That is the article in question.
The original algorithm was in a pseudo-assembly language. I have
updated it to use binary search and a few other optimizations.
I have tested the class extensively. It is about 15 times faster than
boost::poisson_distribution for _mean=500. At small (<10) means both
are too fast to measure.

As expected, the mean and standard distribution of samples from this
poisson distribution are equal to _mean.
I'm not sure exactly how to post code here. I'm afraid the spaces will
be deleted or something. I'll send it in my next message.

On Wed, Dec 31, 2008 at 1:36 PM, Paul A. Bristow
<pbristow_at_[hidden]> wrote:
>
>
>> -----Original Message-----
>> From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]]
> On
>> Behalf Of Ross Levine
>> Sent: 30 December 2008 19:42
>> To: boost_at_[hidden]
>> Subject: [boost] [random] A much faster Poisson variate generation
>>
>> Hello,
>> I have modified the poisson_distribution class to use an updated
>> version of Ahrens and Dieter's PD algorithm for generating Poisson
>> variates, as described in "Computer Generation of Poisson Deviates
>> from Modified Normal Distributions." Is this allowed in Boost, and is
>> there interest? The current algorithm is O(mean), while PD is bounded
>> time. In addition, the current implementation fails for mean >> 750.
>> PD does, however, use a lookup table and thus has a non-trivial
>> constructor and needs 36 * sizeof(RealType) + 1 * sizeof(IntType)
>> bytes per poisson_distribution object.
>> Please let me know if this is desired.
>
> Is this http://doi.acm.org/10.1145/355993.355997
>
> aka
>
> Computer Generation of Poisson Deviates from Modified Normal Distributions
> Full text       PdfPdf (791 KB)
> Source  ACM Transactions on Mathematical Software (TOMS) archive
> Volume 8 ,  Issue 2  (June 1982) table of contents
> Pages: 163 - 179
> Year of Publication: 1982
> ISSN:0098-3500
> Authors
> J. H. Ahrens     Department of Mathematics, University of Kiel, D 2300 Kiel,
> Olshausenstrasse 40-60, West Germany
> U. Dieter        Institute of Statistics, Technical University, A 8010 Graz,
> Hamerlinggasse 6, Austria
> Publisher
> ACM  New York, NY, USA
> Bibliometrics
> Downloads (6 Weeks): 34,   Downloads (12 Months): 280,   Citation Count: 5
>
> (This requires a subscription to ACM)
>
> Or is it a later improved version?
>
> Sounds useful, but I expect can you provide some tests to show equivalence
> and enhancedness?
>
> Paul
>
>
> ---
> Paul A. Bristow
> Prizet Farmhouse
> Kendal, UK   LA8 8AB
> [phone], mobile [phone]
> pbristow_at_[hidden]
>
>
>
>
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>