변수 범위의 이해

산술 오버플로

컴퓨터의 모든 변수에는 담을 수 있는 크기가 제한되어 있다. 산술 오버플로는 어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우를 말한다. 산술 오버플로는 프로그래밍을 하면서 저지를 수 있는 수많은 실수 중에서도 가장 흔한 실수라고 할 수 있는데, 여기에는 크게 두 가지 이유가 있다.

1. 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 나더라도 별다른 경고를 해주지 않는다. 연산이 일어날 때마다 오버플로 확인하는 것이 너무 비효율적이기 때문이다.
2. 프로그램의 정당성을 검증할 때 프로그램의 논리의 정확성에만 집중하다 보면 산술 오버플로가 등장할 수 있따는 사실을 잊기 쉽다.

이제 산술 오버플로가 등장하는 대표적인 경우들을 살피고 이들을 피해갈 수 있는 방법들을 다뤄보자.

너무 큰 결과

프로그램이 출력해야 할 결과가 우리가 흔히 사용하는 32비트 자료형의 범위를 넘어가면 64비트 정수를 사용하거나 큰 정수 구현을 이용해야 한다. 하지만 습관적으로 32비트 정수를 쓰는 실수가 꽤나 흔하다. 그 외에도 최종 결과는 64비트 정수를 이용하면서 중간 계산 값을 32비트 정수로 전달한다든지 하는 실수도 자주 볼 수 있다. 큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관을 들여야 한다.

너무 큰 중간 값

프로그램의 출력 밧의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우가 있다. 예를 들어 두 개의 32비트 부호 있는 정수를 입력받아 이 둘의 최소공배수를 반환하는 함수를 생각해보자. 두 값 a와 b의 최소공배수 lcm(a,b)는 두 수의 최대공약수 gcd(a,b)를 이용해 다음 식으로 구할 수 있다.

lcm(a,b) = (a * b) / (gcd(a,b))

이것을 코드로 옮기면 다음과 같다.

int gcd(int a, int b);	// 두 수의 최대공약수를 반환한다.

int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

위의 코드는 lcm(50000, 100000)을 계산하면 오류가 발생한다. 계산의 중간 값이 32비트 정수 범위를 벗어나기 때문이다. 이때 C++는 우리에게 아무 경고도 하지 않고 이 값의 마지막 32비트만을 취하기때문에 오류가 발생한다. 코드의 논리를 보는 것만으로는 이런 버그를 찾기가 힘들다.

너무 큰 '무한대' 값

프로그램을 짜다 보면 무한대에 해당하는 큰 값을 이용하는 것이 편리할 때가 있다. 예를 들어 두 위치를 잇는 가장 짧은 길의 길이를 구하는 코드를 작성한다고 하자. s에서 t까지 가는데 세 중간 지점 a, b, c 중 항상 한군데를 거쳐 가야 한다면 (s, t) 구간의 최단 경로의 길이 dist(s, t)는 다음 식으로 계산할 수 있다.

dist(s, t) = min(dist(s, a) + dist(a, t),
		 dist(s, b) + dist(b, t),
         	 dist(s, c) + dist(c, t))

그런데 만약 어떤 두 구간을 잇는 경로가 없으면 어떻게 될까?
길이 존재하지 않음을 나타내는 특수한 값을 사용하려면 이 값에 대한 예외 처리를 따로 해줘야 한다. 반면 길이 없는 경우 실제로 나타날 리 없는 매우 큰 값을 반환하면 min()에서 자동으로 걸러지므로 예외 처리가 필요 없어 간편하다.
이 테크닉을 쓸 때 하기 쉬운 실수는 해당 자료형이 처리할 수 있는 가장 큰 값(예를 들어 32비트 부호 있는 정수라면 2^31 -1)을 무한대 값으로 쓰는 것이다. 이 값은 다른 어떤 값보다도 크지만, 앞의 경우에서 dist(s, a) = 2^31 - 1이고 dist(a, t) = 2라면 32비트 부호 있는 정수를 쓸 경우 오버플로가 발생하여 음수가 되어 버린다. 그러면 min()에서 정상적인 경로들 대신에 존재하지 않는 경로를 선택하게 된다.
따라서 무한대 값을 선택할 때는 이 무한대 값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 이럴 때도 오버플로가 나지 않을 크기의 값을 선택하는 것이 좋다.

오버플로 피해가기

