구구단 없어도 된다? ③ 카라추바의 큰 수 곱셈법

우리가 알고 있는 구구단이 곱셈법의 전부는 아니다. 과거 조상들은 저마다 독특한 곱셈법을 개발해서 사용했다. 어떤 것들이 있는지 알아보자!

글_장경아 기자일러스트_소슬랑

곱셈 알고리즘 등장

카라추바 알고리즘은 러시아의 수학자 아나톨리 알렉세예비치 카라추바가 1960년에 발견한 것으로, 컴퓨터에서 계산을 빠르게 하기 위해 고안된 알고리즘이다.

일반적으로 n자리 수 두 개를 곱하려면 한 자리 수의 곱셈을 n²번 해야 한다. 예를 들어 25×13을 하려면 5×3, 2×3, 5×1, 2×1과 같이 한 자리 수의 곱셈이 4번 필요하다.

그런데 카라추바 곱셈 알고리즘을 이용하면 한 자리 곱셈 횟수가 최대 n^log2₃3개로 줄어든다. 만약 n=2¹⁰이라면 일반적인 곱셈에서는 (2¹⁰)²=1,048,576회 한 자리 수의 곱셈을 해야 한다. 그러나 카라추바 알고리즘을 이용하면 한 자리 수 곱셈을 3¹⁰=59,049회만해도 되어, 무려 약 17배 이상 곱셈 횟수를 줄일 수 있다.

수학동아