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

Question

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.

This is not the best way to calculate a factorial. You know that, right? — duffymo, Mar 15 '11 at 20:41
You're loop wouldn't calculate factorial even if you wouldn't get 0. — RoflcoptrException, Mar 15 '11 at 20:41
@Roflcoptr: I think it does, I just tested it for 9 with the correct result. — Trufa, Mar 15 '11 at 20:44
@duffymo Of course! After all, if I want `5!`, I'm not gonna do `5*4*3*2*1`. I'm gonna evaluate `gamma(6)`! — Cole Tobin, Jun 16 '14 at 00:09

Peter Lawrey · Answer 1 · 2011-03-15T21:40:44.360

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.

@Trufa: try this program with printing the (`BigInteger` and `int`) results after every step, to gain more insight. — Paŭlo Ebermann, Mar 15 '11 at 21:02
@PaloEbermann: I did, I actually was able to solve this problem, but was curious about the 0 result. Thanks! — Trufa, Mar 15 '11 at 21:11
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 — Peter Lawrey, Mar 15 '11 at 21:12
@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...) :) — Trufa, Mar 15 '11 at 21:19
@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. ;) — Peter Lawrey, Mar 15 '11 at 21:42

score 22 · Accepted Answer · answered Mar 15 '11 at 20:41

22

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.

answered Mar 15 '11 at 20:41

Jeremiah Willcock

30,161
7
76
78

score 8 · Answer 3 · answered Mar 15 '11 at 21:35

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

score 6 · Answer 4 · answered Mar 15 '11 at 20:47

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.

score 3 · Answer 5 · answered Nov 22 '15 at 02:20

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

score 0 · Answer 6 · edited May 23 '17 at 10:30

0

(Found here, adapted slightly to fit question)

public static void main(String[] args) {

    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= 100; i++)
        fact = fact.multiply(BigInteger.valueOf(i));
    System.out.println(fact);
}

edited May 23 '17 at 10:30

Community

1
1

answered Jul 26 '15 at 09:02

BbJug

90
7

score 0 · Answer 7 · 2018-10-03T07:50:08.600

BigInteger Class in Java. BigInteger class is used for mathematical operation which involves very big integer calculations that are outside the limit of all available primitive data types.

To calculate very large number, we can use BigInteger

Like, If we want to calculate the factorial of 45, answer = 119622220865480194561963161495657715064383733760000000000

 static void extraLongFactorials(int n) {
       BigInteger fact = BigInteger.ONE;
        for(int i=2; i<=n; i++){
            fact = fact.multiply(BigInteger.valueOf(i));
        }
        System.out.println(fact);
    }

Main methods of BigInteger is BigInteger.ONE, BigInteger.ZERO, BigInteger.TEN, BigInteger.ValueOf()

score 0 · Answer 8 · edited Sep 09 '19 at 20:32

import java.util.*;
import java.math.*;
public class BigInteger_Factorial {
    public static void main(String args []){
        Scanner s = new Scanner(System.in);

        BigInteger x,i,fac = new BigInteger("1");
        x = s.nextBigInteger();

        for(i=new BigInteger("1"); i.compareTo(x)<=0; i=i.add(BigInteger.ONE)){
            fac = fac.multiply((i));
        }
        System.out.println(fac);
    }
}

Output of 100 as input:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Output image:

Output result

VIJAY PRATAP SINGH · Answer 9 · 2020-10-13T07:58:50.817

package test2;

import java.math.BigInteger;
import java.util.Scanner;

public class Factorial extends Big {

    public static void main(String args []){ 
    int x,fact=1,i ;
    Scanner sc = new Scanner(System.in);
    
    
    System.out.println("press any dight and 0 to exit");
    while (sc.nextInt()!=0)
    {
    System.out.println("Enter the values ");
    x=sc.nextInt();
    if(x<26)

    {
    for( i=1;i<=x;i++)
    {   fact = fact*i;  }
    
    System.out.println("Factorial of "+x + "is "+ fact );
    
    fact=1;
    }
    else 
    {
        System.out.println("In else big....");
    BigInteger k=fact(x);
    
    System.out.println("The factorial of "+x+"is "+k);
    System.out.println("RESULT LENGTH\n"+k.toString().length());
    }
    System.out.println("press any dight and 0 to exit");
    }
    System.out.println("thanks....");
    }
    
        
    
    
}
//----------------------------------------------------//

package test2;

import java.math.BigInteger;

public class Big {

    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);
    }

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

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 — VIJAY PRATAP SINGH, Oct 13 '20 at 08:00

score -1 · Answer 10 · answered Mar 15 '11 at 20:45

-1

it's an overflow for sure, you can try double, 64 bit long integer are probably too small

answered Mar 15 '11 at 20:45

Julien Vermillard

2,945
1
18
18

Yes, there are -- a quick count shows more than 75 zeros, which is more than the 64 bits in a long. – Jeremiah Willcock Mar 15 '11 at 20:47
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 – Trufa Mar 15 '11 at 20:47
@Trufa: If you only need the result approximately, you could use `double` for this - it would be much faster than BigInteger. – Paŭlo Ebermann Mar 15 '11 at 21:04

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

10 Answers10

Linked