What is the time complexity of calculating factorial n! using Java's BigInteger

Question

Suppose the algorithm is as below:

public static BigInteger getFactorial(int num) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= num; i++)
        fact = fact.multiply(BigInteger.valueOf(i)); // ? time complexity
    return fact;
}

It seems hard to calculate number of digits of fact.

Optimized version:

    public BigInteger getFactorial2(long n) {
        return subFactorial(1, n);
    }
    private BigInteger subFactorial(long a, long b) {
        if ((b - a) < 10) {
            BigInteger res = BigInteger.ONE;
            for (long i = a; i <= b; i++) {
                res = res.multiply(BigInteger.valueOf(i));
            }
            return res;
        } else {
            long mid = a + (b - a) / 2;
            return subFactorial(a, mid).multiply(subFactorial(mid + 1, b));
        }
    }

The number of digits in `fact` is `log(fact)`, and `O(log(n!)) == O(nlogn)` as described [in this answer](https://stackoverflow.com/q/8118221/6221024). From that, just apply whatever multiplication algorithm `BigInteger` uses. — Dillon Davis, Mar 07 '19 at 06:31
Hi @DillonDavis, Thank you, If BigInteger use Karatsuba multiplication, with O(x ** 1.585), will the total complexity be O((nlogn)^1.585)? — Alex Xie, Mar 07 '19 at 06:36
I'm going to be honest, I'm not 100% certain. The two values being multiplied aren't even close to the same size, so the time may be less than `O(x ** 1.585)`, on the other hand we do `num` multiplications, so there could be up to another factor of `n` in there. It is definitely `O((n^2logn)^1.585)`, but there may very well be a tighter upper bound. — Dillon Davis, Mar 07 '19 at 06:41
In fact, using grade school multiplication, we already have `O(logn * (nlogn))` since one of the numbers being multiplied is at most `num` (`n`). So this itself gives `O((nlogn)^2)`, which is better than that other estimate I gave you. — Dillon Davis, Mar 07 '19 at 06:46

score 1 · Answer 1 · answered Mar 07 '19 at 07:15

1

The number of digits contained in fact is log(fact). It can be shown that O(log(n!)) == O(nlogn), so the number of digits in n! grows proportionally to nlogn. Since your algorithm piles values on to a partial product without splitting them into smaller intermediate values (divide and conquer fashion), we can assert that one of the numbers being multiplied will be less than n for calculating n!. Using grade school multiplication, we have O(logn * nlogn) time to multiply each of these numbers, and we have n-1 multiplies, so this is O(n * logn * nlogn) == O((nlogn)^2). I do believe this is a tight upper bound for grade-school multiplication, because even though the beginning multiplications are far smaller, the latter half are all larger than O((n/2)log^2(n/2)), and there are (n/2) of them, so O((n/2)^2 *log^2(n/2)) == O((nlogn)^2).

However, it is entirely possible that BigInteger uses Karatsuba multiplication, Toom-Cook multiplication, or maybe even the Schönhage–Strassen algorithm. I do not know how these perform on integers of such drastically varying sizes (logn vs nlogn), so I cannot give a tight upper bound on those. The best I can do is speculate that it will be less than that of the O(n*F(nlogn)), where F(x) is the time to multiply two numbers of length x using a specific algorithm.

answered Mar 07 '19 at 07:15

Dillon Davis

6,679
2
15
37

AFAIK, Java's BigInteger multiplication uses Karatsuba, Toom-Cook 3-way but no Schönhage-Strassen yet. And of course schoolbook for small values. If the algorithm is not "divide-and-conquered", you are constantly multiplying a quickly growing huge number with a "small" one, which tends to be ssslllooowww. – Rudy Velthuis Mar 07 '19 at 07:36
@RudyVelthuis I agree with your last point, however OP was asking about the time complexity of a specific implementation of the factorial. – Dillon Davis Mar 07 '19 at 07:41
1

correct. I just wanted to point to the flaws of that naive approach. And I wanted to tell which algorithms are used to multiply BigIntegers in Java. FWIW, I just realized that if one of the numbers is below the threshold (and the loop index above is well below that), schoolbook will be used, **so Karatsuba etc. are not used at all, here**. Only schoolbook, unless you use a divide-and-conquer algorithm. – Rudy Velthuis Mar 07 '19 at 07:44
@RudyVelthuis: I tried a few different approaches to computing factorial in [this](https://stackoverflow.com/a/51458972/238704) answer. Arranging things to purposefully take advantage of the more sophisticated algorithms was noticeably faster. – President James K. Polk Mar 07 '19 at 14:22
@JamesKPolk depending on how relatively quickly we can sieve primes up to `n`, it may be even faster to use [knowledge of the prime factorization of n!](https://math.stackexchange.com/a/642220/650428) and exponentiation by squaring (under the hood in `BigInteger`) to obtain the results faster. – Dillon Davis Mar 07 '19 at 19:37

What is the time complexity of calculating factorial n! using Java's BigInteger

1 Answers1