Hello.
On Thu, 19 Nov 2015 10:34:46 +0100, Alexey Dievsky wrote:
Hi,
I recently submitted an issue to JIRA (
https://issues.apache.org/jira/browse/MATH-1293) and received an
advice to
discuss it here.
In short, the current implementation of
CombinatoricsUtils#factorialLog
employs direct summation and thus has linear complexity (O(n)
additions and
O(n) logs). I suggest replacing it with a tabulated lookup. This
solution
will need to allocate some additional memory, but the speed-up for
larger n
would be tremendous. For the values that are too large to be looked
up,
equivalent Gamma#logGamma is still much faster than the existing
algorithm.
I attached a proposed patch to the issue. However, there are a lot of
details that need to be worked out, first and foremost whether such
optimization is at all worth it.
According to your statement above (significantly improved performance),
there
is actually no doubt that the feature should be offered to CM
users.[1][2]
The main question is whether a single speed vs memory (vs possibly
increased
initialization time) trade-off is always acceptable.
Hence at first sight, I'd prefer to provide a factory to create an
object (that will compute the factorial) with a user-defined trade-off.
Regards,
Gilles
[1] It would also be nice if you could provide a benchmark.
[2] A real-life use-case would also be nice to enhance the CM
userguide.
Thus I ask for your opinion. Please let me
know what think.
Sincerely,
Aleksei Dievskii.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
