[알고리즘] 카라추바의 빠른 곱셈(Karatsuba)

123 × 456 = ? 평소에 일상적으로 계산하던 방법을 분석적으로 풀어써보면 이렇다. 우리는 평소 한 자리에 0부터 9까지의 숫자만 사용하는 십진법을 사용하기 때문에, 각 자리별로 십의 자리 수는 다음 칸으로 넘겨준다(예를 들어 10의 자리 27은 (20 + 7)이므로 100의 자리로 2를 넘겨준다). (4 * 10000) + (13 * 1000) + (28 * 100) + (27 * 10) + (18 * 1) = (5 * 10000) + (6 * 1000) + (0 * 100) + (8 * 10) + (8 * 1) = 56088 최종적으로 값을 이렇게 계산해 낼 수있다. 456의 갯수만큼, 123의 각 원소(1, 2, 3)과 한 번씩 곱셈연산을 해야함을 알 수있다. 따라서 전통적인 방법으로는 만약 ..

2020.07.28