CODEWITHSUNDEEP
javalong-integerfactorialinteger-overflow
Matt Andrzejczuk
Matt Andrzejczuk

Reputation: 2066

Factorial function produces wrong result for 21! and above

for (int i = 0; i <= 25; i++)
    System.out.printf("%d! = %,d\n", i, factorial(i));

The code above initializes the factorial method below: 

public static long factorial(int num1)
{
    if (num1 == 0)
        return 1;
    else
        return Math.abs(num1 * factorial(num1 - 1));
}

As so the following output is created:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880
10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6,227,020,800
14! = 87,178,291,200
15! = 1,307,674,368,000
16! = 20,922,789,888,000
17! = 355,687,428,096,000
18! = 6,402,373,705,728,000
19! = 121,645,100,408,832,000
20! = 2,432,902,008,176,640,000
21! = 4,249,290,049,419,214,848
22! = 1,250,660,718,674,968,576
23! = 8,128,291,617,894,825,984
24! = 7,835,185,981,329,244,160
25! = 7,034,535,277,573,963,776

The result for 21! is wrong (it should be 51,090,942,171,709,440,000), and the result becomes completely haywire for 22! and above. Can anyone explain why?

Upvotes: 4

Views: 1306

Answers (5)

Cory Kendall
Cory Kendall

Reputation: 7314

The values become erratic for the 21st value and above, because the true value is is too big for a long. If you need bigger numbers, use BigInteger.

Upvotes: 7

dreamcrash
dreamcrash

Reputation: 51473

With long you can represent between -9,223,372,036,854,775,808 to +9,223,372,036,854,775,807 (source)so as soon the factorial pass that range you start to get errors.

Upvotes: 2

Charles Boyd
Charles Boyd

Reputation: 316

The maximum value that an long can take in Java is 9,223,372,036,854,775,807 and it overflows after 20!.

You should use BigInteger for computing factorials.

For example:

    BigInteger n = BigInteger.ONE;
    for (int i=1; i<=20; i++) {
        n = n.multiply(BigInteger.valueOf(i));
        System.out.println(i + "! = " + n);
    }

Upvotes: 2

Brian Henry
Brian Henry

Reputation: 3171

It's not obviously erratic. see here. You're pretty good up to 20. after that, I'd start looking at the max value of a long (9223372036854775807).

Upvotes: 0

luk32
luk32

Reputation: 16070

It all seems ok up to the long capacity. And why are you using Math.abs() ?

Upvotes: 0

Related Questions