파이톤의 정수형은 어떻게 이루어졌을까요?

이 글은 Python Advent Calendar 2021 18일째 되는 글이다.
구글의 소프트웨어 엔지니어 알베르토 오시로 씨How Python Represents Integers using Bignum의 번역입니다.본인의 동의를 얻어 공개하겠습니다.고맙습니다.

Photo by Crissy Jarvis on Unsplash
C/C++ 등 저층 인코딩을 하는 프로그래머는 정수형 메모리 사용량을 주의해야 한다.또 넘침을 막기 위해서는 int가 충분한지, long가 충분한지 자주 고려해야 한다.
C/C++와 달리 파이톤의 정수 값이 넘치지 않기 때문에 파이톤 프로그래머는 정수가 어떤 종류를 사용하는지 고려할 필요가 없습니다.또 파이톤의 정수형은 매우 큰 수를 계산해도 정밀도를 잃지 않는다.유일한 제한은 기계의 메모리 부족(즉 하드웨어 제한)이다.
실제 계산 곱셈의 예를 봅시다.파이톤에서는 결과의 크기에 상관없이 외부 프로그램 라이브러리를 사용할 수 있습니다.

def factorial(n):
   if n == 0 or n == 1:
     return 1
   return n * factorial(n-1)

factorial 함수에 231를 입력하면 Pythn이 얼마나 큰 정수치를 처리할 수 있는지 알 수 있다.

>>> factorial(231)
1792233667382633521618843263044232513197622942259968207385215805123682159320161029848328112148883186161436034535802659466205111867109614573242316954383604389464524535467759401326264883566523043560811873179996072188155290081861628010250468430411854935707396605833540921031884571521279145124581094374547412403086564118143957940727734634769439112260383017302489106932716079961487372942529947238400000000000000000000000000000000000000000000000000000000

NOTE: 이 코드는 정수 크기의 예로서, 더욱 효과적인 알고리즘으로 곱셈을 계산합니다.

정수 표현식

이 글은 가장 보편적으로 사용되는 처리 시스템인 CPythhon의 이야기다.다른 처리 시스템에서 정수 유형의 표현은 다를 수 있습니다.CPython을 사용하는 장점으로 CPython의 코드 기반은 Giithub에서 자유롭게 볼 수 있다.
Python 3 이후 모든 정수 값은 다음 struct로 표시됩니다.

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

매크로를 확장하면 다음과 같습니다.

struct {
   sssize_t ob_refcnt;
   struct _typeobject *ob_type;
   ssize_t ob_size;
   uint32_t ob_digit[1];
};

첫 번째 필드는 중요하지 않습니다.ob_refcnt는 파이톤의 GC에서 사용되며, ob_type는 유형의 ID를 나타낸다.이제 정수입니다.
정수치는 나머지 두 필드ob_digit, ob_size로 표시한다.ob_digit 정수치를 저장하는 각수.ob_size 수조의 길이와 정수치를 저장하는 기호(양과 음).
이렇게 문자열이나 배열로 정수 값을 나타내는 각 자릿수를 임의 정밀도 연산(Bignum Arrithmetic)[1]이라고 합니다.

2^30진수

db_didit의 수조는 정수치 표시에 사용된다.파이톤의 실용성과 효율성은 내장 함수 중의 특수 비트가 많이 필요하기 때문에 32비트를 모두 사용할 수 없습니다.CPython의 창고에 이 제한에 대한 댓글이 있습니다. 관심 있으신 분들은 보세요.
파이톤은 32자리 중 30자리만 사용할 수 있기 때문에 2^30진법으로 모든 정수치를 표시합니다.그 결과 uint32_t 진열의 각 요소는 0에서 1073741823(2^30-1)의 값이다.uint32_t는 2^30진수조의 길이를 나타낸다.
수조 표현식은 소단 절차, 즉 가장 작은 숫자가 먼저 오는 것이다.예를 들어 십진수를 예로 들면 ob_size이라는 숫자는 배열에서 오히려 234처럼 저장된다.
예를 들어, 정수<4,3,2>를 2^30진수로 변환합니다.기호가 2^30진수를 표시하기에 부족하기 때문에 여기에는 10진수로 표시합니다.234254646549834273498의 정수치234254646549834273498462328538,197050268,203의 첫 번째 digit, 그 다음462328538, 마지막 digit197050268이다.digits는 이렇게 정수치로 되돌아갈 수 있습니다.

