분할정복 (1) 썸네일형 리스트형 [분할정복/카라츠바 알고리즘] 곱셈 최적화! 카라츠바 알고리즘에 대해 알아보자 기본 단계 카라추바 알고리즘의 기본 단계는 큰 두 수 x와 y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다. x와 y를 B진법의 n자리수라고 하자. n보다 작은 양수 m에 대해 다음과 같이 x, y를 쪼갤 수 있다. x = x1Bm + x0 y = y1Bm + y0 (단, x0과 y0는 Bm보다 작다.) z2 = x1y1 z1 = x1y0 + x0y1 z0 = x0y0 라고 할 때, x와 y의 곱은 xy = (x1Bm + x0)(y1Bm + y0) = z2 B2m + z1 Bm + z0 이 식은 4번의 곱셈을 해야한다. 카라추바는 덧셈을 몇 번 함으로써, xy를 3번의 곱셈을 통해 구할 수 있다는 걸 알았다. z2 = x1y1 라 하자. z0 = x0y.. 이전 1 다음