상세 컨텐츠

본문 제목

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

프로그래밍/Multi precision

by ∫2tdt=t²+c 2014. 4. 16. 17:23

본문

앞서 O(nm) 시간에 수행되는 나눗셈 알고리즘에 대해서 다뤄봤는데요, 이번엔 분할정복(Divide and Conquer)을 사용하여 나눗셈 속도를 끌어올리는 방법에 대해서 알아봅시다. 




이 알고리즘은 앞서 소개했던 1998년 [Fast Recursive Division]이라는 논문에 제시된것으로, 4n by 2n 나눗셈과 3n by 2n 나눗셈으로 이뤄져있습니다. 알고리즘에 들어가기에 앞서 표기법을 정리하도록하죠. 위치기수법으로 [a3, a2, a1, a0]a3*X^3 + a2*X^2 + a1*X + a0 를 나타낸다고 약속합시다. 즉 10진법으로 [3, 6, 8, 7]이라는 건 3687를 나타낸다는거죠.

간편한설명을 위하여 나누는 수 B는 정규화되어있다고 가정했습니다.


알고리즘 I. 4n자리 수 A2n자리 수 B로 나누는 알고리즘 (단 A < BX^2. 즉 몫이 2n자리 이하로 나오는 경우)


1. n자리씩 묶어서, A[a3, a2, a1, a0], B[b1, b0]이라고 합니다.

2. [a3, a2, a1][b1, b0]으로 나눕니다. 몫을 q1, 나머지를 [r2, r1]이라고 합니다.

3. [r2, r1, a0][b1, b0]으로 나눕니다. 몫을 q0, 나머지를 S라고 합니다.

4. 몫으로 [q1, q0], 나머지로 S를 출력합니다.


알고리즘 II. 3n자리 수 A2n자리 수 B로 나누는 알고리즘 (단 A < BX. 즉 몫이 n자리 이하로 나오는 경우)


1. n자리씩 묶어서, A[a2, a1, a0], B[b1, b0]이라고 합니다.

2. [a2, a1]b1로 나눕니다. 몫을 q, 나머지를 c라고 합니다.

3. [c, a0] - q*b0 을 계산하여, R = [r1, r0]이라고 합니다.

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

4Y. R += B, q -=1을 계산하고, R < 0인지 확인합니다.

4YY. R += Bq -=1을 계산합니다.

5. 몫으로 q, 나머지로, R을 출력합니다.



알고리즘 III를 보면 서로 재귀적으로 호출한다는것을 눈치챌수 있습니다.

알고리즘 I2번은 알고리즘 II를 호출하는것이고, 알고리즘 II2번은 알고리즘 I을 호출하는 것이죠!


나머지 부분은 자명하니 넘어가도록하고, 알고리즘 II2~3번은 조금 부연설명을 해보도록 하겠습니다.



이죠. 이 과정은 3n by 2n의 나눗셈을 2n by n의 나눗셈 한 번과 n by n의 곱셈 한 번으로 대체할 수 있게합니다. 저번 글에서 설명했듯이 B가 정규화되어있을 경우 이 추정몫은 실제몫과 최대 2밖에 차이나지 않습니다.


그러면 이제 시간복잡도를 계산해보죠. 알고리즘 I의 시간복잡도를 F(n), II의 시간복잡도를 G(n)이라고 합시다.

알고리즘 I에서는 알고리즘 II를 두번 호출하는 일밖에 하지 않죠. 따라서

입니다.

알고리즘 II에서는 2n by n의 나눗셈 한 번(F(n/2))과, n by n 곱셈 한번(M(n))에 2n 길이의 덧뺄셈 1~5번(O(n))을 수행합니다. (단 여기서 M(n)은 n자리 수끼리의 곱셈을 수행하는데 걸리는 시간복잡도입니다. 카라추바나 톰-쿡 알고리즘 등을 이용하면 O(n^2)보다 빠르게 수행할 수 있다는거!)

따라서


짜잔! 이렇게 되겠죠. 핵심은 M(n)이 얼마나 빠르게 나오느냐인데, 카라추바 알고리즘을 사용할 경우 저 합은 2*O(n^log3)이 상한이 됩니다.


그런데 이 알고리즘의 치명적인 문제는 n이 홀수일 경우에는 재귀적용이 불가능하다는 거죠. 또한 4n by 2n의 형태가 아닌 경우 알고리즘 적용이 불가하다는 문제도 있습니다. 임의정밀도에서 실용적으로 써먹기 위해서는 이 문제들을 극복할 필요가 있죠. 어떻게 극복할 수 있는지는 다음 글에서 계속 적도록 하겠습니다.

관련글 더보기

댓글 영역