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

Subject: Re: [boost] [random] A much faster Poisson variate generation
From: Paul A. Bristow (pbristow_at_[hidden])
Date: 2009-01-05 10:24:37

Your test promises equivalence (and much improvement) over the existing
code, but are you able to run the existing test?

\boost_1_37_0\libs\random\random_test.cpp

Which tests with

  instantiate_dist(urng, "poisson_distribution",
                   boost::poisson_distribution<>(1));

Are there any limits that can be relaxed now that you have 'debugged' the
'biggish mean' case?

Are your changes likely to cause any problems to existing users?  (breaking
existing systems is unpopular ;-)

If this looks OK, I suspect that someone can just copy this into trunk and
check if all is well?  John Maddock?

Paul

PS The existing authors copyrights in the header should be retained, and
yours added of course, with some notes on the changes made (since they are
quite major in implementation).

And some notes on your changes need to be added to the docs at

/libs/random/index.html

Would you like to suggest working to go in the History and Acknowledgements
section.

I am not clear what tool was used to generate the html, but I suspect we
could cheat and edited by hand for such a small change.

> -----Original Message-----
> From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]]
On
> Behalf Of Ross Levine
> Sent: 31 December 2008 20:43
> To: boost_at_[hidden]
> Subject: Re: [boost] [random] A much faster Poisson variate generation
> 
> 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
> >>
> >
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost