분할정복 - 카라츠바의 정수 빠른 알고리즘

카라츠바의 빠른 곱셈 알고리즘 두개의 정수를 단 두번의 곱셈을 이용해 빠른 곱셈 알고리즘 구현!!두개를 곱하는데 왜 곱셈이 두번이냐? 1 2 3 4x 5 6 7 8 ------------ 8 16 24 32.....각각 곱해서 더해야 값이 나온다근데 카라츠바는 아니다!알고리즘은 다음과 같습다128자리 숫자 A, B가 있다고 합시다.A = A1 X 10^128 + A0B = B1 X 10^128 + B0이걸 두개를 곱하면? A X B = (A1 X 10^128 + A0) X (B1 X 10^128 + B0)A1 x B1 x 10^256 + (A1 x B0 + A0 x B1 ) x 10^128 + A0 x B0이렇게 되니 결국 A1 x B1이랑 A1 x B0, A0 x B1, A0 x B0 이렇게 네개만 곱..

원문링크 : 분할정복 - 카라츠바의 정수 빠른 알고리즘