구구단 필요 없는 곱셈법

​​구구단 필요 없는 곱셈법

고대 이집트 곱셈법에서 현대의 곱셈 알고리즘까지

초등학교 시절, 구구단을 못 외워 곱셈이 너무 어려웠던 경험이 꽤 있을 것이다. 곱셈을 할 때 구구단이 꼭 필요한 것은 아니다. 25 × 13을 계산하는 과정을 통해 여러 가지 곱셈하는 방법을 알아보자.

참고로, 구구단은 1부터 9까지의 두 수를 곱한 9×9의 곱셈표로, 지금으로부터 약 1200여 년 전 중국에서 시작됐다고 전해진다. 9단부터 외웠기 때문에 ‘구구단’이라고 부른다.

​1 고대 이집트 사람들의 곱셈법
​

고대 이집트 사람들의 곱셈법으로 25 × 13 계산하기

고대 이집트 사람들의 곱셈법은 크게 두 가지 과정으로 나눌 수 있다. 첫 번째는 곱셈식에서 왼쪽에 위치한 수를 이진법으로 분해하는 것이고, 두 번째는 곱셈식에서 오른쪽에 위치한 수를 ‘2배’ 하는 것이다.

그렇다면 고대 이집트 사람들은 왜 수를 이진법으로 분해했을까? 또 고대 이집트 사람들은 오래 전부터 이진법을 알고 있었던 걸까? 사실 고대 이집트 사람들은 기본적으로 십진법을 썼다.

그러나 경험적으로 모든 수를 1과 2의 거듭제곱의 합으로 나타낼 수 있다는 사실을 알고 있었다. 따라서 곱셈식에서 수를 이진법으로 분해해 ‘2배 하기’와 ‘더하기’만으로도 곱셈을 할 수 있었던 것이다.

​2 러시아 농부들의 곱셈법
​

러시아 농부들의 곱셈법으로 25 × 13 계산하기

고대 이집트 사람들의 곱셈법과 비슷하면서도 조금 다른 러시아 농부들의 곱셈법도 있다. 러시아 농부들의 곱셈법에서는 곱셈식에서 왼쪽에 위치한 수를 2로 나눠 그 몫을 쓰고, 나머지와 상관없이 몫을 연속해서 2로 나눈다.

고대 이집트 사람들의 곱셈법과 조금 다르지만, 본질적으로 수를 2로 분해한다는 점은 똑같다. 결국 러시아 농부들의 곱셈법도 이진법과 분배법칙을 이용한 것이다.

​3 선만 잘 그으면 곱셈이 된다?!
​

선 긋기 곱셈법으로 25 × 13 계산하기

선 긋기 곱셈법은 자연수의 곱셈 원리를 잘 활용한 방법이다. 자연수의 곱셈은 덧셈으로 바꿔 나타낼 수 있다. 예를 들어 3 곱하기 5는 3을 5번 더하면 된다. 선긋기에서 교차점의 개수는 자연수를 연속으로 더한 값이 된다.
​

구구단 필요 없는 곱셈법
예를 들어 아래 그림과 같이 그은 선에서 교차점은 3+3(또는 2+2+2)으로, 3×2를 나타낸다. 따라서 교차점이 의미하는 자릿수만 알면, 교차점의 개수를 묶은 다음 더하는 것으로 곱셈 값을 쉽게 구할 수 있다.

​4 겔로시아 곱셈법과 존 네이피어의 계산막대

표를 사용해 곱셈을 하는 방법에는 겔로시아 곱셈법과, 존 네이피어(John Napier, 1550~1674)의 계산막대를 사용한 곱셈법이 있다. 먼저 겔로시아 곱셈법의 ‘겔로시아’는 ‘격자’를 뜻하는 말로, 이 곱셈법은 인도에서 처음 시작된 것으로 추정되고 있다.

인도의 수학자 바스카라(Bháskara)가 지은 수학책인 [릴라바티]에 등장했고, 또 다른 인도의 수학책에서도 겔로시아 곱셈법이 나타나 있기 때문이다. 겔로시아 곱셈법은 현재 많은 사람들이 사용하는 세로 곱셈법과 원리가 같으며, 사선으로 배열해 수를 더하는 방식이다.
​

