근사한 나눗셈

Abstract

컴파일러 최적화는 프로그램의 의미를 유지하면서 비싼 연산을 더 저렴한 연산으로 바꾸는 과정이다. 근사한 나눗셈(magic number division)¹은 상수 나눗셈을 곱셈과 비트 옮기기로 대체하는 최적화다. 본 글은 근사한 나눗셈의 원리를 소개한다.

본문

인간과 마찬가지로, 기계에게도 덧셈보다 곱셈이 어렵고 곱셈보다 나눗셈이 어렵다. CPU 관점에서 나눗셈은 덧셈, 곱셈, 비트 옮기기(bit shift)에 비해 수십 배가량 무거운 연산이다. 따라서 컴파일러가 나눗셈을 더 저렴한 연산들로 대체하려는 것은 자연스러운 선택이다.

근사한 나눗셈은 상수로 나누는 연산을 더 저렴한 곱셈과 비트 옮기기로 바꾸는 컴파일러 최적화 기법이다. 다시 말해, $N$비트 부호 없는 정수 $x$에 대하여 $$ \left\lfloor \frac{x}{C} \right\rfloor =\left\lfloor \frac{x \times m}{2^{N+s}} \right\rfloor $$ 가 성립하도록 하는 $m$과 $s$를 찾는 것이다. 여기서 $m$이 근사한 상수(magic number)이고, $s$는 추가로 옮길 비트의 양이다. $m$은 어림잡아 $\frac{2^{N+s}}{C}$를 올림한 값이므로 작은 오차를 포함한다. 이 오차가 모든 입력에서 몫을 바꾸지 않을 만큼 작도록 $s$를 정하면, 모든 $N$비트 부호 없는 정수에 대해 최적화가 성립한다. 부호 있는 정수의 경우에도 약간의 보정을 추가하면 같은 논리를 통해 정확한 결과를 얻을 수 있다.

근사한 나눗셈은 컴파일러 최적화의 섬세함을 잘 보여준다. 나눗셈을 곱셈과 비트 옮기기로 바꾸는 아이디어는 단순하지만, 모든 입력에서 같은 결과를 보장하려면 정교한 산술 조건이 필요하다. 꼬마 최적화 하나에도 프로그램의 의미를 보존하기 위한 수학적 보장이 필요하다.