Obsługa dużych liczb w kodzie

Question

Pracuję nad problemem programowania, w którym muszę obsłużyć liczbę obejmującą 100000 cyfr. Czy Python może obsługiwać takie liczby?

Answer 1

Pewnie, że można:

>>> s = 10 ** 100000 

Answer 2

Wydaje się działać prawidłowo:

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

Według http://docs.python.org/library/stdtypes.html, „Długie liczby całkowite mają nieograniczoną precyzję”, co prawdopodobnie oznacza, że ​​ich wielkość nie jest ograniczona.

Answer 3

Tak; Python 2.x ma dwa typy liczb całkowitych: int o ograniczonym rozmiarze i długi z nieograniczony rozmiar. Jednak w razie potrzeby wszystkie obliczenia zostaną automatycznie przeliczone na długie. Obsługa dużych liczb działa dobrze, ale jedną z wolniejszych rzeczy będzie próba wydrukowania 100000 cyfr na wyjściu, lub nawet próba utworzenia z niego ciągu.

Jeśli potrzebna jest również precyzyjna dziesiętna precyzja w ustalonym punkcie stałym, dostępny jest moduł dziesiętny.

Answer 4

Jak wskazano w innych odpowiedziach, Python obsługuje liczby całkowite ograniczone tylko ilością dostępnej pamięci. Jeśli chcesz jeszcze szybsze wsparcie dla nich, spróbuj gmpy (jako autor gmpy i bieżącej współpracy opiekuna jestem oczywiście trochę stronniczy tutaj ;-):

$ 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 

Zazwyczaj arytmetyka nie jest wąskim gardłem dla pracy z takie liczby (chociaż gmpy bezpośrednie wsparcie dla niektórych funkcji kombinatorycznych i liczbowo-teoretycznych może pomóc, jeśli to właśnie robisz z takimi liczbami). Przechodząc do ciągów liczb dziesiętnych jest prawdopodobnie wspólna operacja, która poczuje najwolniej ...:

$ 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 

Jak widać, nawet w gmpy stringification ogromnych liczb może być setki razy wolniej niż prostego dodawania (niestety, jest to nierozerwalnie skomplikowana operacja!); ale w natywnym kodzie Pythona stosunek czasów może iść do uszeregowania, który jest kilkadziesiąt tysięcy razy wolniejszy niż zwykły dodatek, więc naprawdę chcesz na to uważać, zwłaszcza jeśli zdecydujesz się nie pobierać i instalować gmpy (na przykład z powodu nie możesz: np. gmpy nie jest obecnie obsługiwany w Google App Engine).

Wreszcie przypadek pośredni:

$ 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 

Jak widać, mnożąc dwie wielkie liczby w natywnym kodzie Pythona może być prawie 1000 razy wolniej niż proste dodanie, podczas gdy z gmpy spowolnienie jest mniejsza niż 100 razy (i nie jest tak źle, nawet jeśli jest tylko jeden, jeśli liczby są już w formacie własnym gmpy, więc istnieje dodatkowy koszt konwersji drugiego).

Answer 5

Jak już wspomniano, Python może obsługiwać liczby tak duże, jak pozwala na to Twoja pamięć. Chciałbym tylko dodać, że wraz ze wzrostem liczby wzrasta koszt wszystkich operacji na nich. Nie chodzi tylko o drukowanie/konwertowanie na ciąg (choć jest to najwolniejszy), ale dodanie dwóch dużych liczb (większych niż to, co twój sprzęt może natywnie obsługiwać) nie jest już O (1).

Po prostu wspomniałem o tym, aby podkreślić, że chociaż Python zgrabnie ukrywa szczegóły pracy z dużymi liczbami, nadal należy pamiętać, że te operacje z dużymi liczbami nie zawsze są takie same jak w zwykłych intach.