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

[PAV]

А нет разве аналога формулы Стирлинга с точной оценкой сверху?

[faruk]

Помимо аппроксимации Стирлинга есть еще аппроксимация Ланцоша для гамма-функции: http://en.wikipedia.org/wiki/Lanczos_approximation

[ТНК]

Brukvalub писал(а):

Обсуждение убедило меня, что применение ф-лы Стирлинга для решения этой задачи - наилучший выход.

Был бы наилучшим еслиб числа представлялись в стандартных типах данных , а у меня число представляется ввиде массива,а деление такого массива на вещественное число задача не простая, но всеравно спасибо за помощь!

[незваный гость]

Я понял: Вас не затрудняет выделить $946795322485$ байт памяти, организовать умножение, и выполнить $9 \times 10^{10}$ операций над такого объёма памятью. Но затрудняет подсчитать сумму логарифмов. По опыту, могу сказать: вторая задача намного проще. Хотя... $9 \times 10^{10}$ логарифмов скорее всего займут пару-тройку часов (да ещё и надо правильно организовать вычисления, чтобы избежать потери точности).

А вот где Вы возьмёте терабайт оперативной памяти, Вам виднее.

Можно немного сжульничать: 90000000000! будет кончаться на 22499997696 нулей, и их можно не считать и не хранить. Сомневаюсь, однако, что это сильно Вам поможет. Ну, пару-тройку процентов.

[Профессор Снэйп]

незваный гость писал(а):

:evil:
Я понял: Вас не затрудняет выделить $946795322485$ байт памяти, организовать умножение, и выполнить $9 \times 10^{10}$ операций над такого объёма памятью. Но затрудняет подсчитать сумму логарифмов. По опыту, могу сказать: вторая задача намного проще. Хотя... $9 \times 10^{10}$ логарифмов скорее всего займут пару-тройку часов (да ещё и надо правильно организовать вычисления, чтобы избежать потери точности).

А вот где Вы возьмёте терабайт оперативной памяти, Вам виднее.

Можно немного сжульничать: 90000000000! будет кончаться на 22499997696 нулей, и их можно не считать и не хранить. Сомневаюсь, однако, что это сильно Вам поможет. Ну, пару-тройку процентов.

Мне почему-то кажется, что не пару-тройку часов, а значительно быстрее.

И тогда уж, чтобы память не терять, лучше не в десятичной, а в 256-ричной системе всё перемножать. Один разряд --- один байт, всё хорошо ужмётся. И в скорости выигрыш будет. А потом полученный результат уже можно и в десятичную систему преобразовать.

[Brukvalub]

Дальнейшее обсуждение убедило меня, что применение ф-лы Стирлинга для решения этой задачи - не самый наилучший выход.

[Gafield]

ТНК писал(а):

Был бы наилучшим еслиб числа представлялись в стандартных типах данных , а у меня число представляется ввиде массива,а деление такого массива на вещественное число задача не простая, но всеравно спасибо за помощь!

А в чем проблема перевести в стандатрный тип и поделить?

[незваный гость]

Профессор Снэйп писал(а):

И тогда уж, чтобы память не терять, лучше не в десятичной, а в 256-ричной системе всё перемножать. ‹…› И в скорости выигрыш будет. А потом полученный результат уже можно и в десятичную систему преобразовать.

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

Правда, есть другой трюк: считать в 100-ричной (или иной системе с основанием $10^k$).

Gafield писал(а):

А в чем проблема перевести в стандатрный тип и поделить?

Число больно велико.

[Gafield]

Для вычислений числа цифр в 9000000000! вычисления проводятся с числом 90000000000, разве оно большое для стандартных типов данных?

[незваный гость]

Gafield писал(а):

Для вычислений числа цифр в 9000000000! вычисления проводятся с числом 90000000000, разве оно большое для стандартных типов данных?

Целых — да (90000000000). Но речь идёт о представлении 9000000000! в виде массива. А вот это уж точно велико.

[faruk]

[незваный гость]

Я думаю, требуются ответы чуточку поточнее. Особенно в клетке D2. С 946795322484 цифрами после запятой.

[Gafield]

А зачем целые? Надо же вычислять логарифм и т.д. Двойной точности вполне хватит . В числе всего то 11 знаков.

[Someone]

Логарифм гамма-функции как-то считается. Mathematica 5.1 выдаёт

Floor[LogGamma[9000000001]/Log[10]]+1

$85679532254$

за очень малую долю секунды.

[незваный гость]

Someone писал(а):

Логарифм гамма-функции как-то считается.

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

Оценка (2-3 часа) давалась на суммирование логарифмов в лоб.

Я, кстати, не исключаю, что подсчёт факториала такого большого числа не будет эффективней через $\ln \Gamma$ и ряды. Тут уже надо либо проверять, либо очень аккуратно считать операции.

Someone писал(а):

$85679532254$

Разное количество ноликов между 9 и 1.