BigInteger를 구현해보자 - 6. 크기비교

예전에 bigint가 0보다 큰지 작은지 같은지를 비교하는 bigint_sign함수를 만든적이 있다. 두 bigint의 대소를 비교하기 위해 빼고 부호를 확인해도 되지만, 그것보다 효율적인 방법으로 두 bigint의 대소를 비교하는 함수를 만들어보자.
그 전에 먼저 bigint가 몇자리 수인지 계산하는 함수를 만든다.

1 2 3 4 5 6 7 8 9

u4 bigint_size_i(const bigint *src) {     for(u4 i=src->len-1;(long)i>=0;--i)     {         if(src->dats[i]==0)continue;         return i+1;     }     return 0; }

특별한 알고리즘 같은것은 없고, 최고자리수부터 차례대로 내려오면서 처음으로 0이 아닌 숫자가 나올때의 자릿수를 돌려준다.

이제 두 bigint가 같은지 확인하는 함수를 만든다.

1 2 3 4 5 6 7

int bigint_eq(const bigint *xi1, const bigint *xi2) {     u4 xi1size=bigint_size_i(xi1), xi2size=bigint_size_i(xi2);     if(xi1size!=xi2size)return 0;     if(memcmp(xi1->dats, xi2->dats, sizeof(u4)*xi1size)==0)return 1;     return 0; }

먼저 두 bigint의 자릿수를 비교해서 같을 경우에는 memcmp로 비교한다. 모든 자리가 정확하게 같을 경우에 1을 돌려준다.

앞의 bigint가 뒤의 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

int bigint_gt_i(const bigint *xi1, const bigint *xi2) {     u4 xi1size=bigint_size_i(xi1), xi2size=bigint_size_i(xi2);       if(xi1size>xi2size)return 1;     if(xi1size<xi2size)return 0;     for(u4 i=xi1size;i>0;i--)     {         if(xi1->dats[i-1]>xi2->dats[i-1])return 1;         if(xi1->dats[i-1]<xi2->dats[i-1])return 0;     }     return 0; } int bigint_gte_i(const bigint *xi1, const bigint *xi2) {     u4 xi1size=bigint_size_i(xi1), xi2size=bigint_size_i(xi2);       if(xi1size>xi2size)return 1;     if(xi1size<xi2size)return 0;     for(u4 i=xi1size;i>0;i--)     {         if(xi1->dats[i-1]>xi2->dats[i-1])return 1;         if(xi1->dats[i-1]<xi2->dats[i-1])return 0;     }     return 1; }

마찬가지로 먼저 두 bigint의 자릿수를 비교해보고, 같을 경우에는 최고자리수부터 비교해 나간다.

이 네 가지 함수 모두 bigint의 len이 n이라고 했을때 시간복잡도는 최악의 경우 O(n)이 된다.
bigint_size_i 와 bigint_gt_i는 부호를 무시하고 계산한다. 부호를 고려했을 때도 별반 다를게 없으므로 생략하도록 한다.