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
>> -----Original Message-----
>> From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]]
>> Behalf Of Ross Levine
>> Sent: 30 December 2008 19:42
>> To: boost_at_[hidden]
>> Subject: [boost] [random] A much faster Poisson variate generation
>> 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
> 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
> 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
> ACM New York, NY, USA
> 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 A. Bristow
> Prizet Farmhouse
> Kendal, UK LA8 8AB
> +44 1539 561830, mobile +44 7714330204
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk