BigInteger를 구현해보자 - 7. 나누기

초등학생 때 배웠던 나눗셈의 알고리즘이다. big integer 나눗셈에서도 이 알고리즘을 그대로 쓴다.

void bigint_div_i(bigint *rmd, bigint *quo, const bigint *divisor) { memset(quo->dats, 0, quo->len*sizeof(u4)); u4 ns=bigint_bits(rmd); u4 ms=bigint_bits(divisor); if(ns<ms)return; if(ms==0)return; bigint temp; bigint_createcopy(&temp, divisor); bigint_shlu4(&temp, ns-ms); for(u4 i=ns-ms;(long)i>=0;--i) { if(bigint_gte_i(rmd, &temp)) { bigint_sub(rmd, &temp); quo->dats[i>>5]|=1<<(i&31); } bigint_shru4(&temp, 1); } bigint_release(&temp); }
함수 자체가 복잡하다. 나누기를 하려면 원래 수와 나누는 수가 필요하고, 몫을 받을 놈, 나머지를 받을 놈까지 필요하다. 여기서 rmd를 원래 수 겸 나머지를 받는 놈으로 하기로 하고 함수를 짰다.
먼저 원래 수와 나누려는 수의 비트 자리수를 비교해서, 나누는 수가 큰 경우 그대로 리턴해버렸다. (어차피 몫은 0이고, 원래수가 그대로 나머지가 될테니까.)
그렇지 않을 경우에는 나누는 수를 복사해서 비트수 차이만큼 왼쪽으로 시프트해준다. 위의 그림에서 109와 123456의 자리수가 3개 차이나므로 3자리 왼쪽인 1000의 자리에서부터 나누기를 시작하는 것과 같다. 이제 rmd와 temp의 크기를 비교한다. rmd가 더 크다면 quo의 그 자리는 1이 된다. (이진법에서는 한 자리가 0 또는 1이므로 0이아니면 무조건 1이다.) 그럴 경우 rmd에서 temp를 빼준다. 123에 109가 한 번 들어가므로 123에서 109를 뺀 것과 같은 이치이다. 자 이제 자리수를 하나 낮춰서 (오른쪽으로 한 번 시프트해서) 지금 했던 것을 또다시 반복한다. 그리하여 자리수가 1의 자리까지 내려올때까지 뺄셈을 반복하고 최종적으로 남는 값이 나머지가 된다.

u4 int_bits(u4 src) { u4 b=0; if(src>>16) { src=src>>16; b+=16; } if(src>>8) { src=src>>8; b+=8; } if(src>>4) { src=src>>4; b+=4; } if(src>>2) { src=src>>2; b+=2; } if(src>>1) { src=src>>1; b+=1; } return b; } u4 bigint_bits(const bigint *src) { for(u4 i=src->len-1;(long)i>=0;--i) { u4 n=src->dats[i]; if(n==0)continue; return i*32+int_bits(n); } }
이 함수는 위에서 쓰였던 bigint의 비트수를 구하는 함수이다.

n자리의 나눗셈을 한다면 최소 n번의 bigint 크기비교와 n번의 시프트, 최악의 경우 n번의 뺄셈을 해야한다. 따라서 최악의 경우의 시간복잡도는 O(n^2)이 된다.