python: вычисление чрезвычайно большого числа

Question

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

Это может быть как

factorial(n x 10,000,0000)*factorial(n x 10,000,0000) 

, так что я думаю, что на обычном 32-битном компьютере, он перетекает ...

Есть обходной путь?

Answer 1

Это не проблема под Python.

>>> 2**100 
1267650600228229401496703205376L 

Python автоматически преобразует простые целые числа в длинные целые числа и не переполняется.

http://docs.python.org/2/library/stdtypes.html#numeric-types-int-float-long-complex

Answer 2

Насколько я знаю, целые числа в Python (3) могут быть сколь угодно большими.

Answer 3

Вы хотите использовать bignums. Python имеет их изначально.

Answer 4

Приближение Стирлинга к n! (n/e)^n * sqrt (2 * pi * n). Это имеет приблизительно n * log (n/e) цифры.

Вы вычисляете (n * 1e8)!^2. Это будет иметь примерно 2 * n * 1e8 * log (n * 1e8/e) цифры, равные 2e8 * n * (17 + log (n)). Предполагая, что n относительно мало и log (n) пренебрежимо мало, это 3.4e9 * n цифр.

Вы можете хранить около 2,4 цифр в байте, поэтому ваш результат будет использовать (1.4 * n) гигабайт ОЗУ, предполагая, что Python может эффективно хранить номер.

32-разрядная вычислительная машина может занимать не более 4 ГБ ОЗУ, поэтому теоретически возможно вычислять n = 1 или 2, но для n = 3 машина не может даже удерживать результат в ОЗУ. По мере того, как вы вычисляете свой результат, Python должен будет хранить в RAM несколько бинарных (например, временных переменных), поэтому фактическое использование памяти будет выше, чем предлагаемые выше вычисления.

На практике я бы ожидал, что на 64-битной машине с большим количеством оперативной памяти вы никогда не сможете получить результат для этого расчета на Python - машина будет тратить все свое время на сбор мусора.