What is the greatest factorial we can calculate using an int in JAVA 19 ?

I have found calculation is correct up to Factorial(12) using an int to stock the result.

Here is the recursive code I use :

public static int Factorial(int n) {
    if (n >= 13) {
        System.out.println("Trop grand");
        return -1;
    }
    if (n == 0) {
        return 1;
    } else {
        return n * Factorial(n - 1);
    }
}

Do you find the same result ?

Subsidiary question : how would you implement the function with a long variable ?

I tried everything, expected nothing and nothing special happened. (I have to fill this blank)

CodePudding user response：

Not coding in JAVA but int in C/C based languages is signed integer meaning it uses one bit for sign (yes even if you use two's complenment) so in case you have 32/64 bit ints you can use only numbers up to (not inclusive):

2^31 = 2147483648
2^63 = 9223372036854775808

Now looking at first few factorials taken from Fast exact bigint factorial:

[ 0.001 ms ] 1! = 1
[ 0.000 ms ] 2! = 2
[ 0.000 ms ] 3! = 6
[ 0.000 ms ] 4! = 24
[ 0.006 ms ] 5! = 120
[ 0.006 ms ] 6! = 720
[ 0.007 ms ] 7! = 5040
[ 0.005 ms ] 8! = 40320
[ 0.006 ms ] 9! = 362880
[ 0.007 ms ] 10! = 3628800
[ 0.008 ms ] 11! = 39916800
[ 0.012 ms ] 12! = 479001600
            2^31 = 2147483648 <-------------------------
[ 0.013 ms ] 13! = 6227020800
[ 0.014 ms ] 14! = 87178291200
[ 0.016 ms ] 15! = 1307674368000
[ 0.014 ms ] 16! = 20922789888000
[ 0.015 ms ] 17! = 355687428096000
[ 0.017 ms ] 18! = 6402373705728000
[ 0.019 ms ] 19! = 121645100408832000
[ 0.016 ms ] 20! = 2432902008176640000
            2^63 = 9223372036854775808 <-------------------------
[ 0.017 ms ] 21! = 51090942171709440000
[ 0.019 ms ] 22! = 1124000727777607680000                       

So I expect 20! should still fit for 64bit signed ints.

If you use unsigned int you can compute up to twice as much number but in case of 64 bit the 21! is still too big ... To compute more you need bigger bitwidth or disect the result to trailing zeros (either decadic or binary) and have the result in form of 2 integers for example like this:

void fact(int &man,int &exp,int n)      // man * 10^exp = n!
    {
    man=1; exp=0;
    if (n<=1) return;
    int i,j;
    for (i=2;i<=n;i  )
        {
        j=i;
        while (j==0){j/=10; exp  ; }
        man*=j;
        if (man<0){ man=0; exp=0; return; }     // overflow
        while (man==0){ man/=10; exp  ; }
        }
    }

I used it in VCL and 32bit signed ints like this:

int i,m,e;
AnsiString s;
for (i=0;i<40;i  )
    {
    fact(m,e,i);
    s=m; while (e){ s ="0"; e--; } // just print m to s and add e times "0" at the end
    mm_log->Lines->Add(AnsiString().sprintf("%2i! = %s",i,s)); // output to memo
    }

with this output:

 0! = 1
 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 6! = 720
 7! = 5040
 8! = 40320
 9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 19184179200 <- this one is overflowed too
16! = 0
17! = 0
18! = 0
19! = 0
20! = 0
21! = 0
22! = 0
23! = 0
24! = 0
25! = 0
26! = 0
27! = 0
28! = 0
29! = 0
30! = 0
31! = 0
32! = 0
33! = 0
34! = 0
35! = 0
36! = 0
37! = 0
38! = 0
39! = 0

As you can see I could compute up to 14! this way instead of 12! ...

Also You are computing factorial using recursion ... iteration is much better unless you implement fast factorials which has no meaning without big integers.

CodePudding user response：

Theoretically, Java would support factorials up to 2^MAXINT-1. That's a pretty insane number, obviously. Specific JVMs, depending on their implemenation, MAY support even larger values, but this is not required by the language specification.

This is the highest you will be able to fit in a BigInteger. Whether you can actually calculate a number that high depends obviously on how you go about that calculation and how much time you have on hand to perform the calculation.

From the JDK API documentation:

All methods and constructors in this class throw NullPointerException when passed a null object reference for any input parameter. BigInteger must support values in the range -2Integer.MAX_VALUE (exclusive) to 2Integer.MAX_VALUE (exclusive) and may support values outside of that range. An ArithmeticException is thrown when a BigInteger constructor or method would generate a value outside of the supported range.

See The Java™ Language Specification: 4.2.2 Integer Operations