BigFloat로 Pi를 구해보자-2. 덧셈, 뺄셈 구현하기

Posted by 적분 ∫2tdt=t²+c
2012.10.16 01:51 프로그래밍/Multi precision


(짤방은 그냥 재미로...)

BigFloat에서 덧셈과 뺄셈을 구현하기 위해서는 초등학교 다닐때의 마음으로 되돌아가서, 컴퓨터에게 받아올림과 받아내림을 알려줘야합니다.ㅋ

(p = 2^32)

c2 = (a2 + b2)를 p로 나눈 나머지

c1 = (a1 + b1 + 받아올림)을 p로 나눈 나머지

c0 = (a0 + b0 + 받아올림)을 p로 나눈 나머지


이런식으로 계산이 되지요.

다행히도 우리는 구현할때 a_n + b_n을 2^32으로 매번 나눠줄 필요가 없습니다. 32비트 CPU에서는 2^32를 넘어가는 숫자는 자동으로 오버플로우되어 버리기 때문이지요.

그러면 받아올림이 일어났는지는 어떻게 알수 있을까요?

c2 < b2이면 받아올림이 일어났다는 것을 알수 있습니다. 받아올림이 없었다면 당연히 c2 >= b2여야할텐깐요. 하지만 아랫자리로부터 받아올림이 있는 경우에는 c2 = b2여도 받아올림이 일어난것일수 있습니다.

정리해보자면, 덧셈을 위해서는 제일 아랫자리에서부터 차례로 더해가며 받아올림을 체크하고 이를 반영하면 되겠습니다. 만약 a0 + b0에서 받아올림이 발생하는 경우는 그냥 무시하도록합시다. 그부분은 RealReal이 책임지는 부분이 아니에요. RealReal은 Pi를 계산하는게 궁극적인 목표니까요ㅋ


뺄셈도 비슷하게 알고리즘을 세워볼수 있습니다. 뺄셈의 경우는 약간 더 복잡한데요,

a가 b보다 작은 경우에는 a-b가 음수가 나오기 때문이지요. 그래서 a0 - b0에서 받아내림이 발생한다면, 우리는 c의 부호를 마이너스로 설정하고, 그 절대값을 취해서 저장해야할것입니다. 즉 실제 데이터에 저장되는 값은 b - a가 되어야한다는 말이지요. 하지만 이미 뺄셈은 a-b를 했기때문에 a-b에서 b-a를 구해야하는 방법이 필요합니다. 사람이라면 그냥 -부호 한번만 붙이면 되지만, 컴퓨터에겐 그런게 없기 때문이지요. 그래서 2의 보수를 사용합니다. 2의보수는 모든 비트를 반전하고 1을 더해주면 얻을수 있습니다.


이를 바탕으로 코드를 짜볼까요? c = a + b가 아니라 어셈블리의 add, sub연산처럼 a += b꼴의 덧셈/뺄셈 함수를 작성할겁니다.




구현을 쉽게하기 위해 인라인 함수로 도우미 함수들을 만들었습니다.

이제 실제 구현을 해봅시다.



Tags
이 댓글을 비밀 댓글로