BigInteger를 구현해보자 - 2. 정의와 생성, 파괴, 덧셈

Posted by 적분 ∫2tdt=t²+c
2009.03.29 00:47 프로그래밍/Multi precision
c++ 클래스를 이용하면 사용할 때 편리한데, 무거워지는 느낌이 있어서, 귀찮지만 c로 구현한다. 먼저 Big Integer를 위한 구조체를 다음과 같이 정의한다.


len은 dats배열의 길이를 나타내고, dats는 실제 숫자정보가 담겨있는 배열이다. (u4는 DWORD와 같다.)
자, 다음 함수는 bigint를 만들어주는 함수이다.

다음 함수는 bigint를 지워주는 함수이다.

다음 함수는 bigint의 크기를 다시 설정해주는 함수이다.

이 함수는 bigint에 u4값을 대입하는 함수이다. 제일 아래자리에 src를 넣고 나머지 윗부분은 0으로 채워주면 된다.
(누락된것을 지적해주신 dor님 감사합니다.)

이함수는 bigint에 bigint를 대입하는 함수이다.


여기까지는 설명할 것도 없이 간단하다.

이제 덧셈을 구현하기 위해 다음 함수들을 만든다.
두 u4배열을 받아서 차례대로 더해주는 함수이다. (자리올림이 발생할 경우 윗 자리로 받아올려준다, 최상위자리에서 자리올림이 발생했을경우 1을 리턴한다.)


u4배열의 가장 아래자리에만 src를 더해주는 함수이다. (자리올림이 발생할 경우 윗 자리로 받아올려준다, 최상위자리에서 자리올림이 발생했을경우 1을 리턴한다.)


자, 이제 이 함수들을 이용해서 두 bigint를 더하는 함수를 만든다.

dest의 길이와 src의 길이를 비교해서 dest의 길이가 긴 경우에는 src의 길이만큼 하위자리를 더해주고, 받아올림이 발생했을 경우 윗 자리에 더해준다. src가 더 긴 경우는 dest길이만큼만 더해주고, 넘치는 부분은 그냥 버린다. dest와 src의 길이가 n이라면, 자리올림이 하나도 발생하지 않을 경우 n회의 덧셈을 하게되고, 한 자리에서는 최대 한 번의 자리올림이 발생할 수 있으므로 최악의 경우에도 2n회의 덧셈을 하게 되므로 이 덧셈 함수의 시간 복잡도는 O(n)이 된다.


이 함수는 bigint의 특정 자리에 u4를 더하는 함수.

bigint는 다음과 같이 쓰면 된다.


Tags
이 댓글을 비밀 댓글로
  1. bigint_create로 bigint형을 만들었으면 값은 어떻게 대입시키나요??
    int a = 30;
    처럼 값을 할당하는 걸 모르겠네요 =_=
  2. 적용하는게 생각처럼 되질 않네요;
    u4를 unsigned long
    u8을 unsigned long long으로 바꿨습니다.

    bigint *a, *b, *c;
    a = (bigint*)malloc(sizeof(bigint)) ;
    b = (bigint*)malloc(sizeof(bigint)) ;
    c = (bigint*)malloc(sizeof(bigint)) ;
    로 한 후
    bigint_create(1,a);
    bigint_create(1,b);
    bigint_create(2,c);
    unsigned long x = 3000000010;
    unsigned long y = 3000000030;

    bigint_setu4(a,x);
    bigint_setu4(b,y);
    bigint_mul_i(c,a,b);
    을 했습니다.
    이 경우 c에 있는 bigint을 어떻게 화면에 출력할 수 있을까요

    c->dats에 값이 저장돼있을 듯 한데
    dats[0], dats[1]에 각각 저장이 될텐데,
    저 코드를 돌려보면
    c->dats[0]에는 3541217580
    dats[1]에는 2095475820
    이라는 정체 불명의 값이 들어가 있습니다.
    • bigint a,b,c;
      bigint_create(1, &a);
      bigint_create(1, &b);
      bigint_create(2, &c);
      bigint_setu4(&a, x);
      bigint_setu4(&b, y);
      bigint_mul_i(&c, &a, &b);
      이런식으로 사용하시면 됩니다.
  3. 질문을 계속하게 되네요;
    계산된 C값은 어떻게 볼 수 있나요? 화면에 출력을 하고 싶은데, dats에 저장된 수를 출력하는 방법이 안나와있네요
    • BigInteger를 구현해보자 8,9번에서 10진수로 출력하는 부분에 대해 설명합니다^^