大數四則運算 in C/C++ - part2 ( 大數的加減乘 )

開發環境:Visual C++ 2010 sp1 with FFTW
延續上一次part1的文章，這邊要介紹實際怎麼使用C進行實作，
首先，先定義一個大數的結構(參考:點我)

//可以儲存100個位數
#define BIG_SIZE 100
//數字以10進位的方式處理
#define BIG_CAP  10

typedef struct tagBig{
    int arr[BIG_SIZE]; //大數位數的陣列
    size_t dig;           // 這個數字的總位數
 bool flag ;        //是否為負數( true -> 負 )
 tagBig() {        //初始化這個變數
                //陣列內容初始化為0
  memset( arr , 0 , sizeof(size_t) * BIG_SIZE ) ;
                //這個數字為正的
  flag = false ;
 } ;
}Big;

以下為把數字以字串的型式輸入以及輸出至Console的code:

// 輸入
void big_from_string(Big * big , const char * str)
{
    int i, j, len, pwr;
    int * arr = big->arr;
    // 去前導0
    while(*str=='0' && *str!='\0') ++str;
    // 轉入大數
    len = strlen(str);
    arr[0] = 0;
    for(j=0, i=len-1; i>=0; ++j, arr[j]=0)
        for(pwr=1; pwr!=BIG_CAP && i>=0; pwr*=10, --i)
            arr[j]+=(str[i]-'0')*pwr;
    // 計算位數
    big->dig = j;
}

// 輸出
void big_print(Big * big)
{
    int i = big->dig;
 if ( big->flag )
  printf("-") ;
    if(!i) printf("0");
    else {
        int *arr = big->arr;
        printf("%d", arr[--i]); // 輸出第一位數字
        for(--i; i>=0; --i) // 輸出其他數字
            printf("%0*d", BIG_LEN, arr[i]);
    }
}

加法

承如上次所介紹的那樣直接對齊每個位數，進行相加，最後檢查進位就可以了，
這邊再加上了正.負號的判斷，假設要運算c = a + b，運算的情況就會有以下四種:
case 1: a與b都是正的，就兩數直接相加
case 2: a為負，b為正，數學表示式就會是 c = -a + b = b - a
case 3: a為正，b為負，數學表示式就會是 c = a + (-b) = a - b
case 4: a與b都是負的，數學表示式就會是 c = (-a) + (-b) = -( a + b )

以下為C的code:

//c = a + b
int big_add(const Big *a ,const Big *b, Big *c) {
 memset( (void*)c , 0 , sizeof(Big) ) ;
 // (a & !b) | (a & b) = a xor b 
 //if ( a->flag && !b->flag || !a->flag && b->flag ) {  //如果其中一個為負的
 if ( a->flag ^ b->flag ) {
  if ( a->flag ) { //如果a為負的
   //c = -a + b = b - a
   return big_sub( b , a , c ) ;
  } else { //如果b是負的
   //c = a + (-b) = a - b 
   return big_sub( a , b , c ) ;
  }
 } else {    //如果兩個都是正的或者是兩個都是負的
  size_t maxDig = ( a->dig > b->dig ) ? a->dig : b->dig ;
  size_t i = 0 , tmp ;
  int over = 0 ;
  for ( i = 0 ; i < maxDig ; i++ ) {
   //tmp = a + b + c(有進位的問題，所以要先加原本的數值)
   tmp = a->arr[i] + b->arr[i] + c->arr[i];
   //把數值算回去
   c->arr[i] = ( tmp >= BIG_CAP) ? tmp % BIG_CAP : tmp ;
   if ( i + 1 > BIG_SIZE ) {
    over = -1 ;
    break ;
   }
   //處理進位
   c->arr[i+1] = tmp / BIG_CAP ;   
  }
  //最後計算總位數，判斷有沒有進位到maxDig的下一位數
  c->dig = maxDig ;
  while ( c->arr[c->dig] && c->dig < BIG_SIZE)
   c->dig++ ;
  //c->dig = (c->arr[i + 1]) ? maxDig + 1 : maxDig ;
  c->flag = ( a->flag ) ;
  return over ;
 }
}

