메아리 저널

잡학에 대한 글을 올릴 요량으로 "잡학다식" 카테고리를 만들었다. (지금까지 카테고리 없이 살아 왔는데... 왠지 올릴 글이 많아질 것 같아서.) 요로시쿠 오네가이시마스. 가 아니라...

residue number system, 줄여서 RNS는 일종의 수 체계이다. 한국어로는 "나머지 수 체계" 정도라고 번역하면 될 것 같다.

RNS의 parameter는 서로 소인 숫자 \{m_1, \cdots, m_n\}이다. 그리고 숫자 N은 \{N \mod m_1, \cdots, N \mod m_n\}으로 나타낸다. 이런 식으로 나타낸 숫자는 0 \le N \le \mathop{lcm}(m_1,\cdots,m_n) = M 범위의 숫자 N을 유일한 표현으로 나타낼 수 있고, RNS 표현이 이 범위의 숫자와 1:1 대응된다. ( m_k들이 서로 소일 필요는 없지만, 이 경우 한 숫자에 대응하는 표현이 여러 개 생길 수 있다.)

같은 parameter를 가지고 있을 경우 두 숫자 A와 B 사이의 사칙연산은 비교적 간단하게 이루어진다. (정확히는, 사칙연산의 맨 마지막 "나눗셈"은 modulo M 하에서 행해지는 연산이다.) 그냥 각 숫자들을 사칙연산한 뒤 결과를 modulo m_k 하여 나머지만 취하면 된다. 쉬운 예로 {2,3,5}-RNS에서 7과 11을 곱한다고 하면, 7은 \{1,1,2\}고 11은 \{1,2,1\}이므로 둘의 원소를 각각 곱하면 \{1,2,2\}가 된다. 여기에 대응하는 숫자는 (7 \times 11) \mod (2 \times 3 \times 5) = 17이어야 하는데, 17은 {2,3,5}-RNS에서 \{1,2,2\}가 되는 걸 쉽게 확인할 수 있겠다.

실제로 \{1,2,2\}라는 결과가 나왔을 때 17을 얻는 방법은 m_k가 서로 소가 아니면 복잡할 수 있다. 하지만 서로 소인 m_k를 가정하면 생각보다 쉽게 해당하는 결과를 얻을 수 있다: 1 + 2 m_1 + 2 m_1 m_2 식으로 계산하면 된다. 이 경우 1 + 2 \cdot 2 + 2 \cdot 2 \cdot 3 = 1 + 4 + 12 = 17이 된다. 이건 {2,3,5}-RNS가 아니라 {2,5,3}-RNS처럼 순서가 바뀌어도 같은 결과가 나온다.

RNS는 이런 저런 곳에서 쓸모가 있다. 예를 들어 modulo M에 대해 곱셈과 나눗셈을 밥먹듯이 해야 하고 최종적인 변환을 맨 마지막에 해야 하는 경우, M이 크다면 여기에 해당하는 RNS를 만들어서(사실은 이 과정이 쉽지 않기 때문에 일반적인 방법은 아니다만) 연산을 쪼갤 수 있다. 특히 연산을 쪼개고 나면 각 원소들은 서로 다른 곳에서 계산한 뒤 최종적으로 합치기만 하면 되기 때문에 병렬화가 무지막지하게 쉬워진다. 요즘 없어서 못 쓰는(?) 게 병렬 처리 루틴인데 괜찮은 방법이라 할 수 있겠다.

RNS를 좀 더 엽기적으로 사용하는 방법으로는 일면 보기에 전혀 상관이 없어 보이는 case로 이루어진 switch 문을 최적화하는 데 있다. RNS의 m_k들을 잘 선택하면 해당 case들을 몇 개의 condition으로 바꿀 수 있고, default가 없다고 가정하면 편리하게 don't care를 구현할 수도 있다. 물론 대부분의 아키텍처에서 나눗셈은 매우 비싼 연산이기 때문에 이걸 일반적으로 적용하긴 힘들지만, 가끔씩 나눗셈을 효율적으로 구현해 놓은 프로세서도 있고 코드를 줄이려는(?????) 목적으로 사용하는 광경도 한 번 본 적이 있다.

뭐 그렇다고. 알아 둬서 나쁜 건 없다.