BigFloat로 Pi를 구해보자-5. 나눗셈 구현 (Goldschmidt division)

Posted by 적분 ∫2tdt=t²+c
2012.10.24 23:06 프로그래밍/Multi precision



저번 연재에서 나눗셈 알고리즘을 설명했으니, 이번에는 곧바로 구현에 들어갑니다.


먼저 나눗셈을 위해서는 비트 시프트 연산이 필수적입니다.


다음은 16비트 정수를 왼쪽으로 3비트 시프트하는 연산입니다.


a0, a1, a2는 오버플로우로 버려지게 되고, 오른쪽의 비는 3자리는 0으로 채워지게 됩니다.


다음은 오른쪽으로 3비트 시프트하는 연산입니다.


b5, b6, b7은 언더플로우로 버려지게 되고, 왼쪽의 비는 3자리는 0으로 채워지게 됩니다.



자 그럼 이제 코드를 볼까요?


왼쪽으로 시프트하는 함수,

오른쪽으로 시프트하는 함수를 구현했습니다.


연산은 인라인 함수에서 다 행하니 실제 함수들은 날씬해졌네요ㅎㅎ.


다음으로 필요한 것은 비트 스캔(bit scan) 함수입니다. 이 함수는 비트열을 왼쪽(혹은 오른쪽)에서부터 스캔하여 1이 나오는 지점을 찾아냅니다.


다음과 같은 비트열이 있을때

int n = 0;

while(a[n] == 0) n++;

return n;

과 같은 연산을 하는 함수를 구현하겠다는 말이지요.

이 함수는 나눗셈 연산이 나누는 수 D를 정규화(normalize)하기 위해 사용됩니다. 나눗셈 알고리즘을 적용하기 위해서는 1 < D < 2 이거나  0.5 < D < 1과 같은 조건을 만족시켜야 했습니다. 이를 위해서는 D의 최상위비트를 찾아서 얼만큼 시프트해야 저 범위로 들어가는지 알아내야 합니다.


i_bscs함수는 dest에서 첫번째 1이 몇번째 비트에서 등장하는지 알려줍니다.


이제 Goldschmidt의 알고리즘을 사용하여 1/D를 계산하는 함수를 짜봅시다.



글이 길어져서, Newton-Raphson 방법을 이용한 구현을 다음으로 넘겨야겠습니다.


Tags
이 댓글을 비밀 댓글로