When calculating the factorial of 100 (100!) with Java using integers I get 0

java overflow int factorial

29,283

Solution 1

Big negative numbers are values that overflowed into certain ranges; factorial(100) has more than 32 binary zeros on the end, so converting it to an integer produces zero.

Solution 2

There are 50 even numbers between 1 and 100 inclusive. This means that the factorial is a multiple of 2 at least 50 times, in other words as a binary number the last 50 bits will be 0. (Actually it is more as even second even number is a multiple of 2*2 etc)

public static void main(String... args) {
    BigInteger fact = fact(100);
    System.out.println("fact(100) = " + fact);
    System.out.println("fact(100).longValue() = " + fact.longValue());
    System.out.println("fact(100).intValue() = " + fact.intValue());
    int powerOfTwoCount = 0;
    BigInteger two = BigInteger.valueOf(2);
    while (fact.compareTo(BigInteger.ZERO) > 0 && fact.mod(two).equals(BigInteger.ZERO)) {
        powerOfTwoCount++;
        fact = fact.divide(two);
    }
    System.out.println("fact(100) powers of two = " + powerOfTwoCount);
}

private static BigInteger fact(long n) {
    BigInteger result = BigInteger.ONE;
    for (long i = 2; i <= n; i++)
        result = result.multiply(BigInteger.valueOf(i));
    return result;
}

prints

fact(100) = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
fact(100).longValue() = 0
fact(100).intValue() = 0
fact(100) powers of two = 97

This means a 97-bit integer would be 0 for the lowest bits of fact(100)

In fact, the number of powers of two is very close to n for fact(n). For fact(10000) there are 9995 powers of two. This is because its is approximately the sum of n times powers of 1/2 giving a total close to n. i.e. every second number is even n/2 and every 4th has an additional power of 2 (+n/4) and every 8th has an additional power (+n/8) etc approaches n as a sum.

Solution 3

To have a look at the cause, we could observe the prime factorization of the factorial.

fac( 1) = 1             = 2^0
fac( 2) = 2             = 2^1
fac( 3) = 2 * 3         = 2^1 * 3
fac( 4) = 2 * 2 * 2 * 3 = 2^3 * 3
fac( 5) =  ...          = 2^3 * 3 * 5
fac( 6) = ...           = 2^4 * 3^2 * 5
fac( 7) = ...           = 2^4 * ...
fac( 8) = ...           = 2^7 * ...
fac( 9) = ...           = 2^7 * ...
fac(10) = ...           = 2^8 * ...
fac(11) = ...           = 2^8 * ...
...
fac(29) = ...           = 2^25 * ...
fac(30) = ...           = 2^26 * ...
fac(31) = ...           = 2^26 * ...
fac(32) = ...           = 2^31 * ...
fac(33) = ...           = 2^31 * ...
fac(34) = ...           = 2^32 * ...  <===
fac(35) = ...           = 2^32 * ...
fac(36) = ...           = 2^34 * ...
...
fac(95) = ...           = 2^88 * ...
fac(96) = ...           = 2^93 * ...
fac(97) = ...           = 2^93 * ...
fac(98) = ...           = 2^94 * ...
fac(99) = ...           = 2^94 * ...
fac(100)= ...           = 2^96 * ...

The exponent for the 2 is the number of trailing zeros in the base-2 view, as all other factors are odd, and thus contribute a 1 in the last binary digit to the product.

A similar scheme works for other prime numbers, too, so we can easily calculate the factorization of fac(100):

fac(100) = 2^96 * 3^48 * 5^24 * 7^16 * 11^9 * 13^7 * 17^5 * 19^5 * 23^4 *
           29^3 * 31^2 * 37^2 * 41^2 * 43^2 * 47^2 *
           53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97

So, if our computer stored the numbers in base 3, and had 48-trit-numbers, fac(100) would be 0 (as fac(99), too, but fac(98) would not :-)

Solution 4

Nice problem - answer is: Factorial of 33 (due to negative values) is -2147483648 which is 0x80000000, or 0xFFFFFFFF80000000 if taking 64bits. Multiplying by 34 (the next member) will give a long value of 0xFFFFFFE600000000, which when casting to int will give you 0x00000000.

Obviously from that point onwards you will remain with 0.

Solution 5

Simple solution using recursion and BigIntegers:

    public static BigInteger factorial(int num){
    if (num<=1)
        return BigInteger.ONE;
    else
        return factorial(num-1).multiply(BigInteger.valueOf(num));
    }

Output:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

View more solutions

29,283

Author by

Trufa

Existing code exerts a powerful influence. Its very presence argues that it is both correct and necessary.

Updated on October 13, 2020

Comments

Trufa over 3 years

When doing this:

int x = 100;
int result = 1;
for (int i = 1; i < (x + 1); i++) {
    result = (result * i);
}
System.out.println(result);

This is clearly because the result is too big for an integer, but I am used to get big negative numbers for the overflow, and not 0.

Thanks in advance!

When I switch to this:

int x = 100;
int result = 1;

for (int i = 1; i < (x + 1); i++) {
    result = (result * i);
    System.out.println(result);
}

I get this.

Jeremiah Willcock over 13 years

Yes, there are -- a quick count shows more than 75 zeros, which is more than the 64 bits in a long.
Trufa over 13 years

Hi, thanks! this should be an comment, not an answer, and no, for 100 it would still be too small, the only way is using BigInteger
Paŭlo Ebermann over 13 years

@Trufa: try this program with printing the (BigInteger and int) results after every step, to gain more insight.
Paŭlo Ebermann over 13 years

@Trufa: If you only need the result approximately, you could use double for this - it would be much faster than BigInteger.
Trufa over 13 years

@PaloEbermann: I did, I actually was able to solve this problem, but was curious about the 0 result. Thanks!
Vishy over 13 years

Hopefully I have explained why you get so many 0 bits at the end of the answer which is all you are left with when you do a large factorial. in fact fib(34).intValue() == 0
Trufa over 13 years

@PeterLawrey: I have understood most of your answer, I'm still going through the edit, math doesn't come too quick too me (but it comes...) :)
Vishy over 13 years

@RonK, Thanks for spotting that, changed it before I saw your comment. fib should be short for Fibonacci. fact is a better short name for factorial. Have written these fibonacci/factorial answers too many times. ;)
VIJAY PRATAP SINGH over 3 years

here I have extended this class from Big
VIJAY PRATAP SINGH over 3 years

and maximum values 2450
VIJAY PRATAP SINGH over 3 years

its give limitless factorial program but the best results showing at 2450 and also depends on the hardware ,,System.out.println("RESULT LENGTH\n"+k.toString().length()); is showing results set length