Для большой целочисленной арифметики цель состоит в том, чтобы одновременно сократить количество операций, которые вы должны выполнять на своих больших целых числах, а также максимально эффективно выполнять основные операции (суммы, подразделения, продукты и т. Д.).
В случае факториалов имеется много доступных алгоритмов, которые могут уменьшить количество умножений, которые нужно сделать (например, рекурсивный подход). Кроме того, умножение выполняется с использованием лучших алгоритмов, которые в порядке возрастания размера, как правило:
основного умножения -> Карацуб -> Том-Кук -> алгоритм Шёнхаг-Strassen
Точного размер где один алгоритм становится лучше другого, не является хорошо известным и, как правило, чувствителен к машинам.
Это, как говорится, все имеет свои пределы. Вот результат времени (10^i)! рассчитанный в Mathematica для i от одного до восьми.
Table[Timing[(10^i)!][[1]], {i, 1, 8}]
{0.000011, 0.00002, 0.000028, 0.000911, 0.015209, 0.20903, 3.99917, 58.9894}
обновление: Как я и предполагал, Вольфрам использует GMP для некоторых из его больших целых операций.
http://library.wolfram.com/infocenter/Conferences/7518/Macalester_talk.txt
Случай для [Формула Стирлинга] (https://en.wikipedia.org/wiki/Stirling%27s_approximation)? –
только цикл от '1' до' 10000' с 'BigInteger' вычисляет факториал 70 миллисекунд; однако этот наивный подход не работает для '100000! '(требуется около 10 секунд) –
Я не знаю, какой алгоритм они используют, но вы можете использовать алгоритм, основанный на простых числах: 10! = 3628800 = 2^(10/2 + 10/4 + 10/8) * 3^(10/3 + 10/9) * 5^(10/5) * 7^(10/7) = 2^8 * 3^4 * 5^2 * 7 – maraca