BigFloat로 Pi를 구해보자-4. 나눗셈은 어려워 (나눗셈 구현 알고리즘)

눈을 감고 사칙연산을 배우던 초등학생 때로 돌아가보면, 덧셈, 뺄셈, 곱셈, 나눗셈 중 제일 어려웠던 것은 나눗셈이었습니다. 계산속도도 나눗셈이 제일 느리고, 실수도 많이 합니다. 그건 나눗셈을 배우던 학생들이 어리석어서가 아니라 본질적으로 나눗셈이 곱셈보다 어려운 과정이기 때문입니다.

한 번의 나눗셈을 하기 위해서는 제일 높은 자리에 들어갈 숫자를 짐작하여서 곱해보고, 빼는 작업을 무수히 반복해야 합니다. 만약 n자리 수를 나눈다고 하면 최소 n번의 곱셈과 뺄셈이 필요하다는 것이지요. 그리고 결과가 나눠떨어지지 않아서 소수점 이하로 내려가면, 걸리는 시간은 몇배로 불어날지 모릅니다. 이렇게 장황하게 나눗셈에 대해서 설명한것은, 필산 나눗셈 알고리즘은 소수점 아래로 무한한 정밀도를 추구하는, 우리가 만들 BigFloat 데이터형에 쓸수 없다는 것을 강조하기 위함입니다.

실제로 요즘 사용되는 CPU에서는 정수 나눗셈 연산이 부동소수점 나눗셈 연산보다 느린 경우도 있습니다. CPU는 부동소수점 나눗셈 연산에 최적화된 알고리즘을 사용하기 때문에 곱셈 연산 못지 않게 빠르게 끝마칠 수 있습니다.

그럼 나눗셈은 어떻게 구현해야할까요? N / D를 계산한다고 해봅시다. 0 < D < 2 이면 테일러 전개를 사용할 수 있을지도 몰라요.

1. 테일러 전개

x의 절대값이 1보다 작은 경우 위 식은 느린 속도지만 수렴합니다. 즉 D = x+1이라고 두고, x를 위식에 대입한다면 1/(x+1)을 구할 수 있을테고, 거기에 N을 곱하면, N/D를 계산해 낼 수 있을겁니다!

약간의 문제점이 있다면, D가 2 이상인 경우는 쓸수 없다는 것이고, 수렴속도가 매우 느리다는 것이지요. 모든 D값에 대해 이 식을 적용할 수 있도록 확장해봅시다.

당연한 식입니다. 만약 D가 2보다 크다면, 적절한 정수 p를 선택하여 가 1과 2사이로 오도록 조절할 수 있습니다. 다행히도 컴퓨터는 비트 연산^[각주:1]을 할 수 있으므로, 2^p를 곱하는 것은 일도 아닙니다. 하지만 여전히 수렴속도가 느린것은 해결되지 않았군요. 다른 방법을 찾아봅시다.

2. Goldschmidt Division

골드슈미츠라는 학자는 좋은 방법을 발견해 냈습니다!

(또 당연한 식이 나왔네요...ㅋ)

적당한 F들을 분모분자에 곱해나가는데,를 1로 수렴하게 만드는 그런 F를 곱해나가자는 게 이 알고리즘의 전부입니다. 분모가 1로 수렴하면 나눗셈을 할 필요가 없을테니깐요. 그럼 그런 F는 어떻게 찾을 수 있을까요?

라고 하면

으로 두면 됩니다.

중학교때 배웠던 곱셈공식을 차례로 적용해보면,

F_1을 곱하면 1-x^2을 얻고, F_2를 곱하면 1-x^4을 얻을 겁니다. F_3을 곱하면 1-x^8을 얻고....

이러한 F들을 계속 곱해나가면 분모는 1로 수렴할 수 있을 겁니다. 단 수렴을 위해서 |x|<1 이라는 조건이 필요합니다. 빠른 수렴을 위해 D의 범위를 0.5에서 1 사이로 제한해버립시다.(이 역시 N과 D를 비트 시프트하는 것으로 대체할 수 있습니다.) 그러면 x의 범위는 0에서 0.5사이가 될테니깐 항이 늘어날수록 빠른 속도로 수렴할 것입니다.

그럼 우리가 원하는 몫은 다음과 같이 계산되겠지요.

덧셈과 곱셈은 이미 저번 연재에서 구현했으니, 문제 될게 없습니다.

3. Newton-Raphson Method

또 다른 선택지도 있습니다. Newton-Raphson의 근사 방법을 사용해도 됩니다.

이 방법은 다항방정식의 근을 근사하는데 사용될 수 있는데요, 다음과 같습니다.

초기값 X_0가 적절하다면 대부분의 경우 위 점화식의 극한은 f(x)=0을 만족하는 해로 수렴합니다.

우리는 1/D를 구하고 싶은것이므로, f(x) = 1/X-D로 두겠습니다. 그러면 위 점화식은 아래와 같이 되겠지요.

이제 이 식에 적절한 초기값을 넣어 근사시키면 1/D가 구해지겠지요. 우리는 이 식을 계산하는데 필요한 덧셈, 뺄셈, 곱셈을 모두 구현했으니 문제 없습니다.

글이 길어져서 폭발하겠으니, 실제 구현은 다음으로 넘겨야겠군요~~ 바이바이

1. 비트 연산에는 비트 마스킹(masking)과 비트 반전(negation), 비트 시프트(shift) 등이 있는데, 비트 시프트 연산으로 2^n을 곱하거나 나누는것을 대체할 수 있습니다. [본문으로]