[CPython] 2. 덧셈의 시간복잡도는 O(logN)입니다.

Python에서 '수'를 나타내는 자료형은 int형과 float형이다.

이러한 값들은 어떠한 데이터로 C++수준에서 작동할까?

 

먼저 python에서 1000**1000을 계산해 보자. 놀랍게도 잘 출력된다.

C++에서는 이러한 값을 저장할 수 있는 기본 타입을 제공하지 않는다.

Unsigned long long 은 0~2^64-1의 값을 가지는데, log(2^64-1)는 약 64log2이고, log(1000^1000)=3000이다.

그렇다면 python에서는 어떤 타입으로 정수형을 저장하는 것 일까?

 

간단하게는 단순히 각 정수에 할당된 공간을 늘리는 방법이 있다.

typedef unsinged long long ull;
struct BigInt {
    ull a0;
    ull a1;
    (...)
    ull a?;
}

 

그렇다면  이번에는 1000**100000를 계산해 보자

>>> 1000**10000
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

sys.set_int_max_str_digits를 호출해서 출력 자릿수의 한계를 늘리라고 한다.

실제로 sys.set_int_max_str_digits(1000000000)를 호출하면 잘 출력됨을 알 수 있다.

 

어떻게 함수의 호출 만으로 최대 값이 늘어난 것일까?

CPython에서 정의를 찾아보면 다음과 같다. [링크]

// Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
typedef struct _PyLongValue {
    uintptr_t lv_tag; /* Number of digits, sign and flags */
    digit ob_digit[1];
} _PyLongValue;

struct _longobject {
    PyObject_HEAD
    _PyLongValue long_value;
};

놀랍게도 CPython에서는 array로 정수를 저장한다!

이 덕분에 python에서는 자릿수에 대한 제약이 없다.

 

실제로 덧셈의 정의를 살펴보면 [링크]

// Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
static PyLongObject *
long_add(PyLongObject *a, PyLongObject *b)
{
    if (_PyLong_BothAreCompact(a, b)) {
        stwodigits z = medium_value(a) + medium_value(b);
        return _PyLong_FromSTwoDigits(z);
    }

    PyLongObject *z;
    if (_PyLong_IsNegative(a)) {
    	(...)
    }
    else {
        if (_PyLong_IsNegative(b))
            z = x_sub(a, b);
        else
            z = x_add(a, b);
    }
    return z;
}

와 같이 부호에 따라 관리하며 실제 계산은 x_add와 x_sub를 이용함을 알 수 있다.

 

함수 x_add를 살펴보면 [링크]

// Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t size_a = _PyLong_DigitCount(a), size_b = _PyLong_DigitCount(b);
    PyLongObject *z;
    Py_ssize_t i;
    digit carry = 0;

    /* Ensure a is the larger of the two: */
    if (size_a < size_b) {
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    z = long_alloc(size_a+1);
    if (z == NULL)
        return NULL;
    for (i = 0; i < size_b; ++i) {
        carry += a->long_value.ob_digit[i] + b->long_value.ob_digit[i];
        z->long_value.ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    for (; i < size_a; ++i) {
        carry += a->long_value.ob_digit[i];
        z->long_value.ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->long_value.ob_digit[i] = carry;
    return long_normalize(z);
}

와 같이 실제로 각 digit 당 계산하고 있음을 알 수 있다.

여기서 for문 2개가 중첩이 아닌 나열되어 있고, 자릿수에 따라 반복 횟수가 증가하므로 시간 복잡도는 O(logN)임을 알 수 있다.

 

그렇다면 파이썬에서 덧셈을 이용한 알고리즘 등은 일반적인 시간 복잡도와 다를까?

사실은 대부분의 경우 그렇지 않다.

ob_digits이 digit[]으로 정의되어 혼동될 수 있으나, digit의 정의를 찾아보면 [링크]

// Copyright (c) Python Software Foundation. Licensed under the PSF License v2.
typedef uint32_t digit;

로, uint32_t의 타입을 가진다.

 

uint32_t는 컴파일러와 상관 없이 32bit사용을 강제하는 타입이므로 약 32bit 내에 표현 가능한 값은 한 번의 loop만 거치게 된다.

따라서 대부분의 상황에서 O(1)의 성능을 가짐을 알 수 있다.

 

다만, 앞에서 살펴 보았듯이 캐스팅, 포인터 접근 등 다양한 단계가 있으므로 C++에 비해서는 현저히 느린 것은 사실이다.