[jira] [Issue Comment Edited] (MATH-585) Very slow generation of gamma random variates

["Brent Worden (JIRA)" <ji...@apache.org>]

    [ 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