[prev in list] [next in list] [prev in thread] [next in thread] 

List:       jakarta-commons-dev
Subject:    [jira] [Commented] (NUMBERS-178) FactorialDouble can tabulate the representable factorials
From:       "Alex Herbert (Jira)" <jira () apache ! org>
Date:       2021-11-30 16:32:00
Message-ID: JIRA.13414358.1638204981000.79541.1638289920006 () Atlassian ! JIRA
[Download RAW message or body]


    [ 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)


[prev in list] [next in list] [prev in thread] [next in thread]