commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Brent Worden (JIRA)" <j...@apache.org>
Subject [jira] [Issue Comment Edited] (MATH-585) Very slow generation of gamma random variates
Date Fri, 10 Jun 2011 14:44:58 GMT

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

Brent Worden edited comment on MATH-585 at 6/10/11 2:43 PM:
------------------------------------------------------------

Here is a performance improvement suggestion to the implementation in the patch.

Since the loop in calculateQ is always a fixed number of iterations, eliminate it and compute
the polynomial directly.  Also, instead of computing is as a1*v + a2*v^2 + a3*v^3 + ... a9*v^9
use the equivalent form v*(a1 + v*(a2 + v*(a3 + ... + v*(a8 + a9*v)))))))).  This method eliminates
about half of the multiplications needed to compute the polynomial.

Apply the same technique to the loops found in Step 4 (lines 244-250 of MATH585-1.patch) and
in Step 11 (lines 307-318).


      was (Author: brentworden):
    Here is a performance improvement suggestion to the implementation in the patch:

Since the loop in calculateQ is always a fixed number of iterations, eliminate it and compute
the polynomial directly.  Also, instead of computing is as a1*v + a2*v^2 + a3*v^3 + ... a9*v^9
use the equivalent form v*(a1 + v*(a2 + v*(a3 + ... + v*(a8 + a9*v)))))))).  This method eliminates
about half of the multiplications needed to compute the polynomial.

Apply the same technique to the loops found in Step 4 (lines 244-250 of MATH585-1.patch) and
in Step 11 (lines 307-318).

  
> 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