減法

那麼減法的就跟加法的概念差不多，沒有進位的問題，可是有某個位數不夠減的問題，
要跟比較大的位數借數字來減， 這邊再加上了正.負號的判斷，一樣假設要運算c = a - b，運算的情況就會有以下四種:
case 1: a與b都是正的，就兩數直接相減
case 2: a為負，b為正，數學表示式就會是 c = -a - b = -(a + b)
case 3: a為正，b為負，數學表示式就會是 c = a - (-b) = a + b
case 4: a與b都是負的，數學表示式就會是 c = (-a) - (-b) = - a + b

由於我個人在實作的時候比較喜歡用數字大的-數字小的
所以要先判斷兩個數字絕對值的大小，然後最後再判斷正負的問題，

以下為C的code:

//交換兩個數字
void swap( Big* a , Big* b) {
 Big tmp = *a ;
 *a = *b ;
 *b = tmp ;
}
//比較兩個數字的大小
int big_compare(const Big *a ,const Big *b ) {
 int maxDig = ( a->dig > b->dig ) ? a->dig : b->dig ;
 // (a & !b) | (a & b) = a xor b 
 //if ( !a->flag && !b->flag || a->flag && b->flag) {   //如果兩個數字都是正的或者是負的
 if ( !(a->flag ^ b->flag) ) {
  bool bothPlus = !a->flag ;
  if ( a->dig > b->dig ){
   if ( bothPlus ) return 1 ;
   else return -1 ;
  }else if ( a->dig < b->dig ) {
   if ( bothPlus ) return -1 ; 
   else return 1 ;
  }
  while ( maxDig-- ) {
   if ( a->arr[maxDig] > b->arr[maxDig] ) {
    if ( bothPlus ) return 1 ;
    else return -1 ;
   }
   else if ( a->arr[maxDig] < b->arr[maxDig] ) {
    if ( bothPlus ) return -1 ;
    else return 1 ;
   }
  }
  return 0 ;
 } else {
  if ( a->flag )  //如果a是負的
   return -1 ;
  else    //如果b是負的
   return 1 ;
 }
 
 /* else if ( a->flag && b->flag ) {   //如果兩個數字都是負的
  if ( a->dig > b->dig ) return -1 ;  //如果a的位數多於b的位數，表示b比較大
  else if ( a->dig < b->dig ) return 1 ;  //如果a的位數少於b的位數，表示a比較大
  while ( maxDig-- ) {
   if ( a->arr[maxDig] > b->arr[maxDig] ) return -1 ;
   else if ( a->arr[maxDig] < b->arr[maxDig] ) return 1 ;
  }
  return 0 ;
 }*/
 
}
//c = a - b
int big_sub(const Big *a ,const Big *b, Big *c) {
 memset( (void*)c , 0 , sizeof(Big) ) ;
 Big *_a = (Big*)malloc( sizeof( Big ) ) ;
 Big *_b = (Big*)malloc( sizeof( Big ) ) ;
 int over = 0;
 //如果其中一個為負的
 //if ( a->flag && !b->flag || !a->flag && b->flag ) {
 // (a & !b) | (a & b) = a xor b 
 if ( a->flag ^ b->flag ) {
  bool flag = false ;
  if ( !a->flag ) { // c = a - (-b) = a + b ;
   memcpy( (void*) _a , (void*) b , sizeof( Big ) ) ;
   memcpy( (void*) _b , (void*) a , sizeof( Big ) ) ;
  }
  else {  // c = -a - b = - ( a + b )
   memcpy( (void*) _a , (void*) a , sizeof( Big ) ) ;
   memcpy( (void*) _b , (void*) b , sizeof( Big ) ) ;
   flag = true ;
  }
  _a->flag = false ;
  //在減法的情況下，數值會溢位只會在兩個為同樣符號的情況下，也就是在兩數相加的情況下才會發生
  over = big_add( _a , _b , c ) ;
  c->flag = flag ;
 } else {  //如果兩數都為正/負的 ，c = a - b or c = -a - (-b)  
  int comp ;
  if ( a->flag ) { //c = -a - (-b) = -a + b = b - a
   memcpy( (void*)_b , (void*)a , sizeof(Big) ) ; //b = -a
   memcpy( (void*)_a , (void*)b , sizeof(Big) ) ; //a = b
   _a->flag = _b->flag = false ;
   comp = big_compare( _a , _b ) ;
   _a->flag = false ;
   if ( comp < 0 )  // if (abs(a) < abs(b))
    swap( _a , _b ) ;
  } else {   //c = a - b
   memcpy( (void*)_a , (void*)a , sizeof(Big) ) ;
   memcpy( (void*)_b , (void*)b , sizeof(Big) ) ;
   _a->flag = _b->flag = false ;
   comp = big_compare( _a , _b ) ;
   if ( comp < 0 )  // if (abs(a) < abs(b))
    swap( _a , _b ) ;
    //_a->flag = _b->flag = true ;
  }

  /*
    the number of a is must greator than b
    c = a - b ;
  */
  size_t maxDig = ( _a->dig > _b->dig ) ? _a->dig : _b->dig ;
  long i , tmp ;
  for ( i = 0 ; i < (long)maxDig ; i++ ) {
   tmp = _a->arr[i] - _b->arr[i] + c->arr[i] ;
   if ( tmp >= 0 ) 
    c->arr[i] = tmp ;
   else {
    c->arr[i] = BIG_CAP + tmp ;
    c->arr[i+1]-- ; //next carry -= 1
    
   }
  }

  //if ( comp < 0 )
  // c->flag = true ;
  //else
  // c->flag = false ;

  c->flag = ( comp < 0 ) ;
  
  c->dig = maxDig ;
  while ( c->arr[c->dig-1] == 0 && c->dig > 0) 
   c->dig -- ;
 }
 free( (void*)_a ) ;
 free( (void*)_b ) ;
 return over ;
}

