Как вычисляется факториал

Как найти n! ? Казалось бы, берём и перемножаем все числа от 1 до n, чего тут думать-то? Однако не так всё просто.

Итак, зададимся целью вычислить 1000000! (безо всяких приближений) за вменяемое время (порядка 1-2 минут). Предполагается, что работа с длинными числами встроена в язык, причём их умножение реализовано более-менее адекватно (ну хотя бы алгоритмом Карацубы). Далее в посте будет использоваться Ruby, в котором именно Карацуба и реализован.

Попытки посчитать "по определению" ни к чему толковому не приводят:

def factorial(n)
    r = 1
    for i in 1..n do
        r *= i
    end 
    return r
end 

user     system      total        real
25000!      3.320000   0.060000   3.380000 (  3.393819)
50000!     14.210000   0.190000  14.400000 ( 14.458802)
100000!    58.970000   0.870000  59.840000 ( 60.115690)

Как видим, время ~ n², хотя число множителей ~ n. Невесело как-то. Эдак 1000000! нам часа два ждать придётся...

А дело в том, что почти все операции — это умножение длинного числа на короткое, в то время как алгоритмы перемножения длинных чисел ведут себя лучше всего при перемножении чисел равной длины. Доказывать это теоретически мне лень, проще это на практике показать.

Чтобы сделать длины перемножаемых чисел примерно равными, поступим следующим образом. Заметим, что


Здесь оба сомножителя, как нетрудно понять, примерно равной длины. С каждым из них можно проделать тот же трюк. Получаем следующую рекурсивную реализацию:

def g(n, step)
    return n if n <= step
    return g(n, step*2) * g(n-step, step*2)
end

def factorial(n)
    g(n, 1)
end

Ничего сложного в этом нет, а время выполнения улучшилось на порядок:

user     system      total        real
25000!      0.330000   0.000000   0.330000 (  0.365312)
50000!      1.030000   0.030000   1.060000 (  1.098816)
100000!     3.560000   0.030000   3.590000 (  3.666322)

И в принципе, если лень заморачиваться, это вполне неплохой алгоритм. Тот самый 1000000! вычисляется за 4 с небольшим минуты.
Этот алгоритм можно ещё немножко ускорить, если заметить, что
, т.е. g(2n, 2) = 2ⁿ*g(n, 1). Вместо уймы умножений на 2 лучше накапливать степень двойки в отдельной переменной, а в конце сделать сдвиг влево на это значение:

class Factorial
    @shift = 0
    def g(n, step)
        return n if n <= step
        if n.even? and step == 2 then
            @shift += n/2
            return g(n/2, 1)
        end
        return g(n, step*2) * g(n-step, step*2)
    end
    def fac(n)
        @shift = 0
        v = g(n, 1)
        return v << @shift
    end
end

Однако можно ускорить вычисление факториала ещё раза эдак в два! Но для этого нужно применять куда более хитрые методы.
(На этом вступление заканчивается ^____^)

О несобственных интегралах

Вообще говоря, на английском их называют improper integrals. "Proper" имеет два основных значения: "надлежащий/правильный" (как в "do your job properly") и "собственный" (например, "proper noun" — "имя собственное").

Так что переводчик, похоже, тем ещё кретином был. Это ж надо было совсем нихрена не шарить в математике, чтобы выбрать такой перевод =\
(Если кому-то такие "аргументы" кажутся неубедительными, можете узнать из Википедии, что, например, на нидерландском понятие звучит как "Oneigenlijke", на польском — "niewłaściwa", что google translate переводит как "ненадлежащий" и "неуместный" соответственно. Невменяемо термин переводится, видимо, только в России и Украине.)

Ну да ладно, хотя бы дроби в нашем языке "правильные" и "неправильные", и то хорошо =)