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

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

1 2 3 4 5 6 7 8 9 10

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를 원래 길이로 돌려놓아야한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

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 알고리즘을 구현한 부분이다.