큰 정수의 계산

  • 특정 컴퓨터/언어가 표현할 수 없는 큰 정수의 산술 연산은 어떻게 할까?
  • int값은 대부분 32bit (부호값 1bit + 31bit) 이므로 -2^32^ ~ 2^31^-1까지만 표현 가능
  • 가정: 10진수 체계에서의 덧셈과 곱셈
  • 10진수를 소프트웨어적으로 표현하는 법 : 리스트를 이용하여 각 자리수를 하나의 원소로 저장 (예: 567,832: S = [2,3,8,7,6,5])
    :point_right: 참고 자바스크립트가 숫자를 다루는 법
    • 자바스크립트에는 number라는 하나의 숫자형만 존재하며 이는 64비트 2진 부동소수점 타입
    • 1개의 부호비트와 11비트의 지수, 53비트의 유효 숫자로 구성됨
    • Number.MAX_SAFE_INTEGER = 9007199254740991
    • 예로 숫자 9000000000000000000 는 ["+", 8650752, 7098594, 31974]로 표현된다

큰 정수의 덧셈

  • n개의 자릿수 각각을 더하면서 올림수(carry)를 고려

파이썬으로 정수 더하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def ladd (u, v):
    n = len(u) if (len(u) > len(v)) else len(v) 
    # 파이썬에서 타 언어의 삼항연산자 처럼 쓰는 법
    # (u.length > v.length) ? n = u.length : n = v.length; 같은 것
    result = []
    carry = 0
    for k in range(n):
        i = u[k] if(k < len(u)) else 0
        j = v[k] if(k < len(v)) else 0
        value = i + j + carry
        carry = value // 10
        result.append(value % 10)
    if (carry > 0):
        result.append(carry)
    return result

자바스크립트로 정수 더하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const add = (a, b) => {
    let n = 0;
    (a.length > b.length) ? n = a.length : n = b.length;
    let result = [];
    let carry  = 0;
    for (let k = 0; k < n; k++) {
        let i = 0, j = 0
        
        if (k < a.length) i = a[k]
        else              i = 0;
        if (k < b.length) j = b[k]
        else              j = 0;

        let value = i + j + carry;
        carry = Math.floor(value / 10)
        result.push(value % 10)
    }
    if (carry > 0) result.push(carry);
    return Number(result.reverse().join(''))
}

큰 정수의 곱셈

  • Brute-Force 방법 : O(n^2^)
  • Divide-and-Conquer
    • u (n자리) = *x * 10^m^* (n/2자리) + y (n/2자리)
    • uv = (x * 10^m^** + y)(**w * 10^m^ + z)
      → uv = xw * 10^2m^ + (xy + yw) * 10^m^ + yz

파이썬으로 정수 곱하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def prod(u, v):
    n = len(u) if (len(u) > len(v)) else len(v) 
    if (len(u) == 0 or len(v) == 0):
        return [0]
    elif (n <= threshold):
        return lmult(u, v)
    else:
        m = n // 2
        # divide
        x = div(u, m); y = rem(u, m)
        w = div(v, m); z = rem(v, m)
        # conquer
        p1 = prod(x, w) # xw
        p2 = ladd(prod(x, z), prod(w, y)) # (xy + yw)
        p3 = prod(y, z) # yz
        return ladd(ladd(exp(p1, 2*m), exp(p2, m)), p3)

def exp(u, m):
    if(u == [0]):
        return [0]
    else:
        return ([0] * m) + u
         # 배열의 합은 두 배열을 단순히 합하는 것
         # ex) [0, 0, 0] + [5, 6, 7] = [0, 0, 0, 5, 6, 7]

def div(u, m):
    if(len(u) < m):
        u.append(0)
    return u[m : len(u)]

def rem(u, m):
    if(len(u) < m):
        u.append(0)
    return u[0 : m]

def lmult (u, v):
    i = u[0] if (0 < len(u)) else 0
    j = v[0] if (0 < len(v)) else 0
    value = i * j
    carry = value // 10
    result = []
    result.append(value % 10)
    if(carry > 0):
        result.append(carry)
    return result

곱셈 개선

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def prod2(u, v):
    n = len(u) if (len(u) > len(v)) else len(v) 
    if (len(u) == 0 or len(v) == 0):
        return [0]
    elif (n <= threshold):
        return lmult(u, v)
    else:
        m = n // 2
    
        x = div(u, m); y = rem(u, m)
        w = div(v, m); z = rem(v, m)

        # 이 부분이 바뀜
        r = prod2(ladd(x, y), ladd(w, z))
        
        p1 = prod2(x, w) # xw
        p3 = prod2(y, z) # yz

         # 이 부분이 바뀜
        p2 = lsub(r, ladd(p1, p3)) # (xy + yw)
        return ladd(ladd(exp(p1, 2*m), exp(p2, m)), p3)

def lsub (u, v):
    n = len(u) if (len(u) > len(v)) else len(v)
    result = []
    borrow = 0
    for k in range(n):
        i = u[k] if (k < len(u)) else 0
        j = v[k] if (k < len(v)) else 0
        value = i - j + borrow
        if (value < 0):
            value += 10
            borrow = -1
        else:
            borrow = 0
        result.apeend(value % 10)
    if(borrow < 0):
        print("음의 정수는 처리할 수 없음")
    return result

# 나머지 함수는 동일