commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alexey Dievsky <diev...@gmail.com>
Subject Re: Fwd: [Math] Tabulated logarithmic factorial
Date Thu, 19 Nov 2015 11:29:01 GMT
Hi Gilles,

thanks for your response. I've run a small JMH benchmark of both old
(direct summation) and new (default 16KB tabulation) approaches, and here
are the results:

Benchmark                                           Mode  Samples
Score      Error   Units
o.a.c.m.s.FactorialLogBench.newFactorialLog100     thrpt       20
75066.697 ± 7122.980  ops/ms
o.a.c.m.s.FactorialLogBench.newFactorialLog1000    thrpt       20
76905.243 ± 5965.782  ops/ms
o.a.c.m.s.FactorialLogBench.newFactorialLog10K     thrpt       20  5770.486
± 285.069  ops/ms
o.a.c.m.s.FactorialLogBench.newFactorialLog100K    thrpt       20  6156.102
± 278.842  ops/ms
o.a.c.m.s.FactorialLogBench.oldFactorialLog100     thrpt       20
585.576 ±   26.802  ops/ms
o.a.c.m.s.FactorialLogBench.oldFactorialLog1000    thrpt       20
29.883 ±    1.663  ops/ms
o.a.c.m.s.FactorialLogBench.oldFactorialLog10K     thrpt       20     2.744
±   0.095  ops/ms
o.a.c.m.s.FactorialLogBench.oldFactorialLog100K    thrpt       20     0.264
±   0.007  ops/ms

Here *100 calculates the factorial of a random number in range [0..99],
*1000 -- of a number in range [900..999], *10K -- of a number in range
[9900..9999], and *100K -- of a number in range [99900..99999]. The default
tabulated version covers the first two cases with a direct lookup, the
third one with a use-the-closest-stored-value approach (about two logs, two
multiplications and two additions on average), and the fourth one delegates
to logGamma.
As you can see, the tabulated (new) approach is about 130x faster on small
numbers and the difference grows drastically from there on, up to about
23000x on fairly big numbers.

Another interesting result is that logGamma doesn't seem to be slower than
the assisted lookup, which possibly indicates that we can drop the assisted
lookup altogether, reducing the memory footprint.

Sincerely,
Aleksei Dievskii.

On Thu, Nov 19, 2015 at 11:18 AM, Gilles <gilles@harfang.homelinux.org>
wrote:

> 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-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message