오버플로가 발생한다는 사실을 알았을 때 어떻게 코드를 고치면 오버플로를 막을 수 있을까? 가장 간단한 방법은 더 큰 자료형을 쓰는 것이다.
두 번째 방법은 오버플로가 나지 않도록 연산의 순서를 바꾸는 것이다.

자료형의 프로모션

피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 대개 이들을 같은 자료형으로 변환해서 계산하는데 이를 프로모션이라고 한다. 이 프로모션은 대부분의 경우에는 신경 쓸 필요가 없지만, 가끔 알기 어려운 버그를 만드는 주역이 되기도 한다.
프로모션의 과정은 언어에 따라 조금씩 다르지만, C++의 경우 다음과 같은 규칙들이 적용된다.

1. 한쪽은 정수형이고 한쪽은 실수형일 경우
   정수형이 실수형으로 변환된다.
2. 양쪽 다 정수형이거나 양쪽 다 실수형일 경우
   보다 넓은 범위를 갖는 자료형으로 변환된다.
3. 양쪽 다 int형보다 작은 정수형인 경우
   양쪽 다 int형으로 변환된다.
4. 부호 없는 정수형과 부호 있는 정수형이 섞여 있을 경우
   부호 없는 정수형으로 변환된다.

프로모션에 관련된 문제들은 대개 부호 있는 정수와 부호 없는 정수형이 섞였을 때 일어난다.

실수 자료형의 이해

실수 연산의 어려움

//[1,n]범위의 자연수 x에 대해 x * 1.0 / x == 1인 x의 수를 센다.
int countObvious(int n) {
	int same = 0;
    	for (int x = 1; x <= n; ++x) {
        	double y = 1.0 / x;
            	if (y * x == 1.0)
                	++same;
        }
        return same;
}

countObvious(n)을 호출하면 당연히 n이 반환되어야 한다. 그런데 이 함수를 직접 수행해 보면 결과는 그렇지 않다. 이 의문을 해결하려면 컴퓨터가 사용하는 실수 표현 방식에 대해 알아야 한다.

실수와 근사 값

우리가 일상적으로 다루는 정수들은 컴퓨터가 모두 정확하게 표현할 수 있다. 반면 실수는 불가능하다. 실수를 다루게 되면 무한을 표현할 수 있어야 하는데 불가능하다. 따라서 적절히 비슷한 값을 사용하는 것으로 만족해야 한다. 컴퓨터의 모든 실수 변수는 정확도가 제한된 근사 값을 저장한다. 근사 값으로 연산한 결과는 수학적으로 정확하지 않을 수 있기 때문에 실수는 훨씬 다루기 까다롭다.

1. IEEE 754 표준
   가장 많은 컴퓨터/컴파일러들에서 사용되는 실수 표기 방식이다.
   • 이진수로 실수를 표기
   • 부동 소수점(floating-point) 표기법
   • 무한대, 비정규 수(subnormal number), NaN(Not a Number)등의 특수한 값이 존재

IEEE 754는 실수 연산에 관한 규정, 오버플로와 언더플로의 처리, 반올림에 관한 규정 등을 모두 포함하는 방대한 표준이다.

2. 실수의 이진법 표기

3. 부동 소수점 표기
   32 비트 변수 중 첫 16비트는 정수부, 뒤 16비트는 소수부로 쓰는 식으로 실수를 표기
   실수 변수는 다음과 같은 3가지의 정보를 저장하게 된다.

   • 부호 비트(sign bit)
     양수 인지 음수인지 여부
   • 지수(exponent)
     소수점을 몇 칸 옮겼나?
   • 가수(mantissa)
     소수점을 옮긴 실수의 최상위 X 비트

정확도에 큰 의미가 없는 경우를 제외하면 32비트형은 아예 쓰지말고 64비트 실수형 이상을 쓰는 것이 좋다.
이렇게 소수점을 움직이는 실수 표기법을 소수점이 둥둥 떠다닐 수 있다는 의미에서 부동 소수점 표기 방식이라고 한다.

실수 비교하기

두 실수 값이 같은지를 비교할 때는 항상 어느 정도의 오차를 염두에 두어야 한다. 구체적으로는 두 값의 매우 차이가 매우 작은 경우 두 값이 같다고 판단해야 한다. 두 수가 같은지 비교하는 함수를 다음과 같이 구현할 수 있다.

