1

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

Noobgineer
  • 758
  • 5
  • 10
  • 24

2 Answers2

3

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.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
  • Couldnt i still potentially run into the same issue? Lets say n = 200, then if i try to evaluate 170!/200!, 170! becomes infinity due the limit set by the compiler. – Noobgineer Jun 21 '17 at 14:28
  • You don't evaluate 170! / 200! by computing both factorials. You do it by computing 1.0 / 171 * 1.0 / 172 * ... * 1.0 / 200 . If a term in your sum goes vanishingly small, then given that one of the terms is 1, it will not affect the final result. I only suggest adding the small terms first to give them chance to influence the result. – Bathsheba Jun 21 '17 at 14:29
  • Well, its not a matter of it going vanishingly small, its about how to actually evaluate the expression such that the values arent so large that they become infinity. If 170! is seen as infinity by the compiler, i would need to somehow evaluate 170!/200! at once without the compiler seeing either numerator or denominator as infinity but I dont know how I would get around that. – Noobgineer Jun 21 '17 at 14:31
  • You're being naughty. Don't evaluate the factorials. Do it my way. Pretty please, with sugar on top. – Bathsheba Jun 21 '17 at 14:31
  • @Noobgineer: Since I'm waiting for a C++ project to compile, I thought I'd type out the solution. – Bathsheba Jun 21 '17 at 14:51
  • 1
    Very clean explanation and solution! I learned a lot from this. I need to learn to think more creatively with my code than trying to implement a mirror logical expression. I'd upvote twice if I could. – Noobgineer Jun 21 '17 at 15:25
0

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();
}
Eelco
  • 26
  • 3