CODEWITHSUNDEEP
javafactorial
Toby
Toby

Reputation: 735

Factorial in Java

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?

Upvotes: 4

Views: 5434

Answers (7)

DrewHoo
DrewHoo

Reputation: 27

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!

Upvotes: 0

Bohemian
Bohemian

Reputation: 425348

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

Upvotes: 1

dann.dev
dann.dev

Reputation: 2494

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.

Upvotes: 0

jonmorgan
jonmorgan

Reputation: 2610

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.

Upvotes: 4

duffymo
duffymo

Reputation: 309008

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.

Upvotes: 0

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272752

25! is bigger than Long.MAX_VALUE...

Upvotes: 3

SLaks
SLaks

Reputation: 888177

You've overflowed long.
Use BigInteger instead.

Upvotes: 7

Related Questions