[PYTHON] 파이썬 무한 정수와 나눗셈: 큰 수 연산은 얼마나 느릴까?

PYTHON 무한정수와 나눗셈

1. 개요

C나 Java 같은 언어에는 int(4바이트), long(8바이트)처럼 정수를 담을 수 있는 크기에 제한이 있습니다. 계산 결과가 이 범위를 넘어가면 '오버플로우(Overflow)'가 발생해 쓰레기 값이 되곤 합니다.

하지만 파이썬은 다릅니다. 메모리가 허용하는 한 무한히 큰 정수를 다룰 수 있습니다.
그렇다면 궁금해집니다. 이렇게 큰 수를 나누거나 곱할 때 성능은 괜찮을까요?

---

2. 간단한 설명

파이썬의 정수(int)는 임의 정밀도(Arbitrary-Precision) 방식을 사용합니다. 숫자가 작을 때는 CPU의 레지스터를 이용해 빠르게 계산하지만, 숫자가 커지면 자동으로 여러 개의 메모리 블록을 연결하여 숫자를 표현합니다. (마치 기차 객차를 연결하듯이)

이 덕분에 개발자는 오버플로우 걱정을 안 해도 되지만, 그 대가로 숫자가 커질수록 연산 속도가 느려지는 특성이 있습니다. 특히 나눗셈이나 거듭제곱 연산은 자릿수에 비례해 급격히 느려집니다.

---

3. 사용 사례

사례: 암호학에서의 큰 수 연산 (RSA 알고리즘)

RSA 암호화 알고리즘은 수백 자리의 소수를 곱하고 나누는 연산을 기반으로 합니다.

[비교] 작은 수 vs 큰 수 연산 시간

import time

# 일반적인 크기의 정수
small_a = 10**10
small_b = 10**5

# 엄청나게 큰 정수 (1000자리 이상)
big_a = 10**1000
big_b = 10**500

# 작은 수 나눗셈
start = time.time()
small_a // small_b
print(f"작은 수 소요시간: {time.time() - start:.10f}")

# 큰 수 나눗셈
start = time.time()
big_a // big_b
print(f"큰 수 소요시간: {time.time() - start:.10f}")

실제로 돌려보면 큰 수의 나눗셈이 미세하게(혹은 자릿수가 수십만 개가 되면 뚜렷하게) 더 오래 걸리는 것을 확인할 수 있습니다.

즉, 자릿수가 2배 늘어나면 계산 시간은 4배로 늘어난다는 뜻입니다. 이를 간단한 데이터로 보면 다음과 같습니다. (예시값)

자릿수 (N)	계산 시간 (초)	증가율
1만 자리	0.001s	-
2만 자리	0.004s	4배
4만 자리	0.016s	16배

단순히 숫자가 커지는 것보다 훨씬 더 가파르게 성능이 떨어지므로, 무작정 큰 수를 다룰 때는 주의가 필요합니다.

이런 성능 차이가 나는 이유는 파이썬은 내부적으로 큰 수 나눗셈을 위해 O(N^2)에 가까운 복잡도를 가진 알고리즘을 사용하기 때문입니다.

---

파이썬은 왜 O(N^2)일까? (Knuth's Algorithm D)

파이썬이 사용하는 나눗셈 알고리즘은 손으로 풀때 사용하는 나눗셈 규칙을 컴퓨터가 처리하기 좋게 구현한 Knuth's Algorithm D입니다.

1. 원리: 우리가 12345 ÷ 12를 세로로 풀 때처럼, 가장 높은 자릿수부터 하나씩 맞추고 빼는 과정을 반복합니다.
2. 연산량: '나눠지는 수의 길이(N)'만큼 반복하면서, 매번 '나누는 수의 길이(M)'만큼 곱셈과 뺄셈을 해야 합니다.
3. 결과: 두 수의 길이가 비슷하다면(N ≈ M), 결국 N번 × N번 = N²번의 연산을 하게 됩니다.

파이썬은 아주 큰 수를 2의 30승(약 10억) 진법의 배열로 쪼개서 관리하는데, 이 배열들을 순회하며 세로 나눗셈을 수행하기 때문에 숫자가 커질수록 연산량이 제곱으로 늘어나는 것입니다.

---

하지만 개발 생산성 측면에서는 별도의 라이브러리(BigInt) 없이 기본 연산자로 이를 처리한다는 점이 엄청난 장점입니다.

---

4. 맺음말

파이썬의 '무한 정수' 기능은 강력한 무기입니다. 팩토리얼 계산이나 암호화 로직을 짤 때 오버플로우를 신경 쓰지 않아도 된다는 건 축복과 같습니다.다만, 수만 자리 이상의 숫자를 다루는 고성능 연산이 필요하다면 gmpy2 같은 C 기반의 고속 연산 라이브러리 도입하는게 도움이 될 수 있습니다.