Самый быстрый факториал

Рейтинг: 40Ответов: 5Опубликовано: 28.01.2011

Столкнулся с интересной задачкой. Как посчитать факториал числа самым быстрым способом? Быстрее чем за O(n). Подкиньте идею.

c# математика алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 27Принят

Типы со знаком (signed)

Самый быстрый алгоритм вычисления факториала числа с типом int - это использование таблицы. Так как переполнение int приводит к неопределенному поведению (UB), то максимальное значение факториала ограничено INT_MAX.

Для 32-разрядного int максимальный факториал это fac(12) = 479001600, по этому самая быстрая функция вычисления факториала int32_t выглядит так:

std::int32_t fac(std::int32_t x) {
    static const int table[] = {
        1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600,
    };
    assert(x >= 0);
    assert(x <= 12);
    return table[x];
}

Типы без знака (unsigned)

Для unsigned int всё интереснее, он может переполняться, но fac(34) имеет множитель 2^32:

fac(34) = 0xde1bc4d19efcac82445da75b'0000'0000

Поэтому начиная с 34 все результаты fac(uint32_t) будут равны нулю.

64-разрядные типы

Для 64-разрядных чисел переполнение происходит после fac(20), нули начиная с fac(66).

Таким образом, использование таблицы факториалов из 66 элементов покроет всех типы до 64 разрядов:

#include <cassert>
#include <cstdint>
#include <iostream>

// Таблица длинная, по этому посчитаем ее во время компиляции (С++14).
template<int N>
struct Table {
    constexpr Table() : t() {
        t[0] = 1;
        for (auto i = 1; i < N; ++i)
            t[i] = t[i - 1] * i; 
    }
    std::uint64_t t[N];
};

template<typename T>
T fac(T x) {
    static_assert(sizeof(T) <= sizeof(std::uint64_t), "T is too large");
    constexpr auto table = Table<66>();
    assert(x >= 0);
    return x < 66 ? static_cast<T>(table.t[x]) : 0;
}

int main() {    
    for (unsigned long long i = 0; i != 70; ++i) {
        std::cout << i << ": " << fac(i) << '\n';
    }
}
▲ 21

Вот есть интересная статейка. Там предлагают считать факториал за O(loglogn*M(nlogn)) (где M(n) — время перемножения двух n-значных чисел). Быстрее вряд ли получится.

Также гляньте вот эту статью — там считают факториал по простому модулю.

▲ 13

Самый быстрый факториал - факториал, посчитанный во время компиляции программы. В С++ для этого можно использовать шаблоны. Взял и скопипастил пример сюда:

#include <iostream>

template<int N>
struct Factorial
{
 enum { value = N * Factorial<N-1>::value };
};

template<>
struct Factorial<1>
{
 enum { value = 1 };
};

int main()
{
 // Example use
 const int fact5 = Factorial<5>::value;
 std::cout << fact5;
 return 0;
}

PS: из недостатков конкретно этого вариант - очень быстро можешь вылезть за пределы допустимых значений для встроенных типов. enum же вроде как int работает.

▲ 12

Есть интересные материалы по этому поводу. Во-первых, есть калькулятор факториалов на JavaScript. Он мгновенно вычисляет факториалы чисел до 9.999.999.999

Там же есть материалы по алгоритмам факториалов: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm. Я думаю, тут действительно хорошие алгоритмы ;)

На этом же сайте описывается некий метод, который, как я понял использовался в калькуляторах HP. Некий RPN-калькулятор.

▲ 7

Думаю, что самый быстрый алгоритм вычисления факториала определяется структурой вычислительных средств.
Например, формула Стирлинга допускает представление вида
n! ~ S(n) = a(n/e)n+½, где a= sqrt (2·pi·e).
log2 S(n) = ((n+½)( ln n - 1 ) + ln a)· log2e = L(n), S(n)= exp ({L(n)}·ln2)·2 [L(n)].
При этом двоичная запись факториала оканчивается на B(n)=[n/2]+[n/22]+[n/23]+... нулей (например, B(2k)=[2k/2]+[2k/22]+...+2+1 = 2k-1), и поэтому множитель при ней целый.

В итоге получаем формулу для быстрого факториала как целого числа с бинарным масштабным коэффициентом.
n! = [a·exp(L(n)·ln2)·2L(n)-B(n)+½]·2B(n),
которая при правильно выбранной точности вычислений будет точной.