Точность подсчета факториала через формулу Стирлинга

[Евгений Машеров]

Речь о "количестве нулей" ведётся о (сюрприз, сюрприз!) количестве нулей в конце записи числа. Идея состояла в том, что, зная это количество нулей, округлять приближённое значение так, чтобы нулей было "сколько надо". Но количество нулей растёт медленнее ошибки, так что для больших $N$ это не работает.

[worm2]

Да, я теперь понял, что самый быстрый способ точного вычисления факториала — прямое перемножение, иллюзии отпали.

[Евгений Машеров]

Ну не дайте помереть от любопытства!
Для чего нужно точное значение факториала 25000?

[worm2]

Евгений Машеров писал(а):

Ну не дайте помереть от любопытства!
Для чего нужно точное значение факториала 25000?

Само по себе, возможно, никому не нужно. Так же, как никому не нужно, скажем, доказательство теоремы Ферма.
А вдруг эта задача позволит развиться какому-нибудь полезному методу вычислений?

[Sidle]

Доброго времени суток
Попробуйте вычислить факториал 1000000 в mathematica 8 (x64) вычисляет до последнего знака. Вконце предлагает задать точность, там выбираем "show all"
А 25000! это вообще проще простого

[sergei1961]

Есть более точная формула Сонина

[arseniiv]

Sidle, автор темы в самом начале упомянул, что он реализует алгоритм для своего калькулятора. Matlab или Mathematica туда засовывать он точно не станет.

[Евгений Машеров]

В качестве "в гамаке, но только стоя!" могу предложить держать таблицу простых, найти очевидным образом степени, в которых простые входят в искомый факториал, и использовать что-то наподобие умножения Шёнхаге-Штрассена для нахождения степеней и их перемножения.
Но боюсь, что тупое умножение на все последовательные сомножители будет сильно лучше.

[venco]

Евгений Машеров в сообщении #496142 писал(а):

Но боюсь, что тупое умножение на все последовательные сомножители будет сильно лучше.

Лучше организовать умножение так, чтобы сомножители были одного порядка.

[Евгений Машеров]

Это очень хороший совет для вычислений с плавающей точкой - группировать сомножители так, чтобы порядок их был примерно одинаков, и лучше всего был бы близок к единице. Тогда риск получить по ходу вычислений переполнение или исчезновение порядка минимален.
Но тут топикстартер, полагаю, удовлетворится лишь длинной целой арифметикой. И особого эффекта от переупорядочения не жду.
Впрочем, обсуждаемо.

[erwins]

Если арифметика 64 битная то как вариант использовать такой алгоритм

a=1
b=1
k=2^64 div n -1
for i=1 to n
a*=i
if a>k then b*=a: a=1
next
a*=b

ускорение будет несколько раз

[Евгений Машеров]

Извините, но Вы не вполне уяснили задачу. 64-битная арифметика для данной задачи, как её поставил топикстартер, крайне недостаточна.
Уже $21!=51090942171709440000>18446744073709551616=2^{64}$
А он желает рассчитывать, притом точно, вплоть до $2500!$.

[venco]

Евгений Машеров в сообщении #496159 писал(а):

Это очень хороший совет для вычислений с плавающей точкой - группировать сомножители так, чтобы порядок их был примерно одинаков, и лучше всего был бы близок к единице. Тогда риск получить по ходу вычислений переполнение или исчезновение порядка минимален.
Но тут топикстартер, полагаю, удовлетворится лишь длинной целой арифметикой. И особого эффекта от переупорядочения не жду.
Впрочем, обсуждаемо.

Я как раз и имел в виду целочисленную арифметику.
Если последовательно умножать на маленькие числа, то сложность будет $O(n^2)$, где $n$ - длина результата. Если же умножать близкие по величине числа, то сложность будет $O(n \ln^2 n)$. Естественно, для этого нужно использовать эффективное умножение со сложностью $n\ln n$.

[Евгений Машеров]

Не то, чтобы невозможно... Но, полагаю, на рассматриваемых диапазонах аргументов (до 2500) выигрыш в порядке числа операций перекроется усложнением их.

[venco]

Евгений Машеров в сообщении #496239 писал(а):

Не то, чтобы невозможно... Но, полагаю, на рассматриваемых диапазонах аргументов (до 2500) выигрыш в порядке числа операций перекроется усложнением их.

Даже для 2500 у меня быстрее раза в два (с gmp): 0.44мс вместо 1мс.
Для 25000 уже в 10 раз быстрее.