Большие числа в Python: типы данных и практические примеры

Расширенные примеры работы с большими числами

Вычисление факториала 1000

import math
print(math.factorial(1000))

402387260077093773543702433923... (сокращено)

Функция math.factorial использует эффективный итеративный алгоритм. Рекурсивное вычисление может быть медленнее и требует установки sys.setrecursionlimit, если глубина рекурсии велика.

Возведение в степень по модулю (модульная арифметика)

# Вычисление 2**1000 mod 1000
result = pow(2, 1000, 1000)
print(result)

376

Функция pow с тремя аргументами значительно эффективнее, чем (2**1000) % 1000, так как не создаёт огромное промежуточное число.

Генерация большого простого числа (512 бит)

import random

def is_prime(n, k=10):
    # тест Миллера-Рабина
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# Генерация 512-битного простого числа
while True:
    candidate = random.getrandbits(512)
    if is_prime(candidate):
        print('Найдено простое число:', candidate)
        break

Найдено простое число: (512-битное число)

Для генерации больших простых чисел используйте модуль random.getrandbits и тест на простоту. В реальных приложениях лучше применять библиотеку sympy.

Точные десятичные вычисления с Decimal (вычисление числа e)

from decimal import Decimal, getcontext
getcontext().prec = 80
e = Decimal(1)
fact = Decimal(1)
for i in range(1, 100):
    fact *= i
    e += Decimal(1) / fact
print(e)

2.7182818284590452353602874713526624977572470936999595749669676277240766303535476

Используя Decimal, можно получать сколь угодно точные значения математических констант.

Сравнение производительности int и gmpy2

import gmpy2, time

# int
start = time.time()
a = 2**1000000
b = 3**200000
c = a * b
print('int time:', time.time() - start)

# gmpy2
start = time.time()
a = gmpy2.mpz(2)**1000000
b = gmpy2.mpz(3)**200000
c = a * b
print('gmpy2 time:', time.time() - start)

int time: 0.435
(gmpy2 time: 0.012)

Для очень больших чисел gmpy2 может быть значительно быстрее (в данном примере в 36 раз). Однако для большинства повседневных задач стандартный int достаточен.

Использование Fraction для точных вероятностей

from fractions import Fraction
import math
n = 100
k = 40
# Точная вероятность выпадения 40 орлов из 100 бросков монеты
prob = Fraction(math.comb(n, k), 2**n)
print('Точная дробь:', prob)
print('Приблизительное значение:', float(prob))

Точная дробь: 245810588801891098700/633825300114114700748351602688
Приблизительное значение: 0.00038779229467880653

Fraction позволяет хранить точное рациональное значение вероятности, что важно в научных расчётах.

Сложение больших чисел, представленных в виде строк

# Демонстрация преобразования строк в int и обратно
a_str = '1234567890' * 100000  # 10^6 цифр
b_str = '9876543210' * 100000
a = int(a_str)
b = int(b_str)
result = a + b
print('Количество цифр в результате:', len(str(result)))

Количество цифр в результате: 1000000

Преобразование длинных строк в int может потребовать много памяти, но Python справляется с числами размером до нескольких миллионов цифр.

Работа с большими числами в комбинаторике: количество сочетаний

from math import comb
n = 10**6
k = 500000
c = comb(n, k)
print('Число сочетаний C(10^6, 500000) имеет', len(str(c)), 'цифр')

(вывод количества цифр, около 300000)

math.comb для больших n, k также использует произвольную точность int.

Быстрое возведение в степень для больших чисел (бинарное возведение)

def fast_pow(base, exp):
    result = 1
    while exp:
        if exp & 1:
            result *= base
        base *= base
        exp >>= 1
    return result

print(len(str(fast_pow(2, 10000))))  # количество цифр 2^10000

3011

Алгоритм бинарного возведения в степень (быстрое возведение) позволяет вычислить огромные степени за O(log exp) умножений.