빠른 나눗셈 알고리즘을 찾아서 1

http://bab2min.tistory.com/227

http://bab2min.tistory.com/408

앞서 여러 글에서 나눗셈이 생각보다 복잡한 일이라는 걸 반복해서 언급했었는데요, 그렇다고 해서 빠르게 나눗셈을 계산하는 방법이 없다던가 그런것은 아닙니다. 곱셈을 빠르게 하는것처럼 나눗셈 역시 빠르게 계산하는 알고리즘이 존재합니다. 이 포스팅은 다음 글들을 참조해서 작성되었음을 명시하는 바입니다.

* 도널드 크누스, [[컴퓨터 프로그래밍의 예술 - 2. 준수치적 알고리즘]]

* Christoph Burnikel Joachim Ziegler, [Fast Recursive Division] 

우리가 긴 나눗셈을 할때 제일 처음 하는 것은 몫으로 어떤 숫자가 들어갈지를 적당히 추측해내는것입니다. 뭐 사람은 오랜 경험을 통해 감으로 몇을 넣으면 알맞게 계산이 될지 알수 있다고 하지만 컴퓨터가 그러기는 쉽지가 않죠.

가장 간단한 경우로 X진법에서 (n+1)자리 수 A를 n자리 수 B로 나누는 경우를 생각해봅시다.

두 수의 각 자릿수가 위와 같이 표현된다고 약속합니다. 상황을 단순하게 하기 위해 먼저 A가 B*X 보다 작다고 가정해봅시다. 그 경우는 당연히 몫이 1자리로 나오겠죠. 우리는 실제로 저 나눗셈을 일일히 하지 않고도 이 몫을 빠르게 추정해야하는 방법을 찾고자 합니다.

제일 좋은 방법은 가장 높은 자리에 있는 수를 보고 어림해보는 것이죠.

a0a1과 b1을 보고 적당히 나눗셈을 해서 몫을 추정해보는겁니다. 다만 몫이 1자리로 나와야하므로, X이상이 될경우는 X-1을 몫으로 추정하는 거죠. 13978 / 2178 을 예로 들어보면 추정 몫은 [13/2]로 6이 나오겠네요.

이 추정몫 q^가 실제몫 q보다 언제나 크거나 같다는 사실을 증명해봅시다.

1. q^가 X-1일 경우, q는 언제나 X 미만이므로, q^ >= q 입니다.

2. 그렇지 않을 경우

입니다. (모든 미지수들이 0보다 큰 정수라는 점!)

그러면 이제 추정몫 q^을 나눗셈 공식 A - QB = R에 넣어 나머지가 어느정도로 나오는지 확인해봅시다.

나머지의 정의는 나눗셈의 정의상 0 <= R < B 일수 밖에 없죠. 근데 추정몫q^로 계산해본 나머지도 B보다 작다는 조건을 만족시킵니다. 몫 Q의 정의가 0 <= A-QB < B를 만족하는 최대의 Q임을 생각해볼때, 추정몫 q^는 자명하게도 Q와 같거나 그보다 작을 수 밖에 없습니다.

그러므로 q^ >= q 입니다.

그 다음 단계는 추정한 몫 q^를 B와 곱해서 A와 빼서 나머지를 구해보는거죠. 앞서 q^가 q보다 같거나 크다고 입증하였으니, 이 나머지가 0 이상이 나오면 추정이 한 번에 맞은 것이고, 0보다 작게 나오면, q^가 실제몫보다 조금 더 크게 나온것이겠죠.

그런데 이 추정몫과 실제몫의 차이는 얼만큼까지 날까요? 큰 차이가 나지 않는다는 것을 증명해봅시다.

그리고 q > A/B-1이죠. 일단 q^가 q보다 3이상 크다고 가정해봅시다.

[A/B]가 실제몫 q라는 거 기억하고 계시죠? 앞에서 q^와 q 차이가 3이상이라는 가정과 q^는 X보다 작다는 사실이랑 조합해서 결과를 이끌어 내봅시다.

만약 b1이 X/2 이상이라면, 위 부등식의 좌변은 X-2 이상이 되므로 애초에 부등식이 성립하지 않습니다. q^가 q보다 3이상 크다는 가정이 거짓이 되는거죠. 그러므로 b1이 X/2이상일 경우 q^와 q의 차이는 2이하로 밖에 날수 없습니다.

* 만약 b1이 X/2이상이라는 조건을 충족시키지 못한다면? 그런 경우는 아예 고려대상에서 제외할게요. A와 B에 적당한 수를 곱해서 b1이 X/2 이상이라는 조건을 만족시킬수 있도록 정규화(normalize)시킬수 있으니까요!

