[Discrete Mathematics] 정수 표현 및 알고리즘

---

정수 표현

 

흔히 정수를 십진법으로 표현한다. 이는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 를 사용하여 정수를 표현하는 방법으로 기호의 위치에 따라 10의 n 제곱을 곱한다. 예를 들어 $ 179 = 1 \times 10^2 + 7 \times 10^1 + 9 \times 10^0 $ 와 같이 나타내는 것이다.

수를 나타내는 진법이 근거로 하는 수, 즉 십진법의 십과 같은 수를 그 진법의 기수(base)라 한다.

이진법(binary number system)에서 정수를 표현할 때는 0 과 1 만이 필요하다. 예를 들어 $ 101101_2 = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 $ 이다. 비트(bit)는 이진수(binary digit)로 0 또는 1 을 나타낸다. 즉 이진법은 비트로 나타낼 수 있다.

십육진법(hexadecimal number system)은 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F 를 사용하고, 팔진법(octal number system)dms 0, 1, 2, 3, 4, 5, 6, 7 을 사용한다. 운영체제에서 가상 주소의 크기를 나타낼 때 십육진법을 자주 사용한다.

컴퓨터에서는 이진법으로 정수를 표현하는데 양의 정수 $ n $ 을 표기하기 위해 필요한 비트의 수는 $ \lfloor 1 + \lg n \rfloor $ 이다.

양의 정수 $ n $ 을 $ k $ 비트로 표현할 수 있다 가정하자. 즉 $ n = 1 \times 2^{k-1} + b_{k-2} 2^{k-2} + \cdots + b_0 2^0 $ 이다.

$ 2^{k-1} \leq n $ 이고 $ n \leq 1 \times 2^{k-1} + 1 \times 2^{k-2} + \cdots + 1 \times 2^0 = 2^k - 1 < 2^k $ 이다.

즉 $ 2^{k-1} \leq n < 2^k $ 에서 $ \lg $ 를 취하여 $ k-1 \leq \lg n < k $ 이고, 이는 다시 $ k \leq 1 + \lg n < k + 1 $ 이므로 $ k = \lfloor 1 + \lg n \rfloor $ 이다.

 

---

여러가지 정수 알고리즘

 

• 다른 진법의 수를 십진수로 변환

입력 : $ c $ (각 자리의 계수), $ n $ (자릿수), $ b $ (기수)
출력 : $ decimal $ (십진수로 변환된 수)

base_b_to_dec(c, n, b) {
    decimal = 0
    b_to_i = 1
    for i = 0 to n {
        decimal = decimal + c[i] * b_to_i
        b_to_i = b_to_i * b
    }
    return decimal
}

 

• 십진수를 다른 진법으로 변환

입력 : $ m $ (변환하려는 정수), $ b $ (기수)
출력 : $ c $ (각 자리의 계수), $ n $ (자릿수)

dec_to_base_b (m, b, c, n) {
    n = -1
    while (m > 0) {
        n = n + 1
        c[n] = m mod b
        m = floor(m / b)
    }
}

 

• 거듭제곱에 의한 누승수 계산

입력 : $ a $ (밑), $ n $ (지수)
출력 : $ a^n $ (계산 값)

exp_via_repeated_squaring(a, n) {
    result = 1
    x = a
    while (n > 0) {
        if (n mod 2 == 1) {
            result = result * x
        }
        x = x * x
        n = floor(n / 2)
    }
    return result
}

지수만큼 밑을 곱하는 것보다 연산 수가 더 적다. 즉 시간복잡도 측면에서 유리하다.

 

• 거듭제곱에 의한 누승수의 $ \bmod $ 계산

$ a $, $ b $, $ z $ 를 양의 정수라 하면 $ ab \bmod z = \left[ (a \bmod z)(b \bmod z) \right] \bmod z $ 이다.

$ w = ab \bmod z , \quad x = a \bmod z, \quad y = b \bmod z $ 라 하면 $ w $ 는 $ ab $ 를 $ z $ 로 나눌 때의 나머지이므로 몫-나머지 정리에 의해 $ ab = q_1 z + w $ 를 만족하는 $ q_1 $ 이 존재한다. 따라서 $ w = ab - q_1 z $ 이다.

즉 $ a = q_2 z + x $ 이고 $ b = q_3 z + y $ 를 만족하는 정수 $ q_2 $, $ q_3 $ 역시 존재한다.

$ w = ab - q_1 z = (q_2 z + x) (q_3 z + y) - q_1 z = qz + xy $ 이고, 여기서 $ q = q_2 q_3 z + q_2 y + q_3 x - q_1 $ 이다.

따라서 $ xy = -qz + w $ 이고, 그러므로 $ w = xy \bmod z $ 이다.

이를 통해서 큰 수, 특히 큰수의 거듭제곱에 대한 나머지 연산을 효율적으로 할 수 있다.

예를 들어 $ 572^{29} \bmod 713 $ 을 계산해보면 다음과 같다.

$ 572^2 \bmod 713 = (572 \bmod 713)(572 \bmod 713) \bmod 713 = (572 \cdot 572) \bmod 713 = 630 $

$ 572^4 \bmod 713 = (572^2 \bmod 713)(572^2 \bmod 713) \bmod 713 = (630 \cdot 630) \bmod 713 = 472 $

$ 572^8 \bmod 713 = (572^4 \bmod 713)(572^4 \bmod 713) \bmod 713 = (472 \cdot 472) \bmod 713 = 328 $

$ 572^{16} \bmod 713 = (572^8 \bmod 713)(572^8 \bmod 713) \bmod 713 = (328 \cdot 328) \bmod 713 = 634 $

$ 572^5 \bmod 713 = (572 \bmod 713)(572^4 \bmod 713) \bmod 713 = (572 \cdot 472) \bmod 713 = 470 $

$ 572^{13} \bmod 713 = (572^5 \bmod 713)(572^8 \bmod 713) \bmod 713 = (470 \cdot 328) \bmod 713 = 152 $

$ 572^{29} \bmod 713 = (572^{13} \bmod 713)(572^{16} \bmod 713) \bmod 713 = (152 \cdot 634) \bmod 713 = 113 $

이러한 연산은 $ 572^{29} $ 를 계산한 후에 $ \bmod $ 연산을 하는 것보다 효율적이고, 특히 PC 에서 계산할 때 큰 수에 대한 오버플로우 현상을 막는데 유용하다.

입력 : $ a $ (밑), $ n $ (지수), $ z $ (나누는 수)
출력 : $ a^n \bmod z $

exp_mod_z_via_repeated_squaring(a, n, z) {
    result = 1
    x = a mod z
    while (n > 0) {
        if (n mod 2 == 1) {
            result = (result * x) mod z
        }
        x = (x * x) mod z
        n = floor(n / 2)
    }
    return result
}