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