Factorial in Java

Question

I use 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 looks like “break” and returns a negative number after factorial 25. It returns a negative number for a while, and then returns “0”.

Am I doing something wrong, what causes this?

Answer 1

You have overflowed long .
Use BigInteger instead.

Answer 2

25! = 15511210043330985984000000

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

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

Answer 3

25! more than Long.MAX_VALUE ...

Answer 4

Overflow (and underflow) does not work according to JLS, so your result was "unexpected".

You have two options:

• If an exact answer is required, use BigInteger
• If precision is not required, use double (although even this will overflow past 170! )

Answer 5

Another approach, the least naive and working for non-integer numbers, is to use a natural gamma function log.

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

If you must persist in using this implementation, I would recommend that you look into memoization. Why re-read the values? Once you have one, hold on to it and just hand it out on repeated requests.

Answer 6

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

In short, a primitive data type has a maximum value, when you go over it, it shuts down and starts again. if you really want this to cause a craze, check out the binary add-on to fully understand it.

Answer 7

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

Consider a fictitious three-bit type of primitive wildcard data (for comparison, the length of Java is 64 bits). It can represent numbers from -4 to 3.

3, the largest positive value that a 3-bit number can represent is as follows: 011

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

decimal version 100 is -4

However, when you encounter a long ability, there are many numbers to count, so here you can quickly determine the largest number determined by this non-decreasing sequence (in this case, factorial):

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

It seems like it should be an endless loop, but it is not; ultimately, factorial (n) will return a negative result due to integer overflow. This will give you the following result:

 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!