[
https://issues.apache.org/jira/browse/NUMBERS-178?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17451235#comment-17451235
]
Alex Herbert commented on NUMBERS-178:
--------------------------------------
{quote}Or could Gamma call the (non-cacheing) implementation in the
combinatorics module?
{quote}
It would be slower than a table look-up.
Here are the ULP differences for various n using the following code:
{code:java}
for (int i = 0; i <= 170; i++) {
double a = Gamma.value(i + 1);
// Implements: n * (n-1) * ... * 3 * 2
double b = factorialDirect(i);
System.out.printf("%3d %25s %s%n", i, a, (a - b) / Math.ulp(a));
}
{code}
||n||ulp||
|70|1|
|80|3|
|90|5|
|100|4|
|120|3|
|145|5|
|170|4|
It seems to drift away at about n=70. Below that the ulp error is 0 or 1.
However the values are reasonably accurate up to the maximum.
I think a single table of 171 double values is an acceptable memory cost. The
FactorialDouble then becomes a very simple class.
> FactorialDouble can tabulate the representable factorials
> ---------------------------------------------------------
>
> Key: NUMBERS-178
> URL: https://issues.apache.org/jira/browse/NUMBERS-178
> Project: Commons Numbers
> Issue Type: Improvement
> Components: combinatorics
> Affects Versions: 1.0
> Reporter: Alex Herbert
> Priority: Trivial
> Fix For: 1.1
>
>
> The updated Gamma function (see NUMBERS-174) tabulates all representable
> factorials.
> This suggests one of the following changes:
> # The FactorialDouble class can call the Gamma function to obtain the values.
> # The FactorialDouble class can also tabulate the values and not use a
> dependency on the Gamma class
> Note that if the call is made to the Gamma class the method is effectively:
> {code:java}
> public static double value(int n) {
> // The Gamma class has all factorial values tabulated.
> return tgamma(n + 1);
> }
> static double tgamma(double z) {
> // Handle integers
> if (Math.rint(z) == z) {
> if (z <= 0) {
> // Pole error
> return Double.NaN;
> }
> if (z <= MAX_GAMMA_Z) {
> // Gamma(n) = (n-1)!
> return FACTORIAL[(int) z - 1];
> }
> // Overflow
> return Double.POSITIVE_INFINITY;
> }
> // ... Not used
> }
> {code}
> So calling the Gamma method has a round trip of the integer to a double, a
> check it is an integer, then a conversion back to an integer.
> The FactorialDouble class also has a cache of the values. So all the values
> are precomputed once and stored for the instance.
> I suggest updating the class to remove the cache and just storing the 171
> representable double values for values up to 170!. The public API can remain
> the same but the cache methods marked as deprecated. The value method then
> becomes:
> {code:java}
> public double value(int n) {
> if (n < 0) {
> throw new CombinatoricsException(CombinatoricsException.NEGATIVE,
> n);
> }
> if (n < FACTORIAL.length) {
> // Cache of precomputed values up to 170!
> return FACTORIAL[n];
> }
> return Double.POSITIVE_INFINITY;
> }
> {code}
> Note:
> This class is a similar implementation to the LogFactorial class. In that
> case the maximum representable LogFactorial is very big and the cache
> functionality makes sense. For a maximum cache size of 171 this caching
> functionality seems unnecessary.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
