고대 이집트 곱셈법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

고대 이집트 곱셈법구구단를 사용하지 않고 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 
328 
656  656 
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이 참이다.

같이 보기[편집]

바깥 고리[편집]