When calculating the factorial of 100 (100!) with Java using integers I get 0
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.
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.