>>> 462328538*(2**30)**0 + 197050268*(2**30)**1 + 203*(2**30)**2
234254646549834273498L

203의 정수치는 파이톤에서 2^30진법234254646549834273498의digits를 사용하여 struct 필드는 다음과 같다.

NOTE: 값이 음수일 경우462328538,197050268,203는 같고ob_digit는 ob_size입니다.

최적화

임의의 긴 정수를 사용하여 정수를 표시하거나 정수를 계산하여 실행할 때의 비용을 표시합니다.파이톤-3형은 정음형으로 파이톤 해석기는 프로그램이 실행되기 전에 미리 제작int부터 -5까지의 전체 수를 필요하면 사용한다.
임의의 긴 정수를 사용하는 명확한 단점은 메모리 사용량이다.파이톤에서는 C 언어의 7~14배에 달하는 정수 값이 최소 28바이트 이상 필요합니다.

임의의 길이 정수 더하기

임의의 장정수 연산의 장점은 연산의 단순성에 있다.이 글은 덧셈만 설명하고 다른 연산도 기본적으로 같다.임의의 장정수의 덧셈은 10진법 때 종이와 연필의 덧셈과 같다.우선 가장 작은 자릿수를 더한 다음에 계산을 다음 자릿수로 옮겨라.여러분의 계산 결과는 다음 분으로 보류됩니다.

배열을 사용하여 Python의 임의의 길이 정수를 계산합니다.연산 대상의 두 숫자의 수조 중의 각 요소를 더하고, 자릿수를 초과할 때 그것을 다음 자리로 옮긴다.이 알고리즘은 수조 원소256에서 시작하여 소수조의 길이까지 이어진다.우선, 빈 그룹을 만들 수 있지만, 이 그룹의 원소 수량은 두 연산 대상 중 비교적 큰 그룹보다 크다.0와 9(덧셈 결과93의 경우 비교적 큰 수치102가 2위, 계산 결과는 3위였다.계산 결과는 비교적 큰 비트와 동시(e.g.93+1=93로 계산한 후 배열을 단축한다.
두 개의 숫자94와 234254646549834273498를 예로 들면 임의의 길이 정수의 덧셈을 도해한다.23425464654983의 struct는 다음과 같다.
234254646549834273498의 struct는 다음과 같다.

덧셈 알고리즘은 먼저 원소수 4부터 배열(비교적 큰 수치23425464654983의 수조가 큰 원소수)

다음은 각 자릿수를 더한다.

왼쪽에서 첫 번째 작은 배열의 길이를 맞추면 이런 중도 결과다.

마지막으로 하나의 배열 크기를 줄이고 덧셈 결과는 다음과 같다.

CPython의 코드는 C 언어인데, Python으로 이 덧셈 연산을 표시하면 이렇게 된다.

base = 2**30

def add(x, y):
    # making sure x is larger than y
    if len(x) < len(y):
        x, y = y, x

    # result list is one digit longer than x
    z = [0] * (len(x) + 1)
    carry = 0
    i = 0
    while i < len(y):
        total = x[i] + y[i] + carry
        z[i] = total % base
        carry = total // base
        i += 1

    while i < len(x):
        total = x[i] + carry
        z[i] = total % base
        carry = total // base
        i += 1

    z[i] = carry
    # removing leading 0's.
    if z[i] == 0:
        z = z[:-1]
  
    return z

234254646549834273498 함수는 두 개의list를 취한다.모든list는 더하기 대상의 2^30진법의 배열입니다.

끝말

파이썬은 정수 값에 임의의 긴 정수를 사용합니다.파이톤의 정수 값은 자바, C/C++ 등의 언어에 비해 매우 쉽게 사용할 수 있다.다른 언어에서 프로그래머는 어떤 종류를 사용해야 하는지 고려해야 하고, 파이톤은 추상화되어 있다.반면 파이톤의 정수치는 메모리 사용량에 불리하지만lit도 있다.C 언어에서는 2, 4바이트는 정수 값을 처리할 수 있지만, 파이톤은 최소 28바이트가 필요하다.간단한 스크립트는 이 정도의 차이를 무시할 수 있지만, 더 큰 데이터를 처리하는 프로그램에서는 C 언어와 같은 프로그래밍 언어를 사용하는 것이 좋을 수 있다.

References

Python internals: Arbitrary-precision integer implementation

How python implements super long integers

각주
임의 정밀도 연산 ↩︎