乘法

假設兩個數字要相乘 99 ,  12，在直式的乘法裡面:
      99
x    12
-----------
    198(r1)
+  99(r2)
-----------
  1188

由上面的式子所得知，乘數以最低到最高的位數來乘乘數的每一個位數(上面標的rn)，
每乘一round之後並且把往左位移一次相加(例如: r1+r2(左移一個位數))，
計算出來的結果再進行進位的判斷，就可以得到所求，
這邊再加上了正.負號的判斷，
假設要運算c = a * b，運算的情況就會有以下四種:
case 1: a與b都是正的，相乘結果就會是正數
case 2: a為負，b為正，相乘結果就會是負數
case 3: a為正，b為負，相乘結果就會是負數
case 4: a與b都是負的，相乘結果就會是正數


以下為C的code:

//c = a * b
int big_mul(const Big *a ,const Big *b, Big *c) {
 memset( (void*)c , 0 , sizeof(Big) ) ;
 bool flag = a->flag ^ b->flag ;
 //sign check
 //if ( !a->flag && b->flag || a->flag && !b->flag )
 // flag = true ;

 size_t i , j , _x , tmp ;
 // Time complex : O( length(a) * length(b) )
 for ( i = 0 ; i < a->dig ; i++ ) {
  if ( !a->arr[i] ) continue ;
  _x = a->arr[i] ;
  for ( j = 0 ; j < b->dig ; j++ ) {
   tmp = c->arr[i+j] + _x * b->arr[j] ;
   c->arr[i+j] = tmp % BIG_CAP ;
   //判斷overflow
   if ( i+j+1 > BIG_SIZE ) return -1 ;
   c->arr[i+j+1] += tmp / BIG_CAP ;

  }
 }
 c->flag = flag ;
 c->dig = a->dig * b->dig ;
 while ( c->arr[c->dig] )
  c->dig-- ;
 return 0 ;
}

在此先暫停一下，因為除法概念上會比較麻煩，下一篇再來講解....

To be continued...