#math 부호가 다른 두 수를 모듈로 연산(modulo operation)할 때, 결과 값 부호는?

모듈로 연산, modulo(modulus) operation?

나머지를 구하는 연산이다. 즉, \(a = n \times q + r\) 일 때, \(a \bmod n = r\) 이 된다.

퀴즈

bool is_odd(int n) {
    return n % 2 == 1;
}

제대로 구현한 걸까?

n이 양수일 때는 문제가 없어 보인다. 1,3,5,… 다 1이 나오니깐. 그럼 n이 음수면 어떻게 될까? 즉, \(-3\bmod2\) 는 -1일까? 1일까?

C++11에선 -1이다. 피제수(dividend) 부호를 따라간다. C+11에서 표준으로 정해졌기 때문에 C++98에서는 컴파일러 마음이다. 난 VS2008에서 테스트했는데, -1이 나오더라.

그래서 저 구현은 잘못됐다. n이 -1, -3, … 일 때, 모듈로 연산 값은 -1이 되고 false를 리턴한다.

bool is_odd(int n) {
    return n % 2 != 0;
}

모듈로 연산 값 부호가 n에 따라 결정되므로 n 부호를 보고 분기를 타서 결과를 계산하거나 0과 비교하면 된다.

truncated division, floored division

\(a = n \times q + r\) 에서 \(q\) 를 어떻게 구하느냐에 따라 부호가 피제수 혹은 제수(divisor)를 따라가게 된다.

truncated division은 \(q = trunc(a / n)\) 로 구한다. 즉, 버린다. \(q=trunc(-3/2)=-1\) 이 되고 계산하면 \(r = -1\) 이 된다. 음수일 때, 소수점 이하를 버려서 나머지가 없는 해(solution)보다 큰 정수가 몫(quotient)이 된다. 그래서 나머지는 음수가 된다. 결국, 모듈로 연산 값 부호는 피제수를 따라간다.

floored division은 \(q = \left\lfloor {a \over n} \right\rfloor\) 로 구한다. 버림과 다르게 내림이다. \(q=\left\lfloor {-3 \over 2} \right\rfloor = -2\) 가 되고 계산하면 \(r = 1\) 이 된다. truncated division과 다르게 해(solution)보다 더 작은 정수가 몫이 된다. 그래서 나머지는 양수. 결국, 부호는 제수를 따라간다. 참고로 Wolfram Alpha에서 이 방법을 사용.

이 두 방법 외에 나머지를 0 또는 양수로 만드는 Euclidean definition도 있다.

mod 정의를 봐야 한다.

\(\begin{array}{lcl} \gcd(a,0) = a\ \gcd(a,b) = \gcd(b, a \,\mathrm{mod}\, b) \ where\, a\mathrm{mod}\, b = a - b \left\lfloor {a \over b} \right\rfloor\end{array}\)

유클리드 호제법(Euclid’s algorithm)이다. floored division을 쓴다고 정의했다.

                                        ; clojure
(defn gcd [a b]
  (if (zero? a)
      b
    (recur (mod b a) a)))

그래 mod. 별 생각 없이 구현했다. 하지만 음수가 들어가니 나오는 gcd 값에 멘붕. 찾아보니 mod도 있고 rem도 있네. 그래 mod는 모듈로 연산. rem은 나머지를 구하는 연산. 엥? 둘이 갖지 않나? 뭐가 다른 거지? 아~ 두 가지 구현을 다 했고 그걸 구분하려고 이렇게 이름을 지었구나. mod는 피제수 부호를 따라가고 rem은 제수 부호를 따라간다. gcd를 구할 땐, floored division을 사용해야 하므로 rem을 사용해야 한다.

참고: Modulo operation - wikipedia