구구단 외우지 않고도 곱셈할 수 있다고?!

수학을 배우는 과정에서 학생들은 여러 번의 위기를 경험한다고 한다. 그 중에서 제일 처음 겪는 위기는 아마도 초등학교 2학년 때 꼭 외워야 하는 구구단을 외울때가 아닐까.

구구단은 곱셈을 빠르고 능숙하게 하기 위해 필요한 도구다. 그런데 모든 곱셈법에서 구구단이 반드시 필요한 것은 아니다. 구구단 없이도 곱셈을 할 수 있는 방법이 여럿 있다.

지금으로부터 약 5천 년 전, 고대 이집트 사람들은 구구단이 없이도 곱셈을 할 수 있었다. 이집트 사람들은 '2배하기'와 '더하기'만으로 곱셈을 했다. 예를 들어 25×13을 하려면 다음과 같은 과정을 따라 곱셈을 할 수 있다.

(주)동아사이언스 제공

이집트 사람들의 곱셈법이 번거롭다면, 선긋기만으로도 곱셈을 할 수 있다. 예를 들어 선긋기 곱셈법으로 25×13을 구하면 다음과 같다.

(주)동아사이언스 제공

뿐만 아니라, 곱셈법은 현대수학자들이 지금도 연구하는 분야 중 하나이기도 하다. 컴퓨터에서 계산을 빠르게 하기 위해 더 효율적인 곱셈 알고리즘을 만들고 있는 것이다. 대표적인 예로 러시아의 수학자 아나톨리 알렉세예비치 카라추바는 1960년대 '카라추바 알고리즘'을 만들었다.

일반적으로 n자리 수 두 개를 곱하려면 한 자리수의 곱셈을 n² 개 해야하는데, 카라추바 알고리즘은 한 자리의 곱셈 횟수를 최대 n^log₂3개로 줄어들도록 만든다. 덕분에 곱셈 시간을 줄일 수 있다.
이 알고리즘은 특히 큰 수의 곱셈에서 그 효과가 크다. 예를 들어 n=2¹⁰이라면 일반적인 곱셈에서는 (2¹⁰)²=1,048,576회 한 자리 수의 곱셉을 해야 한다. 그러나 카라추바 알고리즘을 이용하면 한 자리 수의 곱셈이 3¹⁰=59,049회로 줄어 곱셈 횟수를 무려 17배 이상 줄일 수 있다.
 수학동아