bool absoluteEqual(double a, double b) {
	return (fabs(a - b) < 1e-10);
}

위에서 fabs()는 주어진 실수의 절대 값을 구해준다.
위의 코드처럼 미리 정해둔 오차를 가지고 같은지를 판단한다. 하지만 실수 연산결과의 오차가 이것보다 큰 경우가 있을 수 있다. 이런 경우 문제를 해결하기 위해 크게 두 가지 방법을 쓸 수 있다.

1. 비교할 실수의 크기들에 비례한 오차 한도를 정한다.
   많은 경우 우리는 코드가 다루는 값의 범위를 예측할 수 있다. 실제 입력으로 들어올 최대 값과 최소 값을 대략 예측할 수 있고, 이들이 크게 차이 나지 않는 경우에는 하나의 오차 한도 값을 사용할 수 있다.
   오차 한도 값을 정할 때는 신중해야 하고 다음과 같이 경우를 나눠서 오차 한도 값을 정할 수 있다.
   • 같다고 판단해야 할 큰 값 두개를 비교할 경우
     a 와 b 라는 수가 있을 떄 오차 한도 값은 항상 |a - b|보다 커야 한다.
   • 다르게 판단해야 하는 작은 값 두개를 비교할 경우
     a 와 b 라는 수가 있을 떄 오차 한도 값은 항상 |a - b|보다 작아야 한다.
2. 상대 오차를 이용한다.
   문제의 입력으로 한 자리가 주어질지 서른 자리가 주어질지 알 수 없을 때는 오차 한도를 미리 정할 수 없다. 이런 경우에는 비교하는 숫자들의 크기에 비례하여 오차를 정하는 방식을 사용한다. 두 숫자의 크기에 비해 그 차이가 작다면 두 수가 같다고 판정하는 방식이다.
   relativeError(a, b) = (|a - b|) / (max(|a|, |b|));
   이 방법은 큰 수를 비교할 때는 별 문제가 없지만 매우 작은 숫자들을 비교하려 할 때는 문제가 될 수 있다. 이런 문제를 해결 하기 위해, 두 수의 절대 차이가 매우 작을 경우에 두 수가 같다고 판단할 필요가 있다.

대소 비교

두 수가 같은지를 판단하는 것이 아니라 대소를 판단할 때도 연산 오차가 발목을 잡을 수 있다. a = b가 되어야 할 두 수의 계산에서, 오차 때문에 a가 약간 더 작은 값으로 계산되었다고 해보자. 그러면 a < b는 원래 거짓이어야 했는데 참이 된다. 반대로 a에 약간 큰 값이 얻어졌을 경우 a<=b는 참 대신 거짓을 반환하게 된다. 이 문제를 피하려면 비교할 때 항상 두 값이 같은 경우, 다시 말해 두 값이 아주 가까운 경우를 먼저 확인하고 처리해 주어야 한다.

정확한 사칙연산

유리수의 경우 실수 변수를 사용하는 대신 분자와 분모를 각각 관리하는 유리수 클래스를 만들어서 정확한 사칙연산을 할 수도 있다.

코드의 수치적 안정성 파악하기

어떤 프로그램이 수치적으로 안정적(numerically stable)이라는 말은 프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않는다는 말이다. 프로그램의 실행 중 한 연산 결과와 정확한 값이 0.000000001만큼 차이났는데, 프로그램이 모두 실행된 뒤 마지막 결과는 정답과 17293만큼 차이가 난다면 이 프로그램은 아주 작은 오차를 부풀린 셈이고 이를 수치적으로 불안정하다고 말한다. 수치적으로 안정적인 프로그램에서는 중간에 작은 연산 오차가 난다고 해도 최종 답은 아주 작은 오차만을 갖게 된다.

실수 연산 아예 하지 않기

실수 연산은 제대로 하기 어렵다. 때문에 실수 연산을 제대로 하는 가장 좋은 방법은 아예 실수 연산을 하지 않는 것이다. 의외로 많은 경우, 얼핏 봐서는 실수 연산을 써야만 할 것 같은 문제들에 적절한 변형을 가해 실수 연산을 없앨 수 있다.

• 곱셈과 나눗셈의 순서를 바꾸기

• 양변 제곱하기

• 실수 좌표를 써야 하는 기하문제에서 좌표계를 가로 세로로 정수배 늘리면 정수만을 이용해 문제를 풀 수도 있다.

출처

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략