О вычислении факториала: часть 2

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

Статью (пока что) не читал. Результат, который там приводится, таков:
временная сложность составляет , где — временная сложность перемножения двух чисел длины .
(Для сравнения: в случае разбиения произведения на два произведения примерно равной длины сложность отличается тем, что вместо log(log(n)) в формуле стоит просто log(n). В случае же тупого перемножения последовательных чисел сложность равна O(n² log n).)

Таким образом, в случае использования метода Шёнхаге-Штрассена сложность —

В случае же использования метода Карацубы, для которого , сложность, соответственно, —

Даже проверил из любопытства: (кривая - график f(N) = 1.532e-10 * (N log N)^log₂3 * log log N)

Release of ruby-numtheory 0.0.3

First, I'd like to say a few words about the history of the project.
Right after I switched to Ruby with respect to solving ProjectEuler.net problems, I realized that there's actually no number-theoretical Ruby libraries at all. Of course, I could just turn to some more advanced tools like PARI-GP or switch to, say, Python which has nzmath library. But: 1) I love Ruby. 2) Number-theoretical algorithms are themselves useful to know and understand for I'm sorta mathematician ;-)
Thus I decided to write my own library. And now, I suppose, it even might be useful for somebody else.

Well, what has been implemented so far?

• Eratosphenes sieve
• Factorization by trial division.
• Common multiplicative functions: moebius, sigma, phi, pi.
• Jacobi symbol
• Powermod (works with negative powers also whenever the inverse exists)
• N-th fibonacci number
• Fast factorial computation by PrimeSwing algorithm
• Multiplicative order
• Miller-Rabin primality test

The gem is at rubygems.org/gems/ruby-numtheory; Thanks to the existence of rake-compiler, precompiled version for Windows is also available. 

The features to be implemented in the near future are some more primality tests (I hope I will eventually understand AKS), and roots modulo n (at least Tonelli-Shanks algorithm). Maybe, something else.