3.5 변수 범위의 이해 ( 산술 오버플로)

• 이 블로그 내의 모든 내용은 알고리즘 문제 해결 전략 (저 구동만 출판: 인사이트) 내용을 요약한 것입니다. 
• 제가 이해한 대로 정리한 내용이기에 본문의 내용과 상이할 수 있습니다. 

이 포스팅을 하기 전 저는 파이썬, go 언어로 코딩을 주로 하기에 산술 오버플로에는 신경을 많이 쓰지 않았습니다.

이 책의 내용을 정리하면서 파이썬은 어떻게 산술 오버플로를 해결하지? 파이썬에서 이런 문제가 없었는데? 라는 생각이 들었습니다.

검색 결과 파이썬도 산술 오버플로를 해결할 수 있는 API를 사용한다는 것을 알게 되었고 책의 내용을 정리 후에 파이썬에서는 어떻게 산술 오버플로를 해결하는지를 알아보겠습니다. 

* 산술 오버플로란? 

- 어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우 

- 산술 오버플로는 프로그래밍을 하면서 저지를 수 있는 수많은 실수 중에서도 가장 흔한 실수라고 할 수 있다. 

1) 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 나더라도 별다른 경고를 해 주지 않는다. 
   연산이 일어날 때마다 오버플로를 확인하는 것이 너무 비효율적이기 때문 

2) 프로그램의 정당성을 검증할 때 프로그램 논리의 정확성에만 집중하다 보면 산술 오버플로가 등장할 수 있다는
   사실을 잊기 쉽다. 

아래에서부터 산술 오버플로가 등장하는 대표적인 경우들을 살피고 이들을 피해갈 수 있는 방법들을 다룹니다. 

- 현대의 많은 언더들에서는 메모리가 허락하는 한도 내에서 가능한 한 큰 정수를 구현하는 클래스들을 표준 라이브러리에서 제공하기 때문에 산술 오버플로를 신경 쓸 일이 크게 줄어들었다. ( c/c++에는 그런 클래스가 없다) 
- 그러나 이런 클래스들은 훨씬 많은 메모리와 시간을 필요로 하기 떄문에 이런 기법들을 공부할 가치는 여전히 충분하다. 

 

1. 너무 큰 결과 

- 습관적으로 32비트 정수형을 쓰는 경우 

- 최종 결과는 64비트 정수를 이용하면서 중간 계산 값을 32 비트로 전달 하는 경우 

- 큰 정수를 다룰 때에는 항상 변수의 형태에 주의하는 습관을 들이자. 

 

2. 너무 큰 중간 값 

- 프로그램의 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우 

 

3. 너무 큰 '무한대' 값 

- 프로그램을 짤 때 무한대에 해당하는 큰 값을 이용하는 것이 편리할 때가 있다. 
(해당 자료형이 처리 할수 있는 가장 큰 값을 무한대 값으로 쓰는 것, 예를 들어 32비트 부호 있는 정수라면 2^31 -1) 

- 무한대 값을 선택할 때에는 이 무한대 값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴봐야 한다. 

 

4. 오버플로 피해가기 

- 가장 간단한 방법은 더 큰 자료형을 쓰는 것 

- 문제에 따라 계산 방법을 다르게 하여 오버플로를 피해가는 방법도 있다. (ex : 이항 계수) 
- 이항 계수에 대해 성립하는 점화식을 이용하면 오버플로에 신경 쓰지 않을 수 있다. (8장의 동적계획법에서 소개한다) 

 

* 서두에서 말씀드렸던 것처럼 사실 파이썬으로 주로 문제를 푸는 저는 이 3.5 장에서 배울게 있나? 라는 생각을 했습니다. 하지만, 파이썬에서 오버플로를 어떻게 피해가는지를 알아본 결과 결국 파이썬도 C로 구성되어 있다는 것을 알게 되었습니다. 

 

파이썬에서의 오버플로우

그런데 파이썬 3에서는 오버플로우가 없다는 기가 막힌 제보를 듣고, 어떻게 이게 가능한지 찾아보기로 했다. 실제 ‘python integer overflow’ 키워드로 구글링을 하니까 관련된 질문들이 많이 검색되었다.

