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:43:28

Silly me, I could always just link to it...

http://dl.getdropbox.com/u/416909/poisson_distribution.hpp

And the source file I use to test...

http://dl.getdropbox.com/u/416909/test_pd.cpp

Of special note is that the boost version of the poisson distribution
does not work above mean=745 on my machine, it seems to encounter a
rounding error.

On Wed, Dec 31, 2008 at 3:28 PM, Ross Levine <ross.levine_at_[hidden]> wrote:
> 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
>>
>