자, 추정몫이 실제몫과 큰 차이가 나지 않는다는 것을 증명했으니, 다음 단계로 넘어가봅시다. 추정몫을 이용해서 나머지를 구해보고, 나머지가 음수로 나오면 추정몫을 1줄이고, 나머지를 B만큼 키워주면 되겠죠. 그래도 나머지가 음수면 추정몫을 1 더 줄이고, 나머지를 B만큼 더 키워주면 됩니다. 이렇게 하면 정확한 몫을 얻을 수 있죠.

이를 바탕으로 X진법에서 (n+1)자리 수 A를 n자리 수 B로 나누는 알고리즘을 작성해봅시다. (몫은 한 자리로 나온다고 가정합니다. 그 이상의 경우는 따로 다루도록 할게요.)

1. B의 최고자리수가 X/2 이상인지 확인합니다.

1Y. A와 B를 왼쪽으로 시프트하여, B의 최고자리수가 X/2이상이 되도록 만듭니다.

2. A의 최고자리수 2개를 A`로, B의 최고자리수 1개를 B`로 둡니다.

3. Q = min(A` / B`, X-1) 를 계산합니다.

4. R = A - B*Q를 계산합니다. (곱셈 연산시 빠른 곱셈 알고리즘을 적용하면 좋겠죠!)

5. R < 0 인지 확인합니다.

5Y. Q -= 1, R += B 를 계산하고, 다시 한번 R < 0 인지 확인합니다.

5YY. Q -= 1, R += B를 계산합니다.

6. R을 역정규화합니다.

7. 몫은 Q, 나머지는 R로 연산 결과를 출력합니다.

위 알고리즘에서 사용한 연산은 비트시프트 연산 1번(O(1)), 2 by 1 나눗셈 1번(O(1)), n by 1 곱셈 한 번(O(n)), 뺄셈 1~3번(O(1)), 덧셈 0~2번(O(1))입니다. 시간복잡도는 총 O(n)이군요!

자, 그런데 문제는 n+1자리 수를 n자리 수로 나눌경우가 얼마냐 있겠냐는거죠. 더 일반적인 n+m자리 수를 n자리로 나누는 경우를 다뤄봅시다. 사실 이건 n+1자리 수를 n자리로 나누는 일을 여러번 반복하는것에 불과합니다.

1. B의 최고자리수가 X/2 이상인지 확인합니다.

1Y. A와 B를 왼쪽으로 시프트하여, B의 최고자리수가 X/2이상이 되도록 만듭니다.

2. A의 상위 자리수 n+1개에 대하여, B로 나누는 연산을 수행합니다. (이 연산은 방금 위에서 제시한 알고리즘을 사용하면 되겠죠.) 그 몫을 Qi, 나머지를 R로 둡니다.

3. A의 상위 자리수 n+1개를 R로 대체합니다. (R은 n자리수이므로, A의 전체 길이는 1혹은 그 이상 감소합니다.)

4. A의 전체 자리수가 n보다 큰지 확인합니다.

4Y. 2번으로 돌아가서 반복

5. R을 역정규화합니다.

6. Qi~Q0을 조합하여 몫으로 출력하고, R을 나머지로 출력합니다.

위 알고리즘에서 사용한 연산은 비트시프트 연산 1번(O(1)), n+1 by n 나눗셈 m번(O(nm))이 됩니다. 

마지막으로 위에서는 무시한 상황인데, X진법에서 (n+1)자리 수 A를 n자리 수 B로 나눌때, A >= B*X 인경우를 다뤄봅시다. 사실 이 경우는 A의 상위 n자리와 B와의 나눗셈으로 대체할 수 있습니다. 그러면 n자리 수를 n자리 수로 나누는 경우를 다뤄보죠. 이 경우는 정규화된 경우 자명하게도 몫은 0 혹은 1이 나올수 밖에 없습니다. 정규화되지 않은 경우는 정규화를 하면 되겠죠.

X진법에서 n자리 수 A를 n자리 수 B로 나누는 알고리즘

1. A < B인지 확인합니다.

1Y. 몫을 0, 나머지를 A로 출력합니다.

2. B의 최고자리수가 X/2 이상인지 확인합니다.

2Y. A와 B를 왼쪽으로 시프트하여, B의 최고자리수가 X/2이상이 되도록 만듭니다. 만일 시프트 연산으로 A가 (n+1)자리가 되었다면, n+1자리 나누기 n자리 알고리즘으로 점프!

3. R = A - B로 설정합니다.

4. R을 역정규화합니다.

5. 몫을 1, 나머지를 R로 출력합니다.

간단하죠!

위의 알고리즘은 n+m by n 나누기 연산을 O(nm)의 시간에 수행할수 있습니다. 사실 빠른건 아니지요. 하지만 2n by n 나누기 연산의 경우 분할정복을 사용하여 더 빠른시간에 나눗셈을 수행할 수 있다는거! 다음 글로 패스!