Обработка больших чисел в коде

Question

Я работаю над проблемой программирования, когда мне нужно обрабатывать число, состоящее из 100000 цифр. Может ли python обрабатывать такие числа?

Answer 1

Конечно, это может:

>>> s = 10 ** 100000 

Answer 2

Это, кажется, работает нормально:

>>> x = 10**100000 
>>> x 
10000000000000000000000000000000000000000000000000000000000000000000000000000000 
[snip] 
00000000L 

Согласно http://docs.python.org/library/stdtypes.html, «Длинные целые имеют неограниченную точность», которая, вероятно, означает, что их размер не ограничен.

Answer 3

Да; Python 2.x имеет два типа целых чисел, int и longнеограниченный размер. Однако все вычисления автоматически преобразуются в длину, если необходимо. Обработка больших чисел отлично работает, но одна из самых медленных вещей будет, если вы попытаетесь напечатать 100000 цифр для вывода или даже попытаться создать из нее строку.

Если вам нужна произвольная десятичная точность с фиксированной точкой, есть десятичный модуль.

Answer 4

Как указано в других ответах, Python поддерживает целочисленные числа, ограниченные только объемом доступной памяти. Если вы хотите еще быстрее их поддержки, попробуйте gmpy (как автор gmpy и текущее сотрудничество сопровождающим Я конечно немного предвзято здесь ;-):

$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'x+1' 
10000 loops, best of 3: 114 usec per loop 
$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y+1' 
10000 loops, best of 3: 65.4 usec per loop 

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

$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'str(x)' 
10 loops, best of 3: 3.11 sec per loop 
$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'str(y)' 
10 loops, best of 3: 27.3 msec per loop 

Как вы видите, даже в gmpy stringification огромных чисел может быть в сотни раз медленнее, чем простое сложение (увы, это сложная операция!); но в исходном коде Python отношение времени может идти до строкой: десятки тысяч раз медленнее, чем простое дополнение, поэтому вы действительно хотите следить за этим, особенно если вы решили не загружать и устанавливать gmpy (например, потому что вы не можете: например, gmpy в настоящее время не поддерживается в Google App Engine).

Наконец, промежуточный случай:

$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'x*x' 
10 loops, best of 3: 90 msec per loop 
$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y*y' 
100 loops, best of 3: 5.63 msec per loop 
$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y*x' 
100 loops, best of 3: 8.4 msec per loop 

Как вы видите, умножив два огромных числа в машинном коде Python может быть почти в 1000 раз медленнее, чем простое сложение, а с gmpy замедление менее чем в 100 раз (и это не так уж плохо, даже если только один, если числа уже находятся в собственном формате gmpy, так что есть накладные расходы на преобразование другого).

Answer 5

Как уже указывалось, Python может обрабатывать номера размером с памятью. Я хотел бы добавить, что по мере увеличения числа стоимость всех операций на них возрастает. Это не просто для печати/преобразования в строку (хотя это и есть самая медленная), добавляя два больших числа (больше того, что может обрабатывать ваше оборудование) больше не O (1).

Я просто упомянул об этом, отметив, что хотя Python аккуратно скрывает детали работы с большими числами, вам все равно нужно иметь в виду, что эти операции с большими числами не всегда похожи на операции с обычными ints.