commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gilles (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-1293) Tabulating the logarithmic factorial
Date Wed, 18 Nov 2015 14:56:11 GMT

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

Gilles commented on MATH-1293:
------------------------------

It's a step in the right direction but at this point, it's only my opinion.
You really should raise the issue on the "dev" ML to potentially get other opinions on how
the optimization must be integrated in future versions of CM.

For example, my idea was that the helper class do not need to bother with a table fixed at
compile time; the constructor of {{FastFactorialLog}} would indeed initialize everything according
to the caller's request (e.g. cache size).
It would be the role of {{CombinatoricsUtils}} to decide how to instantiate a {{FastFactorialLog}}
object; and the policy (e.g. lazy instantiation at the first call to {{factorialLog}} or in
a _static_ block) must be discussed on the "dev" ML.

Since we want to have more flexible interfaces, we might want to test alternative design for
those "small" utilities.
An idea would be to create a function object:
{code}
FastFactorialLog fact = CombinatoricsUtils.createFactorialLog().withCacheSize(1024);
{code}
Then the caller could use the returned object:
{code}
double r = fact.value(123);
{code}
So a user won't depend on how we decided to implement the {{factorialLog}} static function
(and maybe the function should be deprecated if the same functionality and more can be achieved
in a better way).

There might be other suggestion of usability improvements or changes...  So, before you embark
on yet another patch, you should really raise the issue on the ML.  Thanks!


> Tabulating the logarithmic factorial
> ------------------------------------
>
>                 Key: MATH-1293
>                 URL: https://issues.apache.org/jira/browse/MATH-1293
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.5
>            Reporter: Aleksei Dievskii
>            Priority: Minor
>              Labels: feature, patch
>         Attachments: factlog.patch
>
>
> Presently, CombinatoricsUtils#factorialLog is calculated via a tabulated value for the
first 21 entries, and for the rest it employs linear-complexity direct summing. For the factorial-heavy
computations this can be rather painful. I propose a patch which allocates additional 16KB
of tabulated log-factorial values, allowing very fast (constant complexity) computation for
arguments up to 17000, and delegating to the log-gamma for the rest. Benchmarks show a speed-up
of up to 200x.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message