상세 컨텐츠

본문 제목

[진짜 BigFloat 구현하기] 4. 시프트 연산과 나눗셈(나머지)

프로그래밍/Multi precision

by ∫2tdt=t²+c 2014. 3. 2. 02:34

본문





앞서서 곱셈을 구현했으니, 이제 나눗셈을 구현할 차례겠죠?

근데 문제는 나눗셈을 구현하는게 생각보다 까다롭다는거지요. 

일반적으로 우리가 학교에서 배우는 나눗셈 방법은 장제법(long division)이라고 하는데,

이게 얼마나 어려운지는 초등학생들이 더 잘 압니다.

http://bab2min.tistory.com/54


자세한 알고리즘에 대한 설명은 위 페이지로 대신합니다.

우리가 나눗셈을 할때 나누는 수랑 나눠지는 수 자리를 맞춰서 계산하죠. 자리 맞추기 위해 숫자들을 왼쪽으로 옮기고 오른쪽으로 옮기고 하는데, 2진법에서 이것과 근본적으로 같은 연산이 비트 시프트 연산입니다.

다른말로 하면 나머지를 구하는 나눗셈 연산을 위해서는 먼저 시프트 연산을 구현할 필요가 있다는 거지요.



오늘 구현하게 될 함수들 목록입니다. 많아보이지만 별거없어요.


NaN이라는 개념이 등장했어요~! 난!이라는 게 아니라 Not A Number의 약자로 연산이 불가능하거나 연산결과가 실수 범위에서 나오지 않는 경우를 표현하기 위해 주로 부동소수점에서 사용되는 값입니다. 덧셈, 뺄셈, 곱셈 연산에서는 문제가 없었지만, 나눗셈이 등장하는 순간 0으로 나누기라는 함정이 생기게 되죠. 0으로 나누는게 불가능하다는 건 다들 알고계실테니 설명하지 않겟구요, 0으로 나눈 결과를 어떻게 표현하기는 해야하니 NaN으로 세팅해주는거죠.


일단 NaN관련 함수를 구현합니다.




먼저 시프트연산보다 앞서서 비교함수를 구현해보죠. 나눗셈 구현에는 비교연산도 필수적이니까요.

하나는 두 XLarge를 비교하는 함수구요, 다른 하나는 한 XLarge랑 0을 비교하는 함수입니다.



뭔가 없는거 같네요. 아 절대값 비교를 하는 _Abs_Cmp를 구현안했죠. 구현해보입시다.


(조금 복잡해보이죠? 하지만 5분만 생각해보면 당연하다는 걸 이해하실수 있을거에요.

goto를 적절히 사용하면 로직이 단순해지는 경우도 있습니다.)

이제 이 함수를 이용해서 _Abs_Cmp를 구현합니다.



환형큐로 부동소수점 포맷을 구현하다보니 비교함수쪽이 매우 복잡하죠? 다시 정리하자면 비교 프로세스는 다음과 같습니다.

1. 최고 자릿수를 비교합니다. 최고 자릿수가 큰 쪽이 더 큰 수

2. 최고 자릿수가 같으면, 전체 길이가 짧은 쪽에 맞춰서 정수 배열을 비교합니다. 정수 배열이 큰 쪽이 더 큰수

3. 정수 배열도 같으면, 지수부를 비교합니다. 지수부가 작은 쪽이 더 큰 수 

4. 지수부도 같으면 두 수는 같은거.


꺄울! 수고많으셨습니다. 이제야... 시프트함수를 구현합니다. 먼저 도우미 함수 보고 가실게요.


직관적인 코드라 설명은 별도로 필요가 없을거같네요! 아주아주 중요한 주의사항은 shift값이 32보다 작아야한다는 겁니다. 어차피 정수가 32비트 단위로 저장되기 때문에 32비트 이상 시프트하는 건 정수 단위로 움직이는것 32미만의 비트 시프트로 분할해서 생각할 수 있기 때문이죠. 그래서 아예 32비트 이상 시프트하는것은 고려하지도 않았습니다.




자, 시프트 연산 구현을 마쳤으니, 이제 본격적으로 나머지를 구하는 나눗셈 연산을 구현해봅시다!




산수시간에 배웠던 나눗셈 방법과 본질적으로 동일합니다. 차이점이 있다면 이진법을 쓴다는거죠. 몫의 각 자리가 0 아니면 1이 되기때문에 나눠지는수와 나누는수를 비교해서 나눠지는수가 크다면 그 자리의 몫은 1, 아니면 0으로 간단하게 결정할 수 있습니다.


이방법은 사실 코드만 봐도 저렇게 긴데, 당연히 빠른 알고리즘은 아닙니다. 뺄셈이 O(n)시간에 수행된다고 했었는데, 그런 뺄셈을 최악의 경우 32*n번 해야하니, 전체 시간복잡도는 O(n^2)이 됩니다. 물론 곱셈도 O(n^2)이었는데, 나눗셈이 곱셈보다도 훨씬 느립니다.


속도를 더 빠르게 할 방법이 없을까요?


없다면 이 글을 안 썼겠죠. 분할정복(Divide & Conquer)의 방법을 사용해서 시간복잡도를 비약적으로 낮추는 방법이 있습니다. 여기까지 가기 전에 먼저 곱셈 알고리즘부터 개선하고 가는게 좋겠지요?

다음 글에서는 O(n^2)의 벽을 깨버린 곱셈 알고리즘을 소개하는 시간을 갖도록하겠습니다.

관련글 더보기

댓글 영역