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

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

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를 넘어가는 숫자는 자동으로 오버플로우되어 버리기 때문이지요.

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

실제로 CPU 어셈블리 상에서는 add연산에서 오버플로우가 발생하면, 캐리플래그(CF)가 세트되어서, 이를 통해 오버플로우의 유무를 알아낼수 있습니다. 또한 adc연산을 이용해 받아올림을 포함한 덧셈을 구현할수 있지요. 하지만 어셈블리를 이용해 최적화하는 건 잠시 뒤로 미뤄두고 알고리즘에 열중해봅시다.

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을 더해주면 얻을수 있습니다.

왜 2의보수를 사용할까요

a0 < b0 인 경우

c0 = a0 - b0 + p 가 됩니다. (p는 역시 2^32)

그 이유는 덧셈과 마찬가지로 32비트 CPU가 모듈로 p에서 연산을 하기 때문이지요.

하지만 우리가 얻기 원하는 값은 a-b의 절대값인 b - a가 되어야합니다.

2의보수를 취하는 것은 c0, c1, c2를 p-c0, p-c1, p-c2로 바꾸고 아랫자리인 p-c2에 1을 더하는 과 동치입니다.

p-c0 = p - (a0 - b0 + p) = b0 - a0이 되고,

c1과 c2에 대해서도 마찬가지입니다.

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

/* 같은 길이의 UINT32배열을 더해주는 덧셈도우미함수 */ inline int i_adds(UINT32* dest, const UINT32* src, UINT32 len) { int carry = 0; for(UINT32 i = len - 1; i != (UINT32)(-1); --i) // i = len - 1부터 시작하고 있습니다. // 제일 낮은 자리부터 더해야하니까요. { dest[i] += src[i]; if(carry) { dest[i]++; carry = dest[i] <= src[i]; } else { carry = dest[i] < src[i]; } } return carry; } /* 같은 길이의 UINT32배열을 빼주는 덧셈도우미함수 */ inline int i_subs(UINT32* dest, const UINT32* src, UINT32 len) { int carry = 0; for(UINT32 i = len - 1; i != (UINT32)(-1); --i) { if(carry) { carry = dest[i] <= src[i]; dest[i]--; } else { carry = dest[i] < src[i]; } dest[i] -= src[i]; } return carry; } /* UINT32배열에 2의보수를 취해주는 함수 */ inline void i_cmplt(UINT32* dest, UINT32 len) { UINT32 i; /* 2의보수의 특성상 제일낮은자리에 나오는 0들은 비트반전 후 1을 더해도 0으로 남습니다. */ for(i = len - 1; i != (UINT32)(-1); --i) { if(dest[i] > 0) { dest[i]--; break; } } for(; i != (UINT32)(-1); --i) { dest[i] = ~dest[i]; } }

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

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

inline void i_RR_add(PRR dest, PRR src) { i_adds(dest->frac, src->frac, MIN(dest->size, src->size)); //최상위 자리의 받아올림은 그냥 무시합니다... //최상위 비트한테 미안하다고 한 마디 전합니다. } inline void i_RR_sub(PRR dest, PRR src) { if(i_subs(dest->frac, src->frac, MIN(dest->size, src->size))) { /*최상위 자리에서 받아내림이 발생했을 경우는 dest < src라는 의미이므로 부호를 반전하고, 2의보수를 취합니다.*/ dest->sign = ! dest->sign; i_cmplt(dest->frac, dest->size); } } void RR_add(PRR dest, PRR src) { if(dest->sign == src->sign) //부호가 같으면 덧셈연산 { i_RR_add(dest, src); } else //다르면 뺄셈연산 호출 { i_RR_sub(dest, src); } } void RR_sub(PRR dest, PRR src) { if(dest->sign == src->sign) //부호가 같으면 뺄셈연산 { i_RR_sub(dest, src); } else // 다르면 덧셈연산 호출 { i_RR_add(dest, src); } }