Python의 int 자료형은 어떻게 범위가 무제한일까?

토즐라·2022년 6월 15일

1D1Q python

1D1Q

목록 보기

2/7

Question

Python의 int 자료형은 어떻게 범위가 무제한일까? 🤔

00. 개요

파이썬 3.10.5 공식 도큐먼트에는 다음과 같은 내용이 있습니다.

Integers have unlimited precision.

어떠한 프로그램이든, 정수 변수를 다룬다면 필연적으로 정수 오버플로우가 발생하기 마련인데, 파이썬은 이를 극복하고 있습니다.

그렇다면 파이썬의 정수 자료형은 어떠한 이유로 무한대의 범위를 가질 수 있는 것인지 차근차근 알아보겠습니다.

01. 정수 오버플로우(Integer Overflow)란 무엇인가

정수 오버플로우(Integer Overflow)란 정수의 값이 증가하면서 허용된 가장 큰 값보다 더 커져서 실제로 저장되는 값은 아주 작은 수이거나 음수가 되어서 프로그램이 예기치 않게 동작되는 오류입니다. 물론, 이는 정수의 값이 허용된 값보다 작아질 때에도 동일하게 발생합니다.

버통 프로그래밍 언어에서 변수란 정보를 저장할 수 있는 공간(메모리)에 이름을 붙인 것입니다. 그리고, 이렇게 변수의 값을 저장하는 공간을 확보하겠다고 말하는 것을 변수를 선언한다고 합니다.

C에서는 변수를 선언할 때, 다음과 같이 변수의 데이터 타입을 앞에 붙여 선언합니다.

int x = 10;
prinf(x)

>> 10

이렇게 변수를 선언하는 이유는 데이터 타입에 따라서 컴퓨터가 할당할 byte 수가 달라지기 때문입니다. 위의 예시에서 integer 타입은 최대 4바이트의 크기를 가지므로, 컴퓨터는 메모리에 공간을 4바이트만큼 할당해 그것에 변수 x 라는 이름을 붙여 관리하는 것이죠.

이렇게 C에서의 모든 데이터 타입은 각자의 자료형에 맞는 저장 가능한 최대/최소 범위가 존재합니다. 그리고 이러한 이유로 C라는 언어는 항상 오버플로우가 발생할 위험이 있고, 이를 잘 관리해야 여러 큰 문제를 막을 수 있습니다.

정수 오버플로우는 다른 프로그래밍 언어인 Java에서도 마찬가지로 발생합니다. 따라서 C나 Java를 이용해 프로그래밍을 하는 개발자에게는 큰 값의 정수형 데이터를 다룰 때 저장 가능한 최대 범위가 큰 자료형(long)을 사용해 한다는 점이 상식이죠.

그렇다면 파이썬의 변수는 어떤 성질을 갖고 있길래 정수형 자료를 다룰 때, 오버플로우가 발생하지 않는 것일까요?

02. 파이썬 변수의 특징

다른 언어와의 차이

C나 Java에서는 변수를 선언할 때, 변수의 데이터 타입을 앞에 붙여 선언해야 했습니다. 하지만, 파이썬은 이 과정이 필요 없습니다. 왜냐하면, 파이썬의 변수는 기본적으로 앞서 살펴보았던 변수와 성질이 매우 다르기 때문입니다. 파이썬에서는 아래와 같이 단순히 변수에 값을 대입하는 것으로 변수를 생성합니다.

x = 10
y = "ten"
print(x)
print(y)

>> 10
>> ten

더 자세히 설명하면, 변수 x 에 10이라는 값을 대입하는 순간 파이썬은 메모리에 10이라는 값을 가지고 있는 객체를 생성하고, x변수가 해당 객체를 가르키게 합니다.
즉, 파이썬에서의 변수란 특정 값을 가지고 잇는 객체를 가리키는 참조자 역할을 하게 됩니다. C에서의 포인터, Java에서의 참조 변수와 비슷한 개념인 것이죠.

