파이썬(Python) 정수 자료형(Integer)과 오버플로우(Overflow)

C언어 혹은 자바에서는 정수 자료형(int)의 오버플로우(Overflow) 문제를 생각해야 한다. 충분히 큰 값의 정수형 데이터를 다룰 때에는 long 타입을 사용해야한다는 점은 C언어와 자바를 이용해 프로그래밍하는 개발자에게는 상식과도 같다.

 

하지만 파이썬에서는 약간 다를 수 있다. 우선 정수형 데이터의 한계값과 타입을 검사해볼 수 있는 코드를 준비하자.

import sys

print sys.maxint
type(sys.maxint)
type(sys.maxint + 1)

이 코드를 파이썬2.x 인터프리터에서 실행해보면 다음 결과를 얻게 된다.

9223372036854775807
<type 'int'>
<type 'long'>

파이썬2에는 maxint라는 값이 존재한다. 정수형 변수가 표현할 수 있는 최대값이 지정되어 있으며 이 값보다 큰 값은 long 타입으로 다뤄진다.

 

파이썬3에서는 약간 다르다. 우선 위 코드를 실행하면 에러가 발생한다. sys.maxint 라는 attribute가 없다는 에러가 발생하는데, int 타입이 다룰 수 있는 한계가 없다는 의미다. 코드를 다음과 같이 살짝 고쳐보자.

type(9223372036854775807)
type(9223372036854775807 + 1)

Python 2.x에서 maxint 값이었던 정수형의 타입을 체크해보는 코드다. 실행 결과는 다음과 같다.

<type 'int'>
<type 'int'>

둘 다 'int' 타입으로 처리되고 있다.

Python 3.x 의 정수처리

파이썬의 PEP-237 문서를 보면 Python 3.x에서 long 타입과 int 타입의 통합에 대해서 이야기한 내용을 확인할 수 있다. (링크 : PEP 237 -- Unifying Long Integers and Integers) 시간나면 내용을 읽어보도록하자.

 

Python 3.x에서는 정수 타입의 자료형에 'Arbitrary-precision arithmetic'을 사용했다. (링크 : Arbitrary-precision arithmetic - Wikipedia) 위키 페이지에 가보면,

Some programming languages such as Lisp, Python, Perl, Haskell and Ruby use, or have an option to use, arbitrary-precision numbers for all integer arithmetic.

파이썬도 Arbitrary-precision arithmetic을 사용했음을 알 수 있다.

정수 타입의 오버플로우

자바나 C언어의 정수타입 연산은 CPU 아키텍처와 연관된다. 32비트 CPU를 사용하는 경우 (2^31 -1) 까지 수를 표현할 수 있다. 32개의 비트 중에 MSB(Most Significant Bit)는 부호를 표현하는데 사용되며 나머지 31개의 비트를 이용해서 숫자를 표현하게 된다.

 

4비트 환경을 예로 들어보자.

0 : 0000
1 : 0001
2 : 0010
3 : 0011
4 : 0100
5 : 0101
6 : 0110
7 : 0111
-1: 1111
-2: 1110
-3: 1101
-4: 1100
-5: 1011
-6: 1010 
-7: 1001
-8: 1000

4비트로 표현할 수 있는 정수들을 나열해봤다. 7을 표현한 0111에서 +1 연산을 수행해보자. 2진수 연산을 하는 CPU는 1비트를 더해서 1000을 얻게 된다. 문제는 1000은 8을 표현한게 아니라 -8을 표현하는 값으로 7에 1을 더했는데 -8이 출력되는 현상을 겪게된다. 이를 정수 타입의 오버플로우(Overflow)라고 한다.

Arbitrary-precision arithmetic

그럼 Python 3.x 버전은 어떻게 정수 계산을 하는지 살펴보자. Arbitrary-precision arithmetic 연산은 조금 더 사람처럼 계산한다. 사람이 일반적으로 두 정수 값을 더하는 과정을 살펴보자.

1004+1008   1004 + 1008 ------   1) 1의 자리를 더한다. 8+4=12 2) 2는 1의 자리 결과가 되고, 1이라는 carry가 발생한다. 3) 10의 자리를 더한다. 여기에 1의 자리에서 올라온 carry를 같이 더한다. 0+0+carry = 1 4) 100의 자리를 더한다. carry가 있으면 같이 더한다. 0+0+carry=0 5) 1000의 자리를 더한다. carry가 있으면 같이 더한다. 1+1+carry=2   결과는 2012가 된다.

1의 자리에서부터 숫자를 더해가며 자리 올림이 발생하면 하나를 다음 자리로 올려서 계산을 한다. 모든 자리수를 다 계산하면 연산이 종료된다. 뺄셈도 비슷하다.

 

Arbitrary-precision arithmetic 연산을 위해서 정수 타입을 저장하기 위한 구조체를 C언어 스타일로 표현하면 다음과 같다.

struct {
    unsigned long length;
    uint32_t *digits;
} bignum;

구조체 멤버의 length에는 몇 자리인지 저장되고, digits 멤버는 각 자리수를 저장하는 배열이다. 1004라는 숫자를 다음과 같이 표현할 수 있다.

bignum.length = 4

bignum.digits[0] = 4
bignum.digits[1] = 0
bignum.digits[2] = 0
bignum.digits[3] = 1

이 구조체를 이용해서 사람이 사칙 연산하는 것과 비슷한 알고리즘으로 정수 연산을 하게 된다. 이런 표현을 이용하면 length 숫자와 배열 사이즈를 늘리면 int 타입으로 표현할 수 없었던 매우 큰 정수 값도 계산할 수 있게 된다.

 

2진수로 표현된 비트 나열을 하드웨어적으로 계산하는 C언어에 비해 Arbitrary-precision arithmetic으로 계산하는 파이썬의 사칙연산은 아무래도 느릴 수밖에 없다. 하지만 maxint 이상의 값을 프로그래머가 인지하고 처리해야 하는 C언어에 비해서 파이썬의 사칙연산은 프로그래머에게 부담을  주지 않는다.

 

특히 C언어에서의 2진수 부동소수 표현은 계산에서 부정확한 결과를 줄 수 있는 반면 Arbitrary-precision arithmetic으로 계산하는 방식은 정확한 값을 얻을 수 있다는 장점도 있다.