상세 컨텐츠

본문 제목

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

프로그래밍/Multi precision

by ∫2tdt=t²+c 2014. 4. 22. 04:24

본문



이번글에서는 두번째 글에서 제시했던 알고리즘을 실제 사용가능하도록 개량해보도록 하겠습니다.


알고리즘 I. 4n자리 수 A를 2n자리 수 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자리 수 A를 2n자리 수 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 += Bq -=1을 계산하고, R < 0인지 확인합니다.

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

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


이 알고리즘 기억나시죠? 이 알고리즘은 4n by 2n인 길이의 나눗셈에만 적용이 가능합니다. 만약 나누는 수의 길이가 짝수가 아니거나, 나눠지는수가 4n보다 더 길거나 혹은 4n보다 짧거나 하는 경우는 적용이 불가능하죠. 하지만 약간의 트릭을 사용하면 극복이 가능합니다!


* B의 길이가 홀수일 경우

B의 길이가 홀수인 경우가 있을수 있죠. 예를 들어볼까요?

A = [a5, a4, a3, a2, a1, a0],  B = [b2, b1, b0]인 경우를 살펴보죠.

알고리즘 I을 적용할수 있을거같지만, 이렇게 되면 알고리즘 I 내부에서 호출하는 알고리즘 II에서 막히게 됩니다. 약간의 편법을 사용해봅시다.


A` = [a5, a4, a3, a2, a1, a0, 0],  B` = [b2, b1, b0, 0]라고 하면, A`/B`의 결과는 A/B의 결과와 일치하겠죠. B의 길이는 하나 늘어났지만, 반으로 나누는 알고리즘을 적용가능하게 되었습니다.


* A의 길이가 4n보다는 짧고, 3n보다는 긴 경우

A3n이면 알고리즘 II, 4n이면 알고리즘 I를 바로 적용하면 됩니다. 하지만, 그 사이에 있다면 애매하게 됩니다. 바로 위의 예를 계속 살펴봅시다.

A` = [a5, a4, a3, a2, a1, a0, 0],  B` = [b2, b1, b0, 0]라고 하면 A`의 길이는 7, B`의 길이는 4가 됩니다. A`의 길이가 8이거나 6이면 좋을텐데 안타깝습니다. 이런 경우 A`를 맘대로 잘라내서 길이를 6으로 만들순 없으니, 늘려서 8로 만들면 됩니다.

A`` = [0, a5, a4, a3, a2, a1, a0, 0],  B` = [b2, b1, b0, 0]이라고 하는 거죠. 그렇게 되면

[0, a5, a4, a3, a2, a1] / [b2, b1, b0, 0] = [q3, q2] ... [r3, r2, r1, r0] 계산을 알고리즘 II를 적용해서 수행할 수 있고, 여기서 나온 나머지 [r3, r2, r1, r0]을 다시 넣어서, [r3, r2, r1, r0, a0, 0] / [b2, b1, b0, 0] = [q1, q0] ... R 계산 역시 알고리즘 II를 적용해서 수행할 수 있습니다.


이 경우 자세히 살펴보면 계산을 최적화시킬수 있습니다.

[0, a5, a4, a3, a2, a1] / [b2, b1, b0, 0] = [q3, q2] ... [r3, r2, r1, r0]의 경우 나누는수 B`의 가장 낮은 자릿수가 0이므로, 나머지의 가장 낮은 자릿수 r0은 항상 a1이 될수 밖에 없습니다. 이 사실을 바탕으로 위 식을 [a5, a4, a3, a2] / [b2, b1, b0] = [q3, q2] ... [r3, r2, r1]로 줄일 수 있죠. 마찬가지로 [r3, r2, r1, r0, a0, 0] / [b2, b1, b0, 0] = [q1, q0] ... R 식 역시 [r3, r2, r1, a1, a0] / [b2, b1, b0] = [q1, q0] ... R로 줄일 수 있습니다.


* A의 길이가 4n보다 긴 경우

A4n보다 더 긴 경우는 알고리즘 I을 반복적용해서 나눗셈을 수행가능합니다. A = [a(n-1), ... , a2, a1, a0], B = [b1, b0]이라고 합시다. 


1. [a(n-1), a(n-2), a(n-3)] / [b1, b0]을 수행하고 몫을 q(n-3), 나머지를 [r2, r1]이라고 합니다.

2. [r2, r1, a(n-4)] / [b1, b0]을 수행하고 몫을 q(n-4), 나머지를 다시 [r2, r1]에 저장합니다.

3. [r2, r1, a(n-5)] / [b1, b0]을 수행하고 몫을 q(n-5), 나머지를 다시 [r2, r1]에 저장합니다.

...

4. [r2, r1, a0] / [b1, b0]을 수행하고 몫을 q0, 나머지를 R에 저장합니다.

5. [q(n-3), q(n-4), ... , q1, q0]을 몫으로, R을 나머지로 출력합니다.


* A의 길이가 3n보다 짧은 경우

A의 길이가 3n보다 짧지만, 2n보다는 큰 경우는 앞에서 했던것처럼 A의 최고 자리에 0을 채워넣어 길이를 3n으로 만든 뒤, 알고리즘 II를 적용하면 됩니다. 길이가 2n 이하인 경우는 첫번째 글에서 제시했던 일반적인 나눗셈 알고리즘을 사용하면 됩니다.



XLarge의 실제 코드 구현은 별도의 글에서 소개할 예정이구요, 여기에서는 결과물만 보여드리도록 하지요.



DCMod는 이번 연재를 통해서 구현한 Divide & Conquer를 적용한 나눗셈 함수구요,

BitMod는 앞서 XLarge 연재에서 구현했던 긴 나눗셈 방식 계산 함수입니다.


살펴볼수 있다시피 길이가 두 배가 될때마다 BitMod는 거의 4배씩 연산시간이 늘어나죠. O(n^2)을 따르고 있습니다. 하지만 이번 글에서 소개된 알고리즘을 따르는 DCMod는 점근적으로 3배씩 연산시간이 늘어나고 있습니다. 앞에서 증명했듯이 시간복잡도는 O(n^log3)입니다. 숫자가 더 커지면 시간차이는 더더욱 벌어지겠죠!



가로축은 나누는 숫자의 길이, 세로축은 로그스케일 시간입니다.


관련글 더보기

댓글 영역