위의 예시에서 x는 객체 10을 가리키게 됩니다. 하지만, x가 가리키는 객체는 단순히 10이라는 값만을 가진 게 아니라, 여러 추가 정보들을 함께 가지고 있습니다.

사실 저 간단해 보이는 한 줄에 코드 아래에는 상당히 복잡한 요소들이 존재하는데, 이를 하나 하나 뜯어보겠습니다.

아래에서는 어떤 일이 벌어지고 있는가

파이썬의 모든 것은 객체로 되어 있고, 이 객체들은 C structure로 표현되어 있습니다.
위의 예시에서 x 변수가 참조하는 객체도 다음과 같은 C struct 자료구조로 구성되어 있습니다.

struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

PyObject_VAR_HEAD : 인스턴스마다 길이가 다른 객체를 나타내는 새로운 형을 선언할 때 사용되는 매크로입니다. 이 매크로는 PyVarObject ob_base로 확장됩니다.

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

_PyObject_HEAD_EXTRA : 파이썬 빌드에서 잘 이용하지 않는 매크로입니다. 검색해보아도 어떤 기능을 하는지 잘 나오지 않습니다.

결국, 위의 모든 것들을 합치고, 모든 매크로들을 해독하면, x 라는 변수가 가르키는 객체는 다음과 같은 구조를 갖추고 있다고 할 수 있습니다.

struct _longobject {
    long ob_refcnt;
    PyTypeObject *ob_type;
    size_t ob_size;
    long ob_digit[1];
};

즉, 파이썬에서 변수가 참조하는 객체는 다음과 같은 정보를 담고 있습니다.

ob_refcnt: 객체의 라이프 사이클을 관리하기 위해 자신을 가리키고 있는 변수들의 참조 계수를 저장해놓은 값. 즉, 얼마나 많은 변수들이 자신을 참조하고 있는지를 알려주는 값.
ob_type: 객체 자신이 가지고 있는 타입에 대한 정보를 가지고 있는 또 다른 객체를 가리키는 변수. 10은 정수이므로, 이 곳에는 정수 타입에 대한 정보를 가지고 있는 객체를 가리키고 있는 내부 변수가 있음.
ob_size: ob_digit 의 크기
ob_digit: 숫자 10 자체

Python과 다른 언어의 변수 구성 방식의 차이는 파이썬이 다른 언어보다 필연적으로 느리게 될 수 밖에 없는 이유인데요, 이에 대한 설명은 아래 블로그에 잘 나와 있습니다. 또, 파이썬은 왜 다른 언어들보다 속도가 느린가?라는 주제를 조만간 새로운 포스트에서 소개해드리겠습니다.
why python is slow?

03. 파이썬의 정수 오버플로우

파이썬2 에는 int long 의 두 가지 정수형 데이터 타입이 존재했습니다. 여기서 int는 C에서의 정수형 데이터 타입과 같은 방식의 자료형이었고, long은 지금의 파이썬에서의 정수형 데이터 타입과 같은 방식의 자료형이었습니다. 이 때, 파이썬은 정수 연산을 할 때 처음에는 int 자료형을 이용하다가, 정수 오버플로우가 발생할 것 같으면 자동으로 long을 사용하는 방식을 통해 정수 오버플로의 발생을 막았습니다.

이 때, long 자료형은 무제한의 자릿수를 제공하는 정수형을 의미하는 Arbitrary precision을 지원합니다. 즉, 무한한 크기의 정수형을 표현할 수 있는 것이죠.

파이썬 3으로 넘어오고 PEP 237 로드맵에 따라 long 자료형이 int 자료형을 대체하게 되면서 파이썬의 정수형 데이터 타입은 int 밖에 존재하지 않게 되었습니다. (long 자료형이 이름이 바뀐 것이죠). 따라서, 파이썬3 에서의 int 자료형 역시 arbitrary precision을 지원하고, 이 덕분에 정수 오버플로우를 방지할 수 있습니다.
그렇다면 파이썬 정수 자료형은 어떤 방식으로 arbitrary precision을 보장하는 것일까요?