겔로시아 곱셈법으로 25 × 13 계산하기

반면 네이피어의 곱셈법은 구구단을 막대로 만들어 곱셈을 쉽게 하도록 만든 것이다. 구구단 계산막대가 있기 때문에 당연히 구구단을 외울 필요가 없지만, 항상 계산막대가 있어야 한다. 네이피어는 계산의 혁명이라고 부르는 ‘로그(log)’를 발명한 수학자로도 잘 알려져 있다.

​

존 네이피어의 계산막대 곱셈법으로 25 × 13 계산하기
​

​5 곱셈 알고리즘 등장, 큰 수의 곱셈도 문제없어!

고대와 중세의 곱셈법을 알아봤으니 컴퓨터 시대의 곱셈법도 알아보자(컴퓨터는 수를 이진법으로 다루고 있으니, 애당초 구구단을 외울 필요가 없다).

카라추바 알고리즘은 러시아의 수학자 아나톨리 알렉세예비치 카라추바가 1960년에 발견한 것으로, 컴퓨터에서 계산을 빠르게 하기 위해 고안된 알고리즘이다. 일반적으로 n자리 수 두 개를 곱하려면 한 자리 수의 곱셈을 n2번 해야 한다. 예를 들어 25×13을 하려면 5×3, 2×3, 5×1, 2×1과 같이 한 자리 수의 곱셈이 4번 필요하다. 그런데 카라추바 곱셈 알고리즘을 이용하면 한 자리 곱셈 횟수가 최대 n의 log23제곱개로 줄어든다. 만약 n=210이라면 일반적인 곱셈에서는 (210)2=1,048,576회 한 자리 수의 곱셈을 해야 한다. 그러나 카라추바 알고리즘을 이용하면 한 자리 수 곱셈을 310=59,049회만 해도 되어, 무려 약 17배 이상 곱셈 횟수를 줄일 수 있다.

25×13을 카라추바 알고리즘으로 계산하면 위와 같은 과정을 거친다. 즉, 카라추바 알고리즘의 기본원리는 식을 변형한 데에 있다. 25×13을 하려면 4번의 곱셈이 필요한데, 식을 변형해 인수가 3개로 줄어들도록 한 것이다.

이 방법은 간단한 숫자의 곱셈에서는 오히려 더 복잡하고 번거로워 보이지만, 컴퓨터로 큰 수의 곱셈을 할 때에는 시간을 줄여 효율적이다.

카라추바 알고리즘의 원리를 문자로 사용해 나타내면 다음과 같다.

​​(a×10 + b)(c×10 + d) = 100ac + 10{ac + bd - (a-b)(c-d)} + bd
즉, ac + bd - (a-b)(c-d) = bc + ad 인 성질을 이용한 것이다.

카라추바 알고리즘 이후에, 톰-쿡(1966년), 쉔하게-슈트라센(1971년), 퓌러 알고리즘(2007년) 등 새롭고 더 빠른 곱셈 알고리즘이 등장하였다. 앞으로도 언제 더 새로운 알고리즘이 등장할지는 알 수 없다.

또 그 발명의 주인공이 이 글을 보고 있는 누군가가 될 지도 모를 일이다. 구구단을 외우는 것은 힘들긴 하겠으나, 그래도 그냥 외우는 것이 좋다. 컴퓨터는 컴퓨터고, 사람이 계산할 때 편리함으로 따지자면 아직은 구구단 곱셈법이 최고니까.

[출처] http://m.navercast.naver.com/mobile_contents.nhn?rid=22&contents_id=31231​

글
장경아 | 수학동아기자
학창시절 수학을 잘 가르치는 선생님이 되고 싶었지만, 더 많은 독자들에게 재밌는 수학을 소개하고 싶어 수학동아 기자가 됐다. 실생활 속에서 신기하고 재밌는 수학 이야기를 찾기 위해 노력하고 있다.