카라츠바 (Karatsuba) - Python

Program Lang./Algorithm 2023. 2. 19. 18:47

1. 카라츠바 알고리즘

 

다른 사람 C++ 코드를 보고 phython으로 옮겨 봤다.

알고리즘의 Insight는 아래 유투브 강의에 잘 나와 있다.

https://www.youtube.com/watch?v=7JvRFnxn3W0

 

?
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
def normalize(a):
    a.append(0)
    for i in range(len(a)-1):
        if a[i] < 0:
            borrow = (abs(a[i]) + 9) // 10
            a[i+1] -= borrow
            a[i] += borrow*10
        else:
            a[i+1] += (a[i] // 10)
            a[i] %= 10
     
    while len(a) > 1 and a[-1] == 0:
        a.pop()
 
def multiply(a, b):
    length = len(a) + len(b) + 1
    c = [0] * length
     
    for i in range(len(a)):
        for j in range(len(b)):
            c[i+j] += (a[i] * b[j])
     
    normalize(c)
    return c
 
def addTo(a, b, k):
    newLength = max(len(a)+1, len(b)+k)
    #a = a + [0]*(newLength - len(a))
    zeroFillNum = newLength - len(a)
    while zeroFillNum > 0:
        a.append(0)
        zeroFillNum -= 1
 
    for i in range(len(b)):
        a[i+k] += b[i]
 
    normalize(a)
 
def subFrom(a, b):
    newLength = max(len(a)+1, len(b)) +1
    zeroFillNum = newLength - len(a)
    while zeroFillNum > 0:
        a.append(0)
        zeroFillNum -= 1
 
    for i in range(len(b)):
        a[i] -= b[i]
 
    normalize(a)   
 
def karatsuba(a, b):
    if len(a) < len(b):
        return karatsuba(b, a)
     
    if len(a) == 0 or len(b) == 0:
        return []
     
    if len(a) < 2:
        return multiply(a, b)
     
    half = len(a) // 2
     
    a0 = a[:half]
    a1 = a[half:]
    b0 = b[:min(len(b), half)]
    b1 = b[min(len(b), half):]
     
    # z2= a1*b1
    z2 = karatsuba(a1, b1)
 
    # z0= a0*b0
    z0 = karatsuba(a0, b0)
     
    # a0 = a0 + a1
    # b0 = b0 + b1
    addTo(a0, a1, 0)
    addTo(b0, b1, 0)
     
    #z1 = (a0+a1)*(b0+b1)-z0-z2
    z1 = karatsuba(a0, b0)
    subFrom(z1, z0)
    subFrom(z1, z2)
     
    result = []
    addTo(result, z0, 0)
    addTo(result, z1, half)
    addTo(result, z2, half+half)
     
    return result
     
 
if __name__ == '__main__':
    #a = [8, 2, 7]
    #b = [4, 4]
 
    a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    b = [9, 8, 6, 5, 4, 3]
         
    result = karatsuba(a[::-1], b[::-1])
    #print(827*44)
    print(123456789*986543)
    print(result)

 

2. 팬미팅 소스

 

https://www.algospot.com/judge/problem/read/FANMEETING

Normalize 코드를 빼주고, fan의 순서를 뒤집어 주는 것이 원본 카라츠바 알고리즘과 차이점

 

?
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
def multiply(a, b):
    length = len(a) + len(b) + 1
    c = [0] * length
     
    for i in range(len(a)):
        for j in range(len(b)):
            c[i+j] += (a[i] * b[j])
     
    return c
 
def addTo(a, b, k):
    newLength = max(len(a)+1, len(b)+k)
    zeroFillNum = newLength - len(a)
    while zeroFillNum > 0:
        a.append(0)
        zeroFillNum -= 1
 
    for i in range(len(b)):
        a[i+k] += b[i]
 
 
def subFrom(a, b):
    newLength = max(len(a)+1, len(b)) +1
    zeroFillNum = newLength - len(a)
    while zeroFillNum > 0:
        a.append(0)
        zeroFillNum -= 1
 
    for i in range(len(b)):
        a[i] -= b[i]
 
def karatsuba(a, b):
    if len(a) < len(b):
        return karatsuba(b, a)
     
    if len(a) == 0 or len(b) == 0:
        return []
     
    if len(a) <= 2:
        return multiply(a, b)
     
    half = len(a) // 2
     
    a0 = a[:half]
    a1 = a[half:]
    b0 = b[:min(len(b), half)]
    b1 = b[min(len(b), half):]
     
    # z2= a1*b1
    z2 = karatsuba(a1, b1)
 
    # z0= a0*b0
    z0 = karatsuba(a0, b0)
     
    # a0 = a0 + a1
    # b0 = b0 + b1
    addTo(a0, a1, 0)
    addTo(b0, b1, 0)
     
    #z1 = (a0+a1)*(b0+b1)-z0-z2
    z1 = karatsuba(a0, b0)
    subFrom(z1, z0)
    subFrom(z1, z2)
     
    result = []
    addTo(result, z0, 0)
    addTo(result, z1, half)
    addTo(result, z2, half+half)
     
    return result
 
def hugs(a, b):
    N = max(len(a), len(b))
    M = min(len(a), len(b))
    inta = [1 if v == 'M' else 0 for v in a]
    intb = [1 if v == 'M' else 0 for v in b]
    intb.reverse()
     
    C = karatsuba(inta[::-1], intb[::-1])
    allHugs = 0
     
    for i in range(M-1, N):
        if C[i] == 0:
            allHugs += 1
 
    return allHugs
 
if __name__ == '__main__':
    members = ['FFFMMM', 'FFFFF', 'FFFFM', 'MFMFMFFFMMMFMF']
    fans = ['MMMFFF', 'FFFFFFFFFF', 'FFFFFMMMMF', 'MMFFFFFMFFFMFFFFFFMFFFMFFFFMFMMFFFFFFF']
     
    for i in range(len(members)):
        result = hugs(members[i], fans[i])
        print(result)

'Program Lang. > Algorithm' 카테고리의 다른 글

다익스트라(Dijkstra) 알고리즘 - 힙사용하지 않을 경우  (0) 2017.11.23
최소 신장 트리 - 프림(Prim) 알고리즘  (0) 2017.11.20
위상정렬 (Topological Sort) - Indegree  (0) 2017.11.06
1로 만들기  (0) 2017.10.26
계단오르기  (0) 2017.10.25
:
◀ PREV : [1] : [2] : [3] : [4] : [···] : [150] : NEXT ▶

티스토리툴바