DAMPER's blog

알고리즘 문제해결전략 183p에 소개된 카라추바 곰셈 알고리즘입니다. 2N자리수인 a와 b를 다음과 같이 정의한다고 하자. $$a = a_{1} \times 10^{N}+a_{0}$$ $$ b = b_{1} \times 10^{N}+b_{0}$$ a x b 는 다음과 같이 표현할 수 있다. $$a \times b \\ = ( a_{1}\times 10^{N} +a_{0}) \times (b_{1} \times 10^{N} + b_{0}) \\ = a_{1} \times b_{1} \times 10^{2N} + (a_{1} \times b_{0} + a_{0} \times b_{1})\times10^{N}+a_{0}\times b_{0}$$ 그렇다면 계산을 위해 다음과 같이 곱셈을 기준으로 4가지 조각으로..