Python Overflow

1. Prologue

2. Overflow

3. Python Overflow

    3.1. Aribitrary Precision Arithmetic

4. Epilogue

---

1. Prologue

Python inf에 대해 다룬, 하나의 코드에서 의문이 시작했다.

 

import sys

# 922_3372_0368_5477_5807
int_pos_inf = sys.maxsize

# -922_3372_0368_5477_5808
int_neg_inf = -(sys.maxsize + 1)

바로 sys.maxsize이다. 922경이라는 매우 큰 수를 반환하니 가히 무한이라 할 수 있다.

이때 양의 무한대가 아닌 음의 무한대를 표현하려면 1을 더하고 -1을 곱해준다.

1을 더해주는 이유는 당연히 다른 자료형과 마찬가지로 정확한 범위 설정을 위함이다.

그렇다면 int_pos_inf에 1을 더하면 오버플로우가 발생할 테니 똑같은 값이겠군!

 

어라? 왜 오버플로우가 발생하지 않는 거지?

그러고 보니 이상하다. -1을 곱하고 1을 더 빼는 게 아니라, 미리 1을 더하고 -1을 곱했네?

파이썬의 엄청난 구조 때문에 실은 몇 바이트 차지하지 않는다든가?

해서 메모리도 확인해보았는데 36 Byte나 차지하고 있었다.

 

심상치 않음을 감지하여 더 큰 수를 확인해보았다. 바로 무한대에 가까운 수를 제곱하였다.

...오버플로우가 일어날 기미가 전혀 없이 거뜬하게 값을 출력했다.

심지어 44 Byte로 늘어난 것을 알 수 있다.

 

의문을 갖던 중 내 궁금증을 최고로 만들어 준 대망의 계기이다.

백준의 어떤 문제를 풀다보니 꽤 간단한 DP로 해결 가능한 규칙을 찾았고, 테스트 해보았다.

이때 깜빡하고 나머지 연산을 수행하지 않고, 문제 조건의 최댓값을 넣어버렸다.

그랬더니 뭐라 불러야 할지도 모를 충격적인 숫자가 나왔다.

저 숫자가 차지하는 메모리 용량만해도 228 Byte다.

 

2. Overflow

파이썬의 구조에 대해 들어가기 전 Overflow에 대해서 간단하게만 짚고 넘어가자.

Overflow란, 값이 증가하면서 허용한 최댓값 초과로 올라가면서 발생하는 '오류'이다.

 └ 이와 반대로, 허용한 최솟값 미만으로 내려가 발생하는 오류는 Underflow라고 부른다.

 

요점은 특정 범위가 있고, 범위를 벗어날 때 발생하는 오류라는 거다.

통상 프로그래밍 언어에서 변수는 이름을 붙여 저장한다.

이때 변수 값을 저장하기 위해 메모리 공간을 확보하고, 그것을 '자료형(Data type)'이라고 부른다. 

 

가장 대표적으로 integer(정수) 타입에는 4 Byte를 할당한다.

그래서 최댓값은 '2 ^ 31 - 1 = 2,147,483,647'라는 21억의 값을 갖는다.

 └ 자바나 C 정수 타입 연산은 CPU architecture와 연관되어, 32bit 사용 시 2^31-1까지 표현한다.

 └ MSB는 부호를 표현하는 데 사용하여 31bit로만 표현한다.

이러한 자료형은 값을 계산하기 위해 중요하게 사용한다.

int로 부족한 공간은 long long을 사용하고, 실수의 경우 float가 아닌 double을 사용한다.

 

3. Python Overflow

num = 10
txt = "num이라는 변수는 10입니다"

하지만 Python에서는 자료형 없이 변수를 선언한다. 이는 파이썬의 모든 것을 객체(Object)로 구현하기 때문이다.

정수 값을 넣어준다면 정수 클래스 객체로, 문자열을 넣어준다면 문자열 클래스 객체로 선언한다.

Python에서는 변수가 자신만을 위한 메모리를 갖는 것이 아닌, 객체를 가리키는 것이다.

Python이 왜 느린지, 변수 관리 방식에 대한 글이다. 궁금하면 직접 더 읽어보자.

 └ http://jakevdp.github.io/blog/2014/05/09/why-python-is-slow/

 

https://peps.python.org/pep-0237/

하지만 이전 버전, 즉 Python 2에는 정수형 데이터 타입에 int와 long이 있었다.

int는 C에서의 정수형 데이터 타입과 같은 방식의 자료형이었고,

long은 Arbitrary precision이라는 것을 지원하는 데이터 타입이었다.

기본적으로 정수 연산 시 int를 사용하되, overflow가 발생할 것 같으면 자동으로 long을 사용하여 overflow를 막았다.

 

