CODEWITHSUNDEEP
javadoublefactorialtruncation
Noobgineer
Noobgineer

Reputation: 768

Calculating the nth factorial

Im writing a function that implements the following expression (1/n!)*(1!+2!+3!+...+n!).

The function is passed the arguement n and I have to return the above statement as a double, truncated to the 6th decimal place. The issue im running into is that the factorial value becomes so large that it becomes infinity (for large values of n).

Here is my code:

public static double going(int n) {
   double factorial = 1.00;
   double result = 0.00, sum = 0.00;

   for(int i=1; i<n+1; i++){
     factorial *= i;
     sum += factorial;
   }
   //Truncate decimals to 6 places
   result = (1/factorial)*(sum);
   long truncate = (long)Math.pow(10,6);
   result = result * truncate;
   long value = (long) result;

   return (double) value / truncate;
}

Now, the above code works fine for say n=5 or n= 113, but anything above n = 170 and my factorial and sum expressions become infinity. Is my approach just not going to work due to the exponential growth of the numbers? And what would be a work around to calculating very large numbers that doesnt impact performance too much (I believe BigInteger is quite slow from looking at similar questions).

Upvotes: 1

Views: 333

Answers (2)

Bathsheba
Bathsheba

Reputation: 234785

You can solve this without evaluating a single factorial.

Your formula simplifies to the considerably simpler, computationally speaking

1!/n! + 2!/n! + 3!/n! + ... + 1

Aside from the first and last terms, a lot of factors actually cancel, which will help the precision of the final result, for example for 3! / n! you only need to multiply 1 / 4 through to 1 / n. What you must not do is to evaluate the factorials and divide them.

If 15 decimal digits of precision is acceptable (which it appears that it is from your question) then you can evaluate this in floating point, adding the small terms first. As you develop the algorithm, you'll notice the terms are related, but be very careful how you exploit that as you risk introducing material imprecision. (I'd consider that as a second step if I were you.)

Here's a prototype implementation. Note that I accumulate all the individual terms in an array first, then I sum them up starting with the smaller terms first. I think it's computationally more accurate to start from the final term (1.0) and work backwards, but that might not be necessary for a series that converges so quickly. Let's do this thoroughly and analyse the results.

private static double evaluate(int n){                        
    double terms[] = new double[n];
    double term = 1.0;
    terms[n - 1] = term;
    while (n > 1){            
        terms[n - 2] = term /= n;
        --n;
    }        
    double sum = 0.0;
    for (double t : terms){
        sum += t;
    }        
    return sum;        
}

You can see how very quickly the first terms become insignificant. I think you only need a few terms to compute the result to the tolerance of a floating point double. Let's devise an algorithm to stop when that point is reached:

The final version. It seems that the series converges so quickly that you don't need to worry about adding small terms first. So you end up with the absolutely beautiful

 private static double evaluate_fast(int n){        
    double sum = 1.0;
    double term = 1.0;
    while (n > 1){
        double old_sum = sum;
        sum += term /= n--;
        if (sum == old_sum){
            // precision exhausted for the type
            break;
        }
    }                
    return sum;        
}

As you can see, there is no need for BigDecimal &c, and certainly never a need to evaluate any factorials.

Upvotes: 3

Eelco
Eelco

Reputation: 26

You could use BigDecimal like this:

public static double going(int n) {
    BigDecimal factorial = BigDecimal.ONE;
    BigDecimal sum = BigDecimal.ZERO;

    BigDecimal result;

    for(int i=1; i<n+1; i++){
        factorial = factorial.multiply(new BigDecimal(i));
        sum = sum.add(factorial);
    }
    //Truncate decimals to 6 places
    result = sum.divide(factorial, 6, RoundingMode.HALF_EVEN);

    return result.doubleValue();
}

Upvotes: 0

Related Questions