이집트인의 곱셈

이집트 알고리즘은 인류 최초로 기록된 알고리즘 중 하나다. 빠른 곱셈 알고리즘, 빠른 나눗셈 알고리즘이다.

먼저 알아둬야하는 상식은 고대 문명의 알고리즘이기 때문에 자릿수 개념과 0을 표현하는 방법이 없었다.
자릿수 개념이 없었다는 말이 나중에 나올 이진수와 비슷하다고 생각이 든다.

먼저 곱셈은 1) 1로 곱하기, 2) 1보다 큰 수로 곱하기, 2가지로 정의하여 나눌 수 있다.

1) 1a = a

2) (n+1)a = na+a

 먼저 우리가 알고 있는 일반 상식? "곱셈은 덧셈을 여러번한 것이다"를 구현해보자. 
=> 덧셈을 n-1번 반복해보는 알고리즘(n-1번 반복하니 시간 복잡도는 O(n)라고 알 수 있다.)

우리는 덧셈을 배울 때 결합 법칙을 배웠기 때문에 덧셈의 횟수를 줄일 수 있다.

 중학교 때 배우는 간단한 덧셈의 결합 법칙을 코드에 녹여낸다는 사실 자체가 신비롭다.
다음은 4a = ( (a + a) + a) +a 덧셈을 4번을 한다. 여기서 결합 법칙을 응용한다면, 4a = (a+a) + (a+a), a+a를 한 번하고 a+a끼리 한번 더해주면 총 2번을 한다. 다시 씹어 먹어보자. 4a = (a+a) + (a+a) <= a를 2배로 하고 2배한 만큼 더한다.

우리가 곱셈 시에 a 하나만을 이용하여 곱하는 것은 아님으로 일반적인 식을 n*a라고 했을 때, n을 반으로 줄이고, a를 2배로 키워서 2를 거듭제곱한 횟수만큼 더한 값을 만든다고 할 수 있다. (물론 책에서 이렇게 말한다.)

# 왜 n을 반으로 줄일까?

n = 41, a = 59

1      59
2     118
4     236
8     472
16     944 
32   1888

 이 부분이 제일 어려운 것 같다. 일단 먼저 자릿수 개념이 없던 이집트에서 수를 어떻게 표기하였는지 모르겠다. 또한, 이 알고리즘을 소개한 책에서 이집트에서 어떠한 방식으로 수를 표기하였다고 추가 설명이 없다. 그럼으로 자릿수 개념과 0에 대한 개념이 없는 이집트에서 이진수를 이용하여 표기했다고 가정해보고 41을 2진수로 표기한다.

0010 1001

 위에 비트를 보고 41을 2의 거듭제곱으로 표현했다고 말할 수 있다. 41은 2^6 + 2^4 + 2^1이기 때문이다.
# 책을 보고  이렇게 분석한 것뿐이지 실제로 이런 생각을 스스로 할 수 있을지 걱정이다.

위에서 생각한 결합 법칙을 이용한 알고리즘을 코드로 작성한다면 아래와 같이 할 수 있다.

여기서 덧셈 횟수를 구해보면 #+(n) = ceil(log n) + ( v(n) -1 ) 와 같다. log n의 이유는 재귀함수로 함수가 돌아가며, 한번 돌 때마다 n의 수가 반절씩 줄어들기 때문이고, v(n)은 홀수인 경우의 수를 의미한다. 거기에 n이 1일 때를 빼줌으로 -1을 한다.

알고리즘 개선

이진수로 생각한다는 것은 무엇일까?

이진수의 정의는 0과 1을 이용하여