카라추바 알고리즘 10만자리 곱하기 10만자리같은 곱셈은 애시당초 자료형으로 표현할 수도 없고, 문자열로 바꾸어 하나하나 곱하면 $O(N^2)$의 복잡도를 갖게 된다. 이때 등장하는 것이 카라추바 알고리즘. 시간복잡도를 $O(N^{log3})$으로 줄여준다. 그 방법을 한번 살펴보자. 일단 256자리의 두 정수 a, b를 곱한다고 생각해볼때 a와 b를 다음과 같이 나눈다. $a = a_1\times10^{128}+a_0​$ $b = b_1\times10^{128}+b_0​$ a1,b1은 각각 a,b의 첫 128자리, a0,b0는 각각 a,b의 뒷 128자리를 나타낸다. 그럼 이제 a * b의 계산 과정은 다음과 같이 나타낼 수 있다. $a\times b = (a_1 \times b_1) \times 10..