CODEWITHSUNDEEP
javaalgorithmmathoptimization
Mark
Mark

Reputation: 23

Finding fast every (2k) factorial

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?

Upvotes: 1

Views: 177

Answers (3)

user4910279
user4910279

Reputation:

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

Upvotes: 0

ryno
ryno

Reputation: 966

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.

Upvotes: 1

user58697
user58697

Reputation: 7923

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.

Upvotes: 5

Related Questions