Calculating factorials with numbers bigger than in

Question

Been searching here and google for a couple of days as well as asking my programming friends. Unfortunately, i still don't understand how to change my code...

My program calculates the factorial of a given number. It then provides a number which represents how many digits the factorials answer includes. Then it sums the values of those digits together to give a total.

My program works for any number between 1! and 31!... If you put in anything over 31! (for example 50! or 100!) it doesn't work and just throws back minus numbers and no total.

I was hoping you guys could point me in the right direction or give me some advice. I understand using BigIntegers maybe a solution however i don't understand them personally, hence coming here.

Any help would be much appreciated. Thanks.

    package java20;

    /**
    * Program to calculate the factorial of a given number.
    * Once implemented, it will calculate how many digits the answer includes.
    * It will then sum these digits together to provide a total.
     * @author shardy
     * date: 30/09/2012
     */

    //import java.math.BigInteger;
    public class Java20 {

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {

    //Using given number stored in factorialNo, calculates factorial
    //currently only works for numbers between 1! and 31! :(
        int fact= 1;
        int factorialNo = 10;

        for (int i = 1; i <= factorialNo; i++)
            {
               fact=fact*i;
            }

        System.out.println("The factorial of " + factorialNo + 
                " (or " + factorialNo + "!) is: " + fact);

        //Using answer stored in fact, calculates how many digits the answer has
        final int answerNo = fact;
        final int digits = 1 + (int)Math.floor(Math.log10(answerNo));

        System.out.println("The number of digits in the factorials "
                + "answer is: " + digits);        

        //Using remainders, calculates each digits value and sums them together
        int number = fact;
        int reminder;
        int sum = 0;

        while(number>=1)
            {
             reminder=number%10; 
             sum=sum+reminder;
             number=number/10;
            }

        System.out.println("The total sum of all the " + digits 
                + " idividual digits from the answer of the factorial of " 
                + factorialNo + " is: " + sum);

      }
    }

Answer 1

You can use BigInteger in java, it has as much numbers as you want

    BigInteger fact= BigInteger.ONE;
    int factorialNo = 10;

    for (int i = 2; i <= factorialNo; i++){
      fact = fact.multiply(new BigInteger(String.valueOf(i)));
    }

    System.out.println("The factorial of " + factorialNo +
                                " (or " + factorialNo + "!) is: " + fact);
   final int digits = fact.toString().length();

   BigInteger number = new BigInteger(fact.toString());
   BigInteger reminder;
   BigInteger sum = BigInteger.ZERO;
   BigInteger ten = new BigInteger(String.valueOf(10));

   while(number.compareTo(BigInteger.ONE)>=0)
     {
     reminder=number.mod(ten);
     sum=sum.add(reminder);
     number=number.divide(ten);
     }

     System.out.println("The total sum of all the " + digits
                     + " idividual digits from the answer of the factorial of "
                     + factorialNo + " is: " + sum

EDIT: the code is improved to be compatible with author's code

Answer 2

If you put in anything over 31! (for example 50! or 100!) it doesn't work and just throws back minus numbers and no total.

This is because primitive integer types are subject to overflow when you exceed their maximum possible value. Which computing factorials has a tendency to do.

I was hoping you guys could point me in the right direction or give me some advice. I understand using BigIntegers maybe a solution however i don't understand them personally, hence coming here.

You are correct that using BigInteger is one possible solution. You can, for instance, do something like:

public BigInteger factorial(int num) {
    if (num < 0) {
        throw new IllegalArgumentException("Not today!");
    }

    BigInteger result = BigInteger.ONE;

    for (int next = 2; next <= num; next++) {
        result = result.multiply(new BigInteger(Integer.toString(next, 10)));
    }

    return result;
}

Answer 3

If you're calculating things like (m!/n!), you are better off using logarithms of factorials.

You should also consider these two improvements:

1. Memoize, don't recalculate. Store those hard-earned values once you calculate them.
2. You should be using the gamma function to calculate factorials. The way you're doing it with a loop is the naive thing that is presented to students. There's a nice implementation of ln(gamma(x)) in Numerical Recipes.

You can always use BigDecimal if you must, but it's a last resort. You should still consider these points.

There's a gamma function implementation available from Apache Commons. The source code might not be as familiar as the naive approach, but if you see how it's done it'll be obvious that it's more efficient even for moderate arguments.