Python 큰 정수 사칙연산: int 한계와 문자열 덧셈·곱셈 구현

컴퓨터에서 “무한히 큰 수”를 저장할 수는 없다. Python의 int는 fixed-width 32·64 bit integer와 달리 필요한 만큼 자릿수를 늘리는 arbitrary-precision integer지만, 실제 한계는 memory와 실행 시간이다.

두 큰 정수를 계산할 때 먼저 판단할 것은 직접 algorithm을 구현할지 여부다. application code라면 검증된 Python int를 쓰는 것이 기본이고, 문자열 연산 구현은 자리 올림과 시간 복잡도를 학습하거나 입력 제약이 특별할 때 의미가 있다.

Python int로 계산하기

Python integer끼리 +, -, *, //, %를 사용하면 결과도 arbitrary precision integer다.

left = 123456789012345678901234567890
right = 987654321098765432109876543210

print(left + right)
print(right - left)
print(left * right)

quotient, remainder = divmod(right, left)
print(quotient, remainder)

integer 나눗셈에서는 /와 //를 구분한다.

• /: float 결과를 만들기 때문에 아주 큰 정수에서는 precision을 잃거나 변환 범위를 넘을 수 있다.
• //: floor division으로 integer quotient를 만든다.
• divmod(a, b): (a // b, a % b)를 한 번에 얻는다.
• 음수의 //는 0 방향 절삭이 아니라 minus infinity 방향으로 내린다.

정확한 decimal fraction을 다뤄야 한다면 binary float 대신 requirement에 맞는 decimal.Decimal의 precision과 rounding policy를 검토한다. 큰 정수 계산과 돈의 소수점 계산은 같은 문제로 묶지 않는다.

문자열 덧셈을 직접 구현해 보기

아래 함수는 부호 없는 10진수 문자열만 받는다. 오른쪽 끝에서 왼쪽으로 이동하며 각 자리의 합과 carry를 계산한다.

def normalize_decimal(value: str) -> str:
    if not value or not value.isascii() or not value.isdigit():
        raise ValueError("non-negative ASCII decimal digits required")
    return value.lstrip("0") or "0"


def add_decimal(left: str, right: str) -> str:
    a = normalize_decimal(left)
    b = normalize_decimal(right)
    i = len(a) - 1
    j = len(b) - 1
    carry = 0
    out: list[str] = []

    while i >= 0 or j >= 0 or carry:
        x = ord(a[i]) - ord("0") if i >= 0 else 0
        y = ord(b[j]) - ord("0") if j >= 0 else 0
        carry, digit = divmod(x + y + carry, 10)
        out.append(str(digit))
        i -= 1
        j -= 1

    return "".join(reversed(out))


assert add_decimal("0009", "91") == "100"
assert add_decimal("99999999999999999999", "1") == "100000000000000000000"

두 입력의 최대 길이를 n이라 하면 모든 자리를 한 번씩 보므로 time complexity는 O(n), 결과를 저장하는 space도 O(n)이다.

Schoolbook Multiplication 구현

각 자리 쌍을 곱해 위치별 배열에 누적한다. 입력 길이가 n, m이면 기본 구현의 time complexity는 O(nm)다.

def multiply_decimal(left: str, right: str) -> str:
    a = normalize_decimal(left)
    b = normalize_decimal(right)
    if a == "0" or b == "0":
        return "0"

    out = [0] * (len(a) + len(b))

    for i in range(len(a) - 1, -1, -1):
        x = ord(a[i]) - ord("0")
        for j in range(len(b) - 1, -1, -1):
            y = ord(b[j]) - ord("0")
            total = x * y + out[i + j + 1]
            out[i + j + 1] = total % 10
            out[i + j] += total // 10

    return "".join(map(str, out)).lstrip("0") or "0"


assert multiply_decimal("00012", "34") == "408"
assert multiply_decimal("123456789", "987654321") == str(123456789 * 987654321)

이 구현은 algorithm 학습용이다. 부호, input length limit, resource budget, cancellation, constant-time requirement를 다루지 않는다. production에서 Python int보다 낫다고 가정하면 안 된다.

Karatsuba와 FFT는 언제 보나

schoolbook multiplication은 모든 자리 쌍을 곱한다. Karatsuba는 큰 수를 절반씩 나눠 multiplication 횟수를 네 번에서 세 번으로 줄여 대략 O(n^log₂3)의 성장을 보인다. 더 큰 수에는 FFT·NTT 계열 algorithm이 사용될 수 있다.

그러나 작은 input에서는 recursion과 memory allocation overhead 때문에 단순 algorithm이 더 빠를 수 있다. CPython이 내부에서 어느 threshold와 algorithm을 쓰는지는 implementation detail이며 application contract가 아니다. 먼저 실제 input distribution을 benchmark한다.

4,300자리 부근에서 ValueError가 날 수 있는 이유

Python 3.11부터 CPython은 decimal string과 int 사이의 비선형 변환 비용을 악용한 denial-of-service를 줄이기 위해 기본 digit limit을 둔다. build의 current setting은 다음처럼 확인한다.

import sys

print(sys.get_int_max_str_digits())
print(sys.int_info.default_max_str_digits)

기본값은 일반적으로 4,300 digits지만 runtime·build 설정에 따라 확인해야 한다. 이 limit은 arithmetic 자체의 최대 integer 크기가 아니라 decimal conversion 경계다. untrusted input을 처리하려고 limit을 무조건 0으로 끄지 않는다.

• protocol에서 허용할 최대 digits를 먼저 정한다.
• parsing 전에 input length와 character set을 검증한다.
• timeout·memory budget을 둔다.
• 정말 더 큰 trusted data가 필요하면 process 전체 설정 변경의 영향을 test한다.

큰 정수에서 자주 하는 실수

• int는 무한하다고 생각해 resource limit을 두지 않는다.
• exact quotient가 필요한데 /로 float를 만든다.
• decimal fraction까지 float로 처리하고 금액 오차를 만든다.
• cryptography에서 직접 만든 multiplication을 사용한다.
• 매우 긴 입력을 검증 없이 int(text)에 넣는다.
• a ** b % modulus를 계산해 거대한 중간 값을 만든다. modular exponentiation에는 pow(a, b, modulus)를 쓴다.

algorithm 문제의 input·output과 complexity를 읽는 기준은 문제 해결형 글 모음에서 함께 볼 수 있다.

자주 묻는 질문

Python int에는 overflow가 없나

fixed-width overflow 대신 필요한 memory가 늘어난다. resource가 부족하면 계산을 끝낼 수 없고, 외부 library·database·serialization format으로 넘길 때 별도 범위 제한이 생길 수 있다.

큰 정수 나눗셈은 /를 쓰면 되나

정수 quotient와 remainder가 필요하면 //, %, divmod()를 사용한다. /는 float 결과라 정확한 arbitrary-precision integer division 용도가 아니다.

문자열 구현이 Python int보다 빠른가

대부분의 일반 application에서는 아니다. Python built-in은 최적화된 arbitrary-precision 구현을 사용한다. 문자열 구현은 학습과 특수한 input contract에 적합하다.

참고 자료

• Python Built-in Types: Numeric Types
• Python Integer String Conversion Length Limitation
• Python decimal
• Python pow