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

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

Ответ

Типы со знаком (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 #include #include
// Таблица длинная, по этому посчитаем ее во время компиляции (С++14). template 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 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(table.t[x]) : 0; }
int main() { for (unsigned long long i = 0; i != 70; ++i) { std::cout << i << ": " << fac(i) << '
'; } }