Factorial in Java

Question

I've been using this factorial program for Java:

public static long factorial(int a) {

    if(a<1) {
        return 1;
    }
    long result=1;
    long x=a;
    while(x>1) {
        result*=x;                     
        x--;
    }
    return result;
}

However, it seems to "break" and return a negative number after the factorial of 25. It returns a negative number for a while then just returns "0."

Am I doing anything wrong that is causing this?

Do you know anything about the biggest number and int can hold, and is this your homework? — dann.dev, Mar 15 '12 at 00:43
This isn't my homework, this is my fun work :) (I'm a geek). I would never ask for help like this for my homework. I don't know anything about the biggest number an int can hold. I'll look it up in the docs. — Toby, Mar 15 '12 at 00:47
My bad, meant long, but the principle stands regardless of type, check out http://en.wikipedia.org/wiki/Integer_overflow as it explains what happens pretty well — dann.dev, Mar 15 '12 at 00:57
possible duplicate of [Why does Java think that the product of all numbers from 10 to 99 is 0?](http://stackoverflow.com/questions/26375932/why-does-java-think-that-the-product-of-all-numbers-from-10-to-99-is-0) — Izkata, Oct 15 '14 at 21:51

score 7 · Answer 1 · answered Mar 15 '12 at 00:43

7

You've overflowed long.
Use BigInteger instead.

answered Mar 15 '12 at 00:43

SLaks

868,454
176
1,908
1,964

Nice page, makes me dizzy after awhile though! – dann.dev Mar 15 '12 at 01:01
I've been having some trouble using BigIntegers, would I convert the long to a BigInteger right before return? – Toby Mar 15 '12 at 01:18
@Toby - no, instead of `long result;`, you'd have `BigInteger result; ` and your multiplication would look like this: `result = result.multiply(BigInteger.valueOf(x));` – blazeroni Mar 15 '12 at 01:30

score 4 · Answer 2 · answered Mar 15 '12 at 00:58

4

25! = 15511210043330985984000000

The maximum value of a long in Java is 2^63-1 = 9223372036854775807 (source).

25! is about 1.7*10^6 the size of the largest value a long can store in Java. Use a BigInteger instead.

answered Mar 15 '12 at 00:58

jonmorgan

2,570
2
22
27

score 3 · Answer 3 · answered Mar 15 '12 at 00:45

3

25! is bigger than Long.MAX_VALUE...

answered Mar 15 '12 at 00:45

Oliver Charlesworth

267,707
33
569
680

score 1 · Answer 4 · answered Oct 06 '14 at 07:09

Overflow (and underflow) is silent according to the JLS, which is why your result was a "surprise".

You have two choices:

if an exact answer is required, use BigInteger
if exactness is not required, use double (although even that will overflow past 170!)

DrewHoo · Answer 5 · 2015-10-05T18:55:14.203

Here's what you're missing: when a signed integer primitive type (such as short, int, long) gets incremented above a signed value that it can represent, it tries to flip its sign bit, which is the leftmost bit, which is only supposed to be used to indicate the sign of the number. 1 in the sign bit indicates a negative value. This phenomenon is called integer overflow.

Consider a fictional 3-bit signed primitive data type (for comparison, a Java long is 64 bits). It can represent numbers between -4 and 3.

3, the biggest positive value a 3-bit number can represent, looks like this: 011

add 1 to 011 and you get: 100 (the number part overflows into the sign part)

the decimal version of 100 is -4

However, when you get to dealing with the capacity of a long, there are a lot of digits to count, so here's a quick way to determine the biggest number defined by a given nondecreasing sequence (in this case, factorial):

long n = 1;
while (factorial(n) > 0) {
    System.out.println("factorial of " + n++ + " can fit in a long!");
}

This looks like it ought to be an infinite loop, but it isn't; eventually, factorial(n) will return negative due to integer overflow. This will give you the following output:

factorial of 1 can fit in a long!
factorial of 2 can fit in a long!
factorial of 3 can fit in a long!
factorial of 4 can fit in a long!
factorial of 5 can fit in a long!
factorial of 6 can fit in a long!
factorial of 7 can fit in a long!
factorial of 8 can fit in a long!
factorial of 9 can fit in a long!
factorial of 10 can fit in a long!
factorial of 11 can fit in a long!
factorial of 12 can fit in a long!
factorial of 13 can fit in a long!
factorial of 14 can fit in a long!
factorial of 15 can fit in a long!
factorial of 16 can fit in a long!
factorial of 17 can fit in a long!
factorial of 18 can fit in a long!
factorial of 19 can fit in a long!
factorial of 20 can fit in a long!

score 0 · Answer 6 · answered Mar 15 '12 at 00:48

0

Another approach that's less naive and works for non-integer numbers is to use the natural log of the gamma function.

http://www.iro.umontreal.ca/~simardr/ssj/doc/html/umontreal/iro/lecuyer/util/Num.html

If you must persist in using this implementation, I'd recommend that you look into memoization. Why keep recalculating values? Once you have one, hang onto it and just hand it out on repeat requests.

answered Mar 15 '12 at 00:48

duffymo

305,152
44
369
561

That won't help; it will still overflow. – SLaks Mar 15 '12 at 00:48
Eventually, but a double will hang in there a lot longer than a long will. And the natural log will delay it as well. Helpful for combinatorial calculations: just add and subtract natural logs. – duffymo Mar 15 '12 at 00:49

score 0 · Answer 7 · answered Mar 15 '12 at 00:59

Check out http://en.wikipedia.org/wiki/Integer_overflow, I know the title refers to an integer but the principle stands for int, long , double etc.

In short, a primitive datatype has a max value, when you go over that, it wraps aroun and starts again. if you really want to get geeky about it, learn about binary addition to fully understand it.

Factorial in Java

7 Answers7

Linked