Борис Рюмшин писал(а):
Mathematica похоже имеет оптимизированное монолитное вычислительное ядро, которое она ставит под конкретный процессор.
Справедливости ради, объясню почему Mathematica чрезвычайно быстро вычисляет факториалы. Тут дело не только в очень хорошей реализации ее библиотек, тут выше берите - дело в алгоритме. Как известно, существует метод быстрого умножения длинных чисел, который имеет сложность O(N*Log(N)) вместо O(N*N), где N-число разрядов в числе. Так, вот оказывается факториалы тоже можно вычислять "достаточно быстро".
Пусть: N - количество чисел которые нужно перемножить.
1) Сначала делаем попарные умножения 1-разрядных чисел (под разрядом здесь условно понимаю машинное слово), т.е. N/2 умножений сложность каждого равна 1.
2) Потом полученные 2-разрядные числа опять умножаем попарно, получая 4-разрядные, выполнив при этом N/4 двухразрядных умножений.
3) Повторяем пока всё не перемножилось.
Сложность(N) = N/2*S(1) + N/4*S(2) + N/8*S(4) + N/16*S(8) +...+ 1*S(N/2) = Sum[(N*S[2^(p-1)])/2^p, {p, 1, Log2[2*N]-1}]
S(k) - сложность умножения k-разрядных чисел. Если использовать обычное умножение в столбик, то S(k) = k^2 и ускорения не будет (а будет O(N^2)). Но можно использовать быстрое умножение. S(k) = k*Log(k), тогда (если я ничего тут не напутал), получаем сложность
O(N*Log2[N]*Log2[N/2]) вместо O(N^2).