Finding fast every (2k) factorial

Question

I am given a number k and I have to find every (2k) factorial from [0;k]; for example 0, 2!, 4!, 6!, etc. I have attempted a solution to save the values in a map and for each kth value to use the (k-1)th result like this:

private Map<Long, BigInteger> cache;

private FactorialCache(int k) {//
    cache = new HashMap<>();
    calculate(k);
    System.out.println("last item " + k);
}

private void calculate(int k) {
    BigInteger result = BigInteger.ONE;
    cache.put(0l, result);
    cache.put(1l, result);

    for (long i = 2; i <= k; i += 1) {
        BigInteger currentRes = cache.get(i - 1).multiply(BigInteger.valueOf(i));
        cache.put(i, currentRes);
    }
}

However, I was curious if there was a faster approach to find and save these specific factorials?

http://www.luschny.de/math/factorial/JuliaFactorial.html will help — Harshal Parekh, Jun 17 '20 at 21:10
Depending on the value of 'k', you might use an array rather than a map. The array can be half the size, if you just store the values for even 'k'. Make use of the fact that `(2k)! = (2(k-1))!*(2k-1)*2k`. — Axel Kemper, Jun 17 '20 at 21:12
As a minor improvement, use the associativity and compute `(2k)!` as `(2k-2)! * ((2k-1)*2k)`, so you multiply a huge number just once. Moreover, you can compute the multiplier as `BigIntger.valueOf((long) (2k-1)*2k)` saving a bit more. — maaartinus, Jun 17 '20 at 22:44
see [Fast exact bigint factorial](https://stackoverflow.com/q/18317648/2521214) its my fast algorithm that computes `(2n)!` from `n!` so its kind of exactly what you asking for — Spektre, Jun 18 '20 at 07:10
Based on your other questions, I guess this is to help you compute sum((3k+1)/(2k)!), but you don't need to cache factorials to compute this; as you sum up the terms, you can keep a variable "F" that stores the current factorial, and then multiply it by the next two integers to get the next factorial. You're making a common mistake which is to micro-optimize a specific part of your code when you don't yet have working code to do the complete task. — Paul Hankin, Jun 18 '20 at 08:10

score 5 · Accepted Answer · answered Jun 17 '20 at 21:37

This is not an answer, but rather an extended comment.

If your goal is to compute factorials, you cannot get seriously faster. However, I assume that this question is asked in the context of your previous question, regarding summation of a certain series,

∑(2k+1)/(2k)! , k =0,... ,∞

If I am correct, the answer is to not compute factorials at all. Use a Horner schedule instead. Your sum can be expressed as

1 + 1/(1*2)(3 + 1/(3*4)(5 + 1/(5*6)(7 + 1/(7*8)(9 + ...)))...)))

See how factorials disappear. Now fix a number of terms you want to add, and work this expression inside out.

Finding a number of terms to achieve a desired precision is a totally different topic. As I mentioned in the comment once, a Taylor theorem is very helpful.

score 1 · Answer 2 · answered Jun 17 '20 at 22:04

So one possible solution to this is using dynamic programming and saving the data in an array rather than using a map.

I went ahead and tried to recreate your code using this approach (you said 2k! in your question, but didn't have that in your code so I did implement that), and I got about a ~25% improvement in speed for larger k. The main drawback of using this approach is you have to define the size of the array beforehand.

The Code:

    public static BigInteger fact(int k, BigInteger[] arr) {
    if (k > 0) {
        arr[0] = BigInteger.valueOf(1);

        k *= 2;
        for (int i = 1; i <= k; ++i) {
            arr[i] = BigInteger.valueOf(i).multiply(arr[i - 1]);
        }
    } else {
        System.out.println("A negative k was entered.");
        return null;
    }
    return arr[k];
}

Using this approach with a k value of 2500 (5000 with your code) and calculating the runtime using nanoTime() using my approach I got a time to compute of 20787300 whereas with your code I got a time to compute of 27325500.

You can read more about dynamic programming here.

score 0 · Answer 3 · 2020-06-17T22:20:11.287

n! = (n - 2)! * n * (n - 1)

Try this.

private void FactorialCache(int k) {
    cache = new HashMap<>();
    BigInteger result = BigInteger.ONE;
    cache.put(0L, result);
    for (long i = 2; i <= k; i += 2)
        cache.put(i, result = result.multiply(BigInteger.valueOf(i * (i - 1))));
}

Or you can use an array instead of Map.

private BigInteger[] Factorials(int k) {
    BigInteger[] results = new BigInteger[k + 1];
    BigInteger result = BigInteger.ONE;
    results[0] = result;
    for (int i = 2; i <= k; i += 2)
        results[i] = result = result.multiply(BigInteger.valueOf(i * (i - 1)));
    return results;
}

and

BigInteger[] results = Factorials(40000);
System.out.println("10! = " + results[10]);
// -> 10! = 3628800

Finding fast every (2k) factorial

3 Answers3