• 파이썬 3에서는 long 타입이 없어지고 int 타입만 남았는데, 이 int가 arbitrary precision을 지원하여 오버플로우가 발생하지 않게 되었다.
• 하지만 파이썬3에서도 pydata stack을 사용하는 numpy/pandas 같은 패키지를 사용할 때는 C 스타일이 유지되기 때문에 오버플로우 발생을 고려해야 한다.

arbitrary precision은 뭔데?

In computer science, arbitrary-precision arithmetic, also called bignum arithmetic, multiple precision arithmetic, or sometimes infinite-precision arithmetic, indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. (Wikipedia)

즉, arbitrary-precision은 사용할 수 있는 메모리양이 정해져 있는 기존의 fixed-precision과 달리, 현재 남아있는 만큼의 가용 메모리를 모두 수 표현에 끌어다 쓸 수 있는 형태를 이야기하는 것 같다. 예를 들어 특정 값을 나타내는데 4바이트가 부족하다면 5바이트, 더 부족하면 6바이트까지 사용할 수 있게 유동적으로 운용한다는 것이다.

Can Integer Operations Overflow in Python?
위 블로그 포스트를 참고해서 실제로 파이썬에서 아주 큰 정수를 표현할 때 사용하는 메모리의 크기가 어떻게 변화하는지 확인해봤다.

그래프를 보면 2^0부터 2^30 -1을 표현할 때까지는 28바이트(!)를 사용하다가, 2^30부터는 4바이트 늘어난 32바이트를 수 표현에 사용한다. 그 이후 일정 수를 넘어가면 4바이트씩 증가하면서 수 표현에 사용하는 바이트 수가 탄력적으로 늘어나는 것을 볼 수 있다.
여기에서 궁금한 것은 아무리 파이썬에 데이터분석에 많이 사용되는 언어라지만 그래도 보통 작은 정수를 사용하는 경우가 훨씬훨씬 많을텐데 기본적으로 사용하는 바이트수가 28바이트나 되는 건 오버헤드가 지나친 게 아닌가 하는 점이다.

어떻게 구현되어 있을까?

파이썬에서는 모든 것은 객체이다. 그렇기 때문에 X라는 수가 있다면 그것도 역시 객체로 존재하는 것이고, 객체의 attribute에 관련된 정보를 담고 있을 것이다. 파이썬에서 큰 정수가 arbitrary precision으로 구현된다면, 현재 이 수가 총 몇 바이트를 사용해서 표현되고 있는지 기억하고 있어야 할 것이고, 나는 그 정보가 정수 클래스의 ob_digit이라는 변수에 저장될 것이라고 추측했다.

 

// Include/longintrepr.h
// 정수 타입을 나타내는 클래스(struct) 
struct _longobject { 
	PyObject_VAR_HEAD 
    digit ob_digit[1]; 
};

그런데 여기서 궁금한 지점은 파이썬도 기본적으로 제일 밑단에서는 C API로 구현되었다고 이해하고 있는데, 4바이트 밖에 처리 못하는 C를 가지고 큰 수 표현을 어떻게 구현해냈는지이다. 마찬가지로 검색을 좀 해보니, integer array로 저장해서 초등학교 때 자리수 하나씩 계산하듯이 하면된다는 답변을 찾았다!
Quora - How is a long integer implemented in python?

그렇다면 실제로 어떻게 구현되어 있을까? 
CPython Include/longintrepr.h

PyObject * 
PyLong_FromUnsignedLong(unsigned long ival) 
{
	PyLongObject *v;
    unsigned long t;
    int ndigits = 0;
    
    /* Count the number of Python digits. */
    t = (unsigned long)ival;
    while (t) {
    ++ndigits;
    t >>= PyLong_SHIFT;
    }
    v = _PyLong_New(ndigits);
    if (v != NULL) {
    	digit *p = v->ob_digit;
        Py_SIZE(v) = ndigits;
        while (ival) {
        	*p++ = (digit)(ival & PyLong_MASK);
            	ival >>= PyLong_SHIFT;
            }
        } return (PyObject *)v;
}