16. karatsuba algorithm [9 1주차]

16. Karatsuba Algorithm [9-1주차]

2024년 1월 14일 일요일

오전 1:44

<Karatsuba Algorithm>

큰 수를 빠르게 곱하는 알고리즘이다.

일반적으로 n자리 수 두 개를 곱하는 데 O(n²)이 걸린다.

그러나 곱 연산을 더 빠르게 할 수 있는 Karatsuba Algotithm이 존재한다.

b=10 -> 10진수

b진수 m자리 숫자 x, y를 곱하는 알고리즘.

두 수 x, y를 곱하기 전, 두 수 각각을 높은 자리의 숫자와 낮은 자리의 숫자로 분리한다.

그러면 아래 식이 성립한다.

-> 총 세번 재귀적으로 곱 연산을 호출하면 된다.

T(m) = 3T(m/2)

O(n^log3)

나누기 연산은 더욱 빠른 알고리즘이 개발되지 않았다. 그러나 곱하기 알고리즘은 Karatsuba알고리즘이 나온 이후 계속 더 빠른 알고리즘이 개발되고 있다.

이로 인해, 컴퓨터는 나누기보다 곱하기를 더 빠르게 연산한다.