Самый быстрый факториал
1,00
р.
Столкнулся с интересной задачкой. Как посчитать факториал числа самым быстрым способом? Быстрее чем за 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] } <br>Типы без знака (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) << '<br>' } }
Ответ
Типы со знаком (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] } <br>Типы без знака (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) << '<br>' } }
