commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mikkel Meyer Andersen (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-585) Very slow generation of gamma random variates
Date Fri, 10 Jun 2011 09:53:58 GMT

    [ https://issues.apache.org/jira/browse/MATH-585?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13047110#comment-13047110
] 

Mikkel Meyer Andersen commented on MATH-585:
--------------------------------------------

Algorithm SA (Ahrens) from p. 876 in the above is faster than the inversion-based exponential
sampling. A couple of tests:

Generating 100000 random Exp(1.0) with mean 1.0 and var 1.0
nextOldExponential took 120.0 ms. with mean 0.9962712206756855 and var 0.9983243442732745
nextExponential took 20.0 ms. with mean 0.9958227425469129 and var 0.9990279223847179

Generating 10000000 random Exp(1.0) with mean 1.0 and var 1.0
nextOldExponential took 671.0 ms. with mean 1.0009038221005877 and var 1.001436791894477
nextExponential took 548.0 ms. with mean 1.0000246277478757 and var 0.9996828540541313

Generating 10000000 random Exp(12.23) with mean 12.23 and var 149.5729
nextOldExponential took 671.0 ms. with mean 12.229128607001826 and var 149.4295066207314
nextExponential took 543.0 ms. with mean 12.233285138487334 and var 149.55112465876087

Generating 10000000 random Exp(0.0013) with mean 0.0013 and var 1.69E-6
nextOldExponential took 669.0 ms. with mean 0.0012998098500627037 and var 1.6880018139800875E-6
nextExponential took 544.0 ms. with mean 0.0013003604434494178 and var 1.6893988569492528E-6

Generating 10000000 random Exp(6.0) with mean 6.0 and var 36.0
nextOldExponential took 687.0 ms. with mean 5.999958564653789 and var 36.008520922357725
nextExponential took 606.0 ms. with mean 5.997436087619412 and var 35.95429173708095

I'm not sure how much it will improve the new Gamma, because exponentials are rarely sampled
(only in about 1-2% in average of the times, I guess).

> Very slow generation of gamma random variates
> ---------------------------------------------
>
>                 Key: MATH-585
>                 URL: https://issues.apache.org/jira/browse/MATH-585
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 2.2, 3.0
>         Environment: All
>            Reporter: Darren Wilkinson
>            Assignee: Mikkel Meyer Andersen
>              Labels: Gamma, Random
>         Attachments: MATH585-1.patch
>
>   Original Estimate: 6h
>  Remaining Estimate: 6h
>
> The current implementation of gamma random variate generation works, but uses an inversion
method. This is well-known to be a bad idea. Usually a carefully constructed rejection procedure
is used. To give an idea of the magnitude of the problem, the Gamma variate generation in
Parallel COLT is roughly 50 times faster than in Commons Math. 

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

Mime
View raw message