고대 이집트 곱셈법

고대 이집트 곱셈법은 구구단를 사용하지 않고 2로 나누고 곱하는 것과 덧셈만을 가지고 두 수를 곱하는 방법이다. 이집트 곱셈법과 농부 곱셈법은 첫 번째 수를 2의 거듭제곱들의 합으로 분해하고, 두 번째 수의 2의 거듭제곱에 대한 표를 만들어 첫 번째 수와 두 번째 수의 곱을 구한다. 어떤 지역에서는 이 방법을 아직도 사용한다.

두 번째 이집트 곱셈법과 나눗셈법은 모스크바 신관 문자와 기원전 17세기에 쓰여진 린드 파피루스에서 발견되었다.

분해

이집트인들은 이진법을 통하여 수를 2의 거듭제곱들의 합으로 분해하지 않았다. 이집트인들은 그러한 개념을 몰랐고, 보다 간단한 방법에 의존해야 했다. 고대 이집트인들은 커다란 2의 거듭제곱수들을 계산해 놓은 표를 가지고 있었고, 그래서 매번 그 수들을 다시 계산할 필요가 없었다. 그러므로 수의 분해는 그 수를 만드는 2의 거듭제곱수들을 찾는 일로 이루어졌다. 이집트인들은 경험적으로 주어진 2의 거듭제곱의 합들은 오로지 한 가지 수로만 나타난다는 것을 알았다. 그들은 주어진 수보다 작거나 같은 수들 중에서 가장 큰 2의 거듭제곱을 찾고, 그것을 빼어나가는 것을 반복함으로써 주어진 수를 2의 거듭제곱의 합으로 분해하였다.

가장 큰 2의 거듭제곱을 찾기 위해 1에서부터 시작해 2를 계속 곱해나간다.

예:

1 x 2 = 2
2 x 2 = 4
4 x 2 = 8
8 x 2 = 16
16 x 2 = 32

25를 2의 거듭제곱들의 합으로 분해하는 예:

• 25보다 작거나 같은 가장 큰 2의 거듭제곱은 16이므로,
• 25 - 16 = 9,
• 9보다 작거나 같은 가장 큰 2의 거듭제곱은 8이므로,
• 9 - 8 = 1,
• 1보다 작거나 같은 가장 큰 2의 거듭제곱은 1이므로,
• 1 - 1 = 0

그러므로 25는 16과 8, 1의 합으로 이루어진다.

표

첫 번째 수를 분해한 뒤에, 두 번째 수에 2의 거듭제곱을 곱한 수들의 표를 만드는 것이 필요하다.

예를 들어 첫 번째 수를 분해했을 때 나오는 가장 큰 2의 거듭제곱이 16이고, 두 번째 수는 7이라하면 다음과 같은 표가 만들어질 것이다.

• 1; 7
• 2; 14
• 4; 28
• 8; 56
• 16; 112

결과

첫 번째 수를 분해했을 때 나온 수들과 대응하는 두 번째 단의 수들을 더해서 결과를 얻는다.

예를 들어 25 곱하기 7을 계산하고 싶다면 25를 분해했을 때 나오는 16, 8, 1과 위의 표에서 대응하는 112, 56, 7를 모두 더하면 된다.

• 25 x 7 = 112 + 56 + 7 = 175

이 방법의 장점은 2로 곱하는 것과 덧셈, 뺄셈만을 통해 곱하기를 할 수 있다는 것이다.

농부 곱셈법

농부 곱셈법, 혹은 러시아 농부 곱셈법은 이집트 곱셈법과 비슷한 알고리즘이다.

• 곱하고 싶은 두 수 A 와 B를 제일 첫 줄에 쓴다.
• A부터 시작하여 2로 나누고 나머지는 버린다. 더 이상 나눌 것이 없을 때까지 계속 반복하고, 결과를 차례대로 아랫줄에 써내려간다.
• A를 나눈 만큼 B를 곱해나간다. 결과를 차례대로 아랫줄에 써내려간다.
• A단에서 홀수가 있는 줄에 있는 B단의 숫자들을 모두 더한다. 그것이 곱셈의 결과이다.

예: 27 곱하기 82

A 단	B 단	더할 숫자
27	82	82
13	164	164
6	328
3	656	656
1	1312	1312
		결과: 2214

이 방법은 곱셈의 분배법칙때문에 성립한다.

$82 \times 27\,$	$= 82 \times (1\times 2^0 + 1\times 2^1 + 0\times 2^2 + 1\times 2^3 + 1\times 2^4\,)$
	$= 82 \times (1 + 2 + 8 + 16)\,$
	$= 82 + 164 + 656 + 1312\,$
	$= 2214\,.$

증명

농부 곱셈법은 수학적 귀납법을 통해 증명할 수 있다.

자연수 n, m에 대해 PM(n, m)이 농부곱셈법의 결과를 나타낸다고 하자.

기본적인 경우

$n = 1$이고 $m \in \N$인 n, m에 대해, $PM(n, m) = PM(1, m) = 1 \cdot m = n \cdot m$은 참이다.

$n = 2$이고 $m \in \N$인 n, m에 대해, $PM(n, m) = PM(2, m) = 2 \cdot m = n \cdot m$은 참이다.

일반적인 경우

$PM \left (\left \lfloor \frac n 2 \right \rfloor, 2m \right ) = n \cdot m$이라고 가정하면,

$n\!\,$이 짝수일 때, $PM(n, m) = PM \left (\left \lfloor \frac n 2 \right \rfloor, 2m \right )$이 성립한다.

$n\!\,$이 홀수일 때, $PM(n, m) = PM \left (\left \lfloor \frac n 2 \right \rfloor, 2m \right ) + m$이 성립한다.

따라서 모든 자연수 n, m에 대해 $PM(n, m) = n \cdot m$이 참이다.

같이 보기

• 이집트 수학
• 곱셈 알고리즘
• 이진법

바깥 고리

• 러시아 농부 곱셈법
• 러시아 농부 곱셈법 (pdf 파일)