[Python] 정수형(Integer)과 오버 플로우

자바 혹은 C언어 같은 프로그래밍 언어를 배우다보면 정수형(int) 변수의 오버플로우에 대해서 배우게 된다. 자바와 C언어의 int 변수에 저장할 수 있는 숫자는 상한 값이 있다. 이 상한 값을 넘어버리면 갑자기 숫자가 마이너스 값으로 표기되는 문제가 발생한다. 따라서 큰 값의 정수형 데이터를  다룰 때에는 long 타입을 사용해야한다. 그것보다 더 큰 천문학적인 숫자를 정확하게 다루려면 별도의 알고리즘을 구현해서 사용해야한다.

파이썬에서는 약간 다르다. 파이썬에서는 버전별로 오버플로우 관련 내용이 다르다. 정수형 데이터의 한계값과 타입을 검사해볼 수 있는 코드를 생각해보자.

import sys

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

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

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

파이썬 2.x 에서는 maxint라는 값이 정해져 있다. 정수형 타입인 int가 표현할 수 있는 최대 값에 대한 내용으로 이 값보다 큰 정수 값은 long 타입으로 처리된다.

반면 파이썬 3에서는 maxint 값이 정의되어 있지 않다. 한계 값이 없다는 소리인데, 파이썬 2.x의 maxint 값을 그대로 사용해보자.

type(9223372036854775807)
type(9223372036854775807 + 1)

실행 결과는 다음과 같다.

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

파이썬 2.x 에서 long으로 처리되었던 큰 수도 파이썬 3에서는 int 타입으로 처리되고 있다. 흥미로운 결과다. 정해진 크기의 바이트로 표현할 수 있는 정수의 상한은 정해져있기 마련인데, 파이선 3에서는 어떤식으로 정수를 처리하길래 한계가 없을까?

Python 3의 정수처리

파이썬 3의 정수처리에 대한 힌트는 파이썬 문서에서 찾을 수 있다. PEP 237 -- Unifying Long Integers and Integers의 내용읽어보면 파이썬 3.x 버전에서 long 타입과 int 타입의 통합에 대한 내용을 볼 수 있다.

파이썬 3에서는 정수 타입의 값을 '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

파이썬3에서는 Arbitrary-precision arithmetic을 사용해서 오버플로우를 피했다고 했다. Arbitrary-precision arithmetic은 사람이 계산하는 방식을 따른다.두 정수를 더하는 과정을 초등학생때 배운 방법으로진행해보자. 알고리즘은 다음과 같이 진행된다.

1004 + 1008

1. 일의 자리를 더한다. 8+4=12
2. 2는 1의 자리 결과가 되고, 1이라는 값은 십의 자리로 올려(carry)진다.
3. 십의 자리 값을 더한다. 여기에 일의 자리에서 올라온 Carry 값을 함께 더한다. 0 + 0 + 1 = 1
4. 백의 자리 값을 더한다. Carry 값이 없기 때문에 백의 자리만 더하면 된다. 0 + 0 = 0
5. 천의 자리를 더한다. Carry 값이 없기 때문에 천의 자리만 더한다. 1 + 1 = 2
6. 더 이상 더할 자리가 없으므로 각 자리의 더한 결과를 합쳐서 최종 결과 값을  도출한다. 결과 : 2012

당장 1004와 1008을 더 하라고하면 흰 종이에 두 숫자를 쓰고 이런 알고리즘으로 숫자를 더하게 될 것이다. (두 숫자를 이진수로 바꾼 다음에 이진수의 각 비트를 더하는 사람은 별로 없을 것이다.)

Arbitrary-precision arithmetic 연산은 이런식으로 진행된다. 아무리 큰 두 숫자를 더하는 과정이라도 이런 식으로 한자리씩 더하고 올리는 식으로 계산을 해주면, 오버플로우라는 것은 겪지 않게 된다.

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

이런 방식을 이용해서 사람이 사칙연산 하는 것과 비슷한 알고리즘으로 정수 연산을 할 수 있다. 우리가 종이에 계산하는 과정에서 오버플로우를 만나지 않는 것처럼 이 알고리즘을 이용하면 오버플로우 걱정없이 매우 큰 정수에 대한 연산을 할 수 있다.

하지만 이런 방식의 단점은 느리다는 것이다. 2진수로 표현된 비트 나열을 하드웨어적으로 계산하는 방식에 비해서는 아무래도 연산속도가 느릴 수 밖에 없다. 하지만 오버플로우를 신경쓰지 않고 프로그래밍을 할 수 있다는 장점이 있고, 부동소수 계산의 경우에는 정확한 값을 얻을 수 있다는 장점도 있다. (2진수로 계산하는 부동소수 연산은 100% 정확하지 않을 수 있다.)

---

파이썬 스크립트 작성에 도움되는 글 모음