어떻게 arbitrary precision을 지원하는가

파이썬은 arbitrary precision을 지원하기 위해 10진수로 이루어져있는 정수를 $2^{30}$ 진수로 교체한 후, 각 자릿수의 수들을 배열에 하나하나 저장합니다.
이렇게 하면 32bit 운영체제에서 표현할 수 있는 정수의 최댓값인 $2^{30}-1$ 을 벗어나지 않고, 이보다 더 큰 숫자를 표현할 수 있습니다.

큰 숫자를 표현하는 것에 대한 파이썬 공식 도큐먼트의 코멘트는 다음과 같습니다.

/* Long integer representation.
   The absolute value of a number is equal to
    SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i)
   Negative numbers are represented with ob_size < 0;
   zero is represented by ob_size == 0.
   In a normalized number, ob_digit[abs(ob_size)-1] (the most significant
   digit) is never zero.  Also, in all cases, for all valid i,
    0 <= ob_digit[i] <= MASK.
   The allocation function takes care of allocating extra memory
   so that ob_digit[0] ... ob_digit[abs(ob_size)-1] are actually available.

   CAUTION:  Generic code manipulating subtypes of PyVarObject has to aware that integers abuse  ob_size's sign bit.
*/

다음은 파이썬에서 아주 큰 정수를 표현할 때 사용하는 메모리의 크기가 어떻게 변화하는지에 대한 그래프인데, $2^{30}$ 단위로 계단식으로 올라가는 것을 볼 수 있습니다.

이해를 위해 예시를 살펴보겠습니다.


z = 123456789101112131415

파이썬은 우선 이 정수를 표현하기 위해서 다음과 같이 $2^{30}$ 진수로 교체합니다.

$(437976919 * 2^{30*0} + (87719511*2^{30*1})+107*2^{30*2}$

그리고는 각 숫자를 ob_digit 배열에 저장합니다.

ob_digit	437976919	87719511	107

정수에서 배열로의 변환

그렇다면 파이썬이 정수를 어떻게 배열로 변환하는지에 대해 알아보겠습니다.
부호가 없는 64비트 정수를 파이썬의 정수 표현법으로 변환하는 간단한 예제를 살펴보겠습니다.
다음은 C 정수를 파이썬 정수로 변환하는 간단한 알고리즘입니다.

SHIFT = 30  # 각 자릿수를 나타낼 비트 갯수
MASK = (2 ** SHIFT)
bignum = 18446744073709551615

def split_number(bignum):
    t = abs(bignum)

    num_list = []
    while t != 0:
        # 나머지를 얻는다
        small_int = t % MASK  # 좀 더 효율적인 비트 연산: (t & (MASK-1))
        num_list.append(small_int)

        # 나눗셈의 정수부를 얻는다 (나눗셈 내림)
        t = t // MASK  # 좀 더 효율적인 비트 연산: t >>= SHIFT

    return num_list

def restore_number(num_list):
    bignum = 0
    for i, n in enumerate(num_list):
        bignum += n * (2 ** (SHIFT * i))
    return bignum

num_list = split_number(bignum)
assert bignum == restore_number(num_list)

04. 정리

Python의 int 자료형은 어떻게 범위가 무제한일까? 🤔

💡 파이썬의 정수 자료형은 하나의 객체이다.
💡 파이썬은 이 객체 내부에서 정수를 배열로 변환해 저장한다.
💡 배열 안의 값들은 $2^{30}$ 의 값을 벗어나지 않으므로, 정수 오버플로가 발생하지 않는다.
💡 따라서, 배열을 계속 확장하면 이론상 무한한 크기의 정수를 표현할 수 있다.