[빠른 곱셈] 카라츠바 알고리즘

N 자리 수의 곱셈은 보통 O(N^2) 으로 표현이 된다.

카라츠바 알고리즘 을 통해 구현한다면 N^log3 으로 조금더 빠르게 구현 할 수 있다.





x와 y를 B진법 N자리수라고 가정 할때

X  = x1 B^m + x0

Y  = y1 B^m + y0

로 표현 할 수 있다.

XY = (x1 B^m + x0) (y1 B^m + y0 )

로 4번의 계산을 통해야 하지만 카라츠바의 방법은 3번의 곱셈을 사용한다.


z0 = x0 * y0
z1 = (x1+x0) (y1+y0) - z2 - z0
z2 = x1 * y1


z2 * B^2M + z1 * B^M + z0 로 나타 낸다.


예시는 위키에 자세히 나와 있다.


참고 사이트

https://en.wikipedia.org/wiki/Karatsuba_algorithm

https://jmk.pe.kr/read/karatsuba-fast-integer-multiplication