Быстрый поиск каждого (2k) факториала

Question

Мне дано число k, и я должен найти каждый (2k) факториал из [0; k]; например 0, 2 !, 4 !, 6 !, et c. Я попытался сохранить значения на карте и для каждого k-го значения использовать результат (k-1), например:

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);
    }
}

Однако мне было любопытно, есть ли более быстрый подход чтобы найти и сохранить эти c факториалы?

Answer 1

Это не ответ, а скорее расширенный комментарий.

Если ваша цель - вычислить факториалы, вы не сможете серьезно ускориться. Однако я предполагаю, что этот вопрос задан в контексте вашего предыдущего вопроса , касающегося суммирования определенного ряда,

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

Если я прав, ответ - не вычислять факториалы вообще. Вместо этого используйте расписание Хорнера . Ваша сумма может быть выражена как

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

Посмотрите, как исчезают факториалы. Теперь исправьте несколько терминов, которые вы хотите добавить, и обработайте это выражение наизнанку.

Найти количество терминов для достижения желаемой точности - это совершенно другое дело c. Как я уже упоминал в комментарии однажды, теорема Тейлора очень полезна.

Answer 2

Таким образом, одним из возможных решений этой проблемы является использование динамического c программирования и сохранение данных в массиве вместо использования карты.

Я пошел дальше и попытался воссоздать ваш код, используя этот подход (вы сказали 2k! В вашем вопросе, но в вашем коде этого не было, поэтому я реализовал это), и я получил примерно 25% улучшение скорости для большего k. Главный недостаток использования этого подхода заключается в том, что вам необходимо заранее определить размер массива.

Код:

    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];
}

Использование этого подхода со значением k, равным 2500 (5000 с вашим кодом) и вычисляя время выполнения с использованием nanoTime() с использованием моего подхода, у меня есть время для вычисления 20787300, тогда как с вашим кодом у меня есть время для вычисления 27325500.

Вы можете узнать больше о Dynami c программирование здесь .

Answer 3

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

Попробуйте это.

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))));
}

Или вы можете использовать массив вместо 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;
}

и

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