大數四則運算 in C/C++ - part1 ( 序 )

開發環境:Visual C++ 2010 sp1 with FFTW


在電腦中，無法將一個很大的數字存入一個變數裡面，
譬如說: 2^100000，這樣子的數字完全無法使用如:int,float,double,long,long long...來儲存，
那麼勢必要把這一大串的數字擺放於陣列，
要怎麼擺放呢?這裡有一個很簡單的方式，
以10進位的數字來講，把每一個位數(digit)都用一個int來儲存，
例如: 12345(in decimal) 以陣列的方式儲存就會是:(以最高位元為優先)

int x[] = { 1 , 2 , 3 , 4 , 5 } ;

也可以把數值以最低為元優先而存成:

int x[] = { 5 , 4 , 3 , 2 , 1 } ;

以我個人會是以最低為元優先來做儲存，主要原因在於做四則運算時要對齊位元的位置，
以及進位的問題，
假設有兩個數字要相加，分別為: 11111與99999，
以最高位元為優先的表示方法就會是:

int a[6] = { 1 , 1 , 1 , 1 , 1 , 0} ;
int b[6] = { 9 , 9 , 9 , 9 , 9 , 0} ;

假設 a_len 為a的位元數，b_len 為a的位元數， 那兩數相加的時候，code大概要寫成

int maxCarry = 0 ;
int tmp = a_len ;
while ( a_len-- >= 0 ) {
 if ( b_len -- >= 0 )
  a[a_len] += b[b_len] ;
 if ( a[a_len] > 9 ) {
  if ( a_len > 0 ) { //如果陣列前面還有位置可以存
   a[a_len-1] += a[a_len] / 10 ; 
  } else {  //如果沒有了，暫存到另一個變數
   maxCarry = a[a_len] / 10 ;
  }
  a[a_len] %= 10 ;
 }
}
if ( maxCarry ) { //如果最後還有進位
 //把原先a的資料存到最大位數的後面那個位數
 memset( a + 1 , a , tmp  ) ;
 //將進位數字填回去第一個位數
 a[0] = maxCarry ;
}

然而，使用最低位元優先的時候，code大概可以寫成

//Given a_len >= b_len
for ( int i = 0 ; i < a_len ; i++ ) {
 a[i] += b[i] ;
 if ( a[i] > 9 ) {
  a[i+1] += a[i] / 10 ;
  a[i] %= 10 ;
 }
}

現在來比較兩邊的code，上面的code要多一個if來判斷最後的進位，
而且最後進位的時候還要做記憶體搬移的工作，基於以上的原因，
往後我寫的大數程式碼都會是以"最低位元優先"的儲存方式來撰寫。
 P.S.: 三點了，該是好孩子上床睡覺的時候了 XD


To be continued...