[Algorithm] Karatsuba algorithm

큰 수를 곱해야 하는 상황에서 카라추바 알고리즘이 최적화에 많이 이용 된다고 하여...

문제풀이에 필요할 것 같아 정리해 둔다.

 

아래는 위키에 적혀있는 내용이다.

 

---

인터넷에 보면 예시가 많은데...  나도 이해를 해야하니 하나의 예시를 적어보려 한다.

 

예를들어, 1234 * 4321 을 곱해야 하는 상황이라 하면 아래와 같이 풀어서 적을 수 있을 것이다.

 

1234 * 4321 을 구해야 한다.

 

1234 = 12 * 100 + 34

4321 = 43 * 100 + 21

 

이 수식을 다시 정리하면

(12 * 100 + 34 ) * ( 43 * 100 + 21 ) = 1234 * 4321

= ( 12 * 43 ) * 10000 + ( 12 * 21 * 34 * 43 ) * 100 + 34 * 21 * 1

 

여기서 10의 거듭제곱 앞의 계수들을 z0, z1, z2 로 놓으면,

z0 = 12 * 43

z1 = 12 * 21 + 34 * 43

z2 = 32 * 21 

 

그리고 z1을 아래와 같이 쓰면 ... z1 의 계산을 3번의 곱으로 구할 수 있다.

( z0 에서 한번, z2에서 한번, z1 에서 한번 )

 

z1 = ( 12 * 34 ) * ( 21 * 43 ) - z0 - z2

 

알고리즘 상에서 구현하면, z0 과 z2를 계산 한 뒤, z1을 구하면 z1의 곱셈을 줄일 수 있으며,

이를 전부 더하면,  곱셈 결과를 얻을 수 있게 된다.

 

코드는 나중에 구현해 볼 예정이다.