Python 3로 넘어오면서 많은 변화가 있었는데, 그중 하나가 PEP 237을 따른 것이다.

이에 따라 int를 long의 방식으로 통합하고 이름을 int로 함으로써 arbitrary precision을 지원하는 int만이 남게 되었다.

 └ 하지만 Python 3에서도 numpy, pandas 같은 패키지는 아직도 C 스타일을 유지해 overflow에 주의해야 한다.

 

    3.1. Arbitrary Precision Arithmetic

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

컴퓨터 과학에서, 임의 정밀도 산술은, 호스트 시스템의 사용 가능한 메모리 내에서 각각의 자릿수에 대한 연산을 수행하는 것을 말한다. 이는 큰 수 산술, 복수 정밀도 산술, 가끔은 무한 정밀도 산술이라고도 부른다.

 

그럼 대체 Arbitrary precision가 뭐길래 무한한 자료형을 제공하는 걸까?

위키피디아 정의를 가져온 것으로, 사람이 계산하는 방식을 그대로 따라하는 것이다.

그러니까 정해진 메모리를 사용하는, 기존의 Fixed-precision과 달리, 사용 가능한 메모리를 계속 끌어다 사용한다.

특정 값을 나타내는데 4 Byte로 부족하다면 5, 6... 이렇게 유동적(the available memory)으로 운용한다.

 

https://mortada.net/can-integer-operations-overflow-in-python.html

Python 3.4를 기준으로 아주 큰 정수를 표현할 때 사용하는 메모리의 크기를 그린 그래프이다.

 └ 따로 확인한 결과 Python 3.11에서도 같은 그래프를 그린다.

2^0부터 2^30-1까지는 28 Byte를 사용하다가, 특정 수를 넘길 때마다 4 Byte씩 증가하면서 수를 표현한다.

0이든 100이든 1000이든 28 Byte를 잡아먹는 건 overhead가 지나친 게 아닌가 싶다.

그렇게 생각하며 찾아보던 중 감사하게도 이를 분석해주신 분이 계시다.

 └ 분석 블로그 : https://tyoon9781.tistory.com/entry/python-int-size-28bytes

 

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

자세하게는 말고 정말 간단하게 어떤 방식으로 arbitrary precision arithmetic을 구현하는지 알아보자.

사용 가능한 메모리를 끌어다 쓰는 연산을 위해, 정수를 저장한 구조체를 C로 표현하면 위와 같다.

length에는 몇 자리 숫자인지, digits에는 각 자릿수를 저장한다.

 

bignum.length = 4

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

1004라는 숫자가 있으면 위와 같이 저장할 수 있다.

각 자릿수를 저장하고, 연산을 수행한다. 올림수가 발생하면 길이와 배열을 늘려주고, 올림값을 저장한다.

이런 방식을 이용해 사람이 사칙연산하는 것과 흡사한 알고리즘 구현을 할 수 있다.

우리가 종이에 계산할 때 오버플로우가 발생하는가? 그렇지 않다.

초반에 말한 "사람이 계산하는 방식을 그대로 따라하는 것"은 이걸 말한다.

 

하지만 그렇기에 Python은 느릴 수밖에 없는 언어가 됐다.

2진수로 표현한 비트 나열을, 하드웨어적으로 일일이 계산한다면 당연히 느려진다.

 

4. Epilogue

내가 생각한 것보다 더 깊게 들어간 느낌이다.

뭐 하나 허투루 만들어진 게 없고, 모든 것에는 다 이유가 있다.

생각해보면 21억이 넘어가는 수가 종종 나오곤 했지만, Python에 익숙해져 넘어간 적이 많다.

힘들지만, 하나하나 의심하고 생각해보는 습관이 중요해지는 요즘이다.

 

 

고민을 시작한 문제 출처 : https://miny-genie.tistory.com/222

참고한 문서 자료 : https://peps.python.org/pep-0237/

참고한 문서 자료 : https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

참고한 문서 자료 : https://en.wikipedia.org/wiki/Fixed-point_arithmetic

참고한 웹 사이트 : https://yunreka.tistory.com/3

참고한 웹 사이트 : https://velog.io/@toezilla/1D1Q-001.-Python의-int-자료형은-어떻게-범위가-무제한일까

참고한 웹 사이트 : http://jakevdp.github.io/blog/2014/05/09/why-python-is-slow/

참고한 웹 사이트 : https://ahracho.github.io/posts/python/2017-05-01-everything-in-python-is-object-integer/

참고한 웹 사이트 : https://hbase.tistory.com/109

참고한 웹 사이트 : https://mortada.net/can-integer-operations-overflow-in-python.html

참고한 웹 사이트 : https://tyoon9781.tistory.com/entry/python-int-size-28bytes