목표: 두 수를 빠르게 곱하는 방법
초등학교에서 긴 곱셈을 통해 두 숫자를 곱하는 방법을 배웠다. 먼저 이 방법을 시도해 보자!
5678
*1234
------
22712
17034-
11356--
5678---
--------
7006652
그렇다면 긴 곱셈법의 문제점은 무엇일까? 우리의 목표 중 첫 번째 부분을 기억해보자. 두 숫자를 빠르게 곱하는 것이다. 긴 곱셈법은 느리다! (O(n^2))
긴 곱셈법의 구현에서 **O(n^2)**이 어떻게 발생하는지 확인할 수 있다:
// 긴 곱셈법
func multiply(_ num1: Int, by num2: Int, base: Int = 10) -> Int {
let num1Array = String(num1).characters.reversed().map{ Int(String($0))! }
let num2Array = String(num2).characters.reversed().map{ Int(String($0))! }
var product = Array(repeating: 0, count: num1Array.count + num2Array.count)
for i in num1Array.indices {
var carry = 0
for j in num2Array.indices {
product[i + j] += carry + num1Array[i] * num2Array[j]
carry = product[i + j] / base
product[i + j] %= base
}
product[i + num2Array.count] += carry
}
return Int(product.reversed().map{ String($0) }.reduce("", +))!
}이중 for문이 문제의 원인이다! 각 자릿수를 비교하면서 (필요한 과정이지만) **O(n^2)**의 실행 시간을 가지게 된다. 따라서 긴 곱셈법이 최선의 알고리즘이 아닐 수 있다. 더 나은 방법이 있을까?
카라츠바 알고리즘은 아나톨리 카라츠바가 1962년 발견하고 발표했다. 카라츠바는 두 큰 수의 곱을 세 개의 작은 곱셈과 덧셈, 뺄셈으로 계산할 수 있다는 것을 발견했다.
두 수 x, y가 있고, m <= n일 때:
x = a*10^m + b
y = c*10^m + d
이제 다음과 같이 표현할 수 있다:
x*y = (a*10^m + b) * (c*10^m + d)
= a*c*10^(2m) + (a*d + b*c)*10^(m) + b*d
이 방법은 19세기부터 알려져 있었다. 문제는 이 방법이 4번의 곱셈(a*c, a*d, b*c, b*d)을 필요로 한다는 점이다. 카라츠바의 통찰은 단 3번의 곱셈(a*c, b*d, (a+b)*(c+d))만으로 충분하다는 것이었다. 이게 어떻게 가능한지 궁금할 것이다. 다음 수식을 보자:
(a+b)*(c+d) - a*c - b*d = (a*c + a*d + b*c + b*d) - a*c - b*d
= (a*d + b*c)
꽤 멋지지 않은가?
다음은 전체 구현이다. 재귀 알고리즘은 m = n/2일 때 가장 효율적이다.
// 카라츠바 곱셈
func karatsuba(_ num1: Int, by num2: Int) -> Int {
let num1String = String(num1)
let num2String = String(num2)
guard num1String.count > 1 && num2String.count > 1 else {
return multiply(num1, by: num2)
}
let n = max(num1String.count, num2String.count)
let nBy2 = n / 2
let a = num1 / 10^^nBy2
let b = num1 % 10^^nBy2
let c = num2 / 10^^nBy2
let d = num2 % 10^^nBy2
let ac = karatsuba(a, by: c)
let bd = karatsuba(b, by: d)
let adPlusbc = karatsuba(a+b, by: c+d) - ac - bd
let product = ac * 10^^(2 * nBy2) + adPlusbc * 10^^nBy2 + bd
return product
}이 알고리즘의 실행 시간은 어떻게 될까? 이 추가 작업이 가치가 있을까? 마스터 정리를 사용해 이 질문에 답할 수 있다. 이는 T(n) = 3*T(n/2) + c*n + d로 이어지며, 여기서 c와 d는 상수다. (3 > 2^1이므로) 실행 시간은 **O(n^log2(3))**이며, 이는 대략 **O(n^1.56)**이다. 훨씬 나은 결과다!
m = 2
x = 1234 = a*10^2 + b = 12*10^2 + 34
y = 5678 = c*10^2 + d = 56*10^2 + 78
a*c = 672
b*d = 2652
(a*d + b*c) = 2840
x*y = 672*10^4 + 2840*10^2 + 2652
= 6720000 + 284000 + 2652
= 7006652Swift Algorithm Club을 위해 Richard Ash가 작성함