0

Possible Duplicate:
Calculate the factorial of an arbitrarily large number, showing all the digits

This question might be asked thousand times here. I am repeating my question with a modification. I want to calculate factorial of a large number (max range of the number=10^6). Generally we uses a for loop from i=1 to i=number and every time multiplying the old value to the new value. This is fine for small numbers but what if i have a large number? The range of for loop is increased now. Java primitive data type int, long can't handle the resultant large number. They simply overflows. Although i knew about BigInteger class, which can handle this large output but still for loop is not suiting better here for me. Can somebody please suggest me any tick, any hack to calculate factorial of a number? Below is the simple program which works fine for small number-

public long getFactorial(long number) {
    long factorial = 1;
    for (long i = 1; i <= number; ++i) {
        factorial *= i;
    }
    return factorial;
}
Community
  • 1
  • 1
ravi
  • 6,140
  • 18
  • 77
  • 154
  • 7
    `1000000!` is `12,815,519` digits long. You're gonna need a "real" bignum library to handle that. – Mysticial Apr 13 '12 at 20:50
  • There are linkedlist/stack based solutions to achieve this. Such as [this](http://www.cs.columbia.edu/~allen/S12/NOTES/BigFactorial.pdf) one – ring bearer Apr 13 '12 at 20:52
  • 1
    @Ravi Joshi: perhaps you should clarify whether you need a precise (BigInteger) answer, or whether an approximation would do. – Ned Batchelder Apr 13 '12 at 21:08
  • @NedBatchelder: I need precise answer. Because this resultant value will be used next. – ravi Apr 13 '12 at 21:12
  • Correction to my first comment: It's `5,565,709` digits. I forgot to divide by `log(10)`. But the point still holds: You need a "real" bignum library with sub-quadratic multiplication - something that Java's BigInteger currently does not have – Mysticial Apr 13 '12 at 21:22
  • http://stackoverflow.com/questions/3125872/unsigned-long-long-wont-go-beyond-the-93th-fibonacci-number – BlueRaja - Danny Pflughoeft Apr 13 '12 at 21:33
  • 1
    I seriously doubt that you need that number. You might think you do, but you're likely to be wrong. And that's as naive a factorial implementation as you could wish for. No ln(gamma), no memoization. You won't get far with this. – duffymo Apr 14 '12 at 01:39

4 Answers4

10

Understand that the value is in the range of 105565708. It's going to take up about two megabytes of space, all by itself.

That said, Guava's BigIntegerMath.factorial(int) is good enough to handle it, and more importantly, it's actually been optimized for large factorials -- it'll do significantly better than a straightforward for loop. (Disclosure: I contribute to Guava...and wrote much of BigIntegerMath.factorial myself.)

That said, I wouldn't exactly call it fast -- my benchmarks indicate an average of 414ms for a factorial in that range -- but there isn't going to be a truly fast solution, not without extremely heavy-duty bignum libraries, and I wouldn't expect even those to be significantly faster.

That's if you need the exact value. If you can settle for the logarithm, then yeah, either use Apache's logGamma(n+1) to get ln(n!), or approximate it yourself:

double logFactorial = 0;
for (int i = 2; i <= n; i++) {
  logFactorial += Math.log(i);
}

Some rounding error will probably accumulate, but it's supposed to be an approximation anyway.

Iulian Popescu
  • 2,595
  • 4
  • 23
  • 31
Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • Cool... But i have to first look over the source code of `factorial` method of `Guava`. I should know the logic. Thank you. – ravi Apr 14 '12 at 08:06
  • 2
    @Louis Wasserman: Do you mean 414 ms for `factorial(1_000_000)`, really? On my computer it takes over 200 seconds. I doubt your computer is 500 times faster than mine. Any explanation? – maaartinus Oct 31 '12 at 16:29
2

You can use an approximation function called Stirling's Formula for such large values of n.

You can refer to my answer here for more details: https://softwareengineering.stackexchange.com/questions/134968/number-of-combinations/134972#134972

Community
  • 1
  • 1
Hunter McMillen
  • 59,865
  • 24
  • 119
  • 170
1

Use the Gamma function. Gamma(i + 1) = i!

org.apache.commons.math.special provides it for Java.

What people typically do is to calculate log(Gamma(i+1)) and then work in log-space (multiplications become additions, etc.).

Here are some other methods to calculate the factorial quickly: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

j13r
  • 2,576
  • 2
  • 21
  • 28
  • I didn't hear about `Gamma` function for calculating factorial. Can you please elaborate it in detail with an example. Thank you. – ravi Apr 13 '12 at 20:59
  • The result won't fit into a `double`. It'll just be `Double.POSITIVE_INFINITY`. Unless the OP is willing to settle for the logarithm of the factorial, this won't be much help. – Louis Wasserman Apr 13 '12 at 21:00
  • @RaviJoshi check again. See the first equation. – j13r Apr 13 '12 at 21:03
  • @LouisWasserman The log of the factorial can be easily stored in a double. – j13r Apr 13 '12 at 21:04
  • Yes, the log can be stored, but the OP didn't indicate that he was interested in the log. I see you've since added some explanation as to how to work with it, though. – Louis Wasserman Apr 13 '12 at 21:09
0

You use BigInteger for factorial, and you still only need a long for i, the loop variable. i only has to go up to 1000000. What's the problem?

Ned Batchelder
  • 364,293
  • 75
  • 561
  • 662
  • Have you analyzed the complexity of this? I'd say it's `O(n^2)`. – Mysticial Apr 13 '12 at 20:53
  • @Mysticial: the question is about how to accomplish it, he was concerned about the limits of the for loop. But it isn't a problem. I'm not sure why you are bringing the time complexity into it. – Ned Batchelder Apr 13 '12 at 20:55
  • I'm saying that it's gonna be impractical to go to any large `i` because the complexity is `O(n^2)`. Java's BigInteger doesn't have the right algorithm to bring it down to quasi-linear. – Mysticial Apr 13 '12 at 20:57
  • The length of the _result_ is going to be `O(n log n)`, and `BigInteger` uses a quadratic multiplication algorithm. I think it might be _worse_ than `O(n^2)`. – Louis Wasserman Apr 13 '12 at 21:11
  • If you do it by bottom-up multiplication, it'll be `O(n^2 log(n))` - regardless of the multiplication algorithm. To go sub-quadratic, you need sub-quadratic multiplication combined with some sort of product balancing technique. – Mysticial Apr 13 '12 at 21:26
  • The key to getting a faster factorial is not to focus on how to multiply, but on what to multiply. For example, here's a Python implementation: http://en.literateprograms.org/Factorials_with_prime_factorization_%28Python%29 On my machine, I got 10**6! in 44 seconds. – Ned Batchelder Apr 13 '12 at 21:34