BigInteger를 구현해보자 - 9. 10진수로 출력하기(코드)

바로 전 글에서 알고리즘에 대해 주절주절 설명하느라고 코드를 올리지 못했다. 시프트 더하기 16..(몇이었더라)알고리즘을 쓰도록 하겠다. 그전에 먼저 bigint의 길이를 줄여주는 함수를 작성한다.

u4 bigint_shrink_i(bigint *dest) { u4 dlen=dest->len; for(u4 i=dest->len;i>0;i--) { if(dest->dats[i-1]==0)dest->len--; else break; } return dlen; }
이 함수는 bigint의 현재 길이에서 필요없는 부분(예를 들어 0000001101101011011에서 앞의 0000000 같은놈)을 잘라내어서 길이를 줄인다. 그리고 원래 길이를 리턴한다. 이 함수를 만든 이유는 계산시에 불필요한 부분을 계산하지 않고 효율성을 높이기 위해서이다. 단, 계산후에는 bigint를 원래 길이로 돌려놓아야한다.

void bigint_print(FILE *file, const bigint *src) { bigint temp; u4 srcsize=bigint_size_i(src); if(srcsize==0) { fprintf(file, "0"); return; } u4 dcsizemax=10704*srcsize/10000+1; bigint_create(dcsizemax, &temp); bigint_setu4(&temp, 0); temp.len=0; for(u4 i=srcsize-1;(long)i>=0;i--) { for(u4 bit=31;(long)bit>=0;bit--) { for(u4 j=0;j<temp.len;j++) { if(temp.dats[j]>=500000000)temp.dats[j]+=1647483648; } if(temp.len<dcsizemax)temp.len++; bigint_shlu4(&temp, 1); if(src->dats[i] & (1<<bit))temp.dats[0]|=1; bigint_shrink_i(&temp); } } u4 dcsize=bigint_size_i(&temp); fprintf(file, "%u", (unsigned int)temp.dats[dcsize-1]); for(u4 i=dcsize-2;(long)i>=0;i--) { fprintf(file, "%09u", (unsigned int)temp.dats[i]); } bigint_release(&temp); }
 제일 처음에 dcsizemax를 구하는 부분이 나오는데, 이는 src이 10^9진수로 변환했을때 몇자리가 나오는지 구해준다. 별거 없고 그냥 이 식을 이용해서 구한것이다. 소수점아래 4번째자리까지 취했는데, n이 커질수록 오차가 커진다. 따라서 1.0704로 취해서 자리가 남으면 남았지 모자라지 않게 했다.
중간에 이중루프 있는 부분이 시프트 더하기 1647483648 알고리즘을 구현한 부분이다.