Modulo 연산이란 우리가 흔히 아는 나머지 연산을 의미합니다. Modulo 연산에는 여러 특기할만한 특성이 있어 프로그래밍 영역에서 자주 사용됩니다.
그리고 프로그래밍 영역에서 자주 사용 되는 용어가 있는데, 바로 이 글에서 말씀드릴 Modulo reduction입니다.
다음 코드를 보겠습니다.
A = B % N A에 B를 N으로 나눈 나머지를 대입한다는 간단한 코드입니다. 결과적으로 B는 원래의 값에서 작아(reduction)지게 됩니다.
이러한 형태의 코드는 여러 곳에서 사용됩니다. 대표적으로는 C언어의, unsigned의 wrap around 같은 것이 있습니다.
문제
Modulo 연산의 대표적인 문제는 나눗셈과 같은 다른 연산의 고질적인 문제와 같습니다. 성능 저하가 발생한다는 것입니다.
64x CPU에서 나눗셈 연산을 할 때 매 명령에 6사이클 연산 시간과 26 사이클 지연 시간이 생기는데, 이에 반해 곱셈 연산을 할 때는 매 명령에 한 사이클 연산 시간, 3 사이클 지연 시간이 생기게 됩니다.
해결책
이러한 문제를 해결하기 위한 해결책에는 강력한 트릭이 있습니다. Precompute, 전처리라는 트릭입니다.
그리고 이러한 트릭을 컴파일러들은 사용하고 있습니다. N이 컴파일 시간에 알 수 있을 경우 컴파일러는 해당 명령을 최적화합니다.
그리고 또 다른 방법도 있습니다. N이 2의 거듭제곱일 경우, B % N와 B & (N - 1)은 같습니다. B의 하위 비트들에 1로 채워진 비트마스크를 사용하는 것과 다르지 않죠.
다만 이 방법은 2의 제곱에만 적용할 수 있다는 제한이 있습니다.
이게 한계일까요? 무언가 조금 더 나은 방법이 있지 않을까요?
다행히도 더 나은 방법이 있습니다. Modulo 연산을 곱셈 연산으로 바꾸어 버리는 것입니다.
다음 C언어 코드를 보겠습니다.
uint32_t reduce(uint32_t b, uint32_t n) {
return ((uint64_t)b * (uint64_t)n) >> 32;
} 보시다시피 이 코드는 32비트의 unsigned int b와 n을 받아 곱한 뒤, 2의 32제곱으로 나누어 리턴합니다.
이 간단한 코드는 이전에 비해 몇 배나 빠릅니다.
만약 다른 형태의 128비트를 지원하는 환경에 있다면 32비트를 64비트로 진급시킬 수도 있습니다.
