超长整数运算

說明

基於記憶體的有效運用，程式語言中規定了各種不同的資料型態，也因此變數所可以表達的最大整數受到限制，例如 123456789123456789這樣的整數就不可能儲存在long變數中（例如C/C++等），我們稱這為long數，這邊翻為超長整數（避免與資 料型態的長整數翻譯混淆），或俗稱大數運算。

解法

一個變數無法表示超長整數，則就使用多個變數，當然這使用陣列最為方便，假設程式語言的最大資料型態可以儲存至65535的數好了，為了計算方便及符合使用十進位制的習慣，讓每一個陣列元素可以儲存四個位數，也就是0到9999的數，例如：


很多人問到如何計算像50!這樣的問題，解法就是使用程式中的乘法函式，至於要算到多大，就看需求了。

如果您使用的是Java，那麼在java.lang下有BigInteger與BigDecimal可以直接進行大數運算。

由於使用陣列來儲存數值，關於數值在運算時的加減乘除等各種運算、位數的進位或借位就必須自行定義，加、減、乘都是由低位數開始運算，而除法則是由高位數開始運算，這邊直接提供加減乘除運算的函式供作參考，以下的N為陣列長度。

實作

• C

void add(int *a, int *b, int *c) {
   int i, carry = 0;

   for(i = N - 1; i >= 0; i--) {
       c[i] = a[i] + b[i] + carry;
       if(c[i] < 10000)
           carry = 0;
       else { // 進位
           c[i] = c[i] - 10000;
           carry = 1;
       }
   }
}

void sub(int *a, int *b, int *c) {
   int i, borrow = 0;

   for(i = N - 1; i >= 0; i--) {
       c[i] = a[i] - b[i] - borrow;
       if(c[i] >= 0)
           borrow = 0;
       else { // 借位
           c[i] = c[i] + 10000;
           borrow = 1;
       }
   }
}

void mul(int *a, int b, int *c) { // b 為乘數
   int i, tmp, carry = 0;

   for(i = N - 1; i >=0; i--) {
       tmp = a[i] * b + carry;
       c[i] = tmp % 10000;   
       carry = tmp / 10000;
   }
}

void div(int *a, int b, int *c) {  // b 為除數
   int i, tmp, remain = 0;

   for(i = 0; i < N; i++) {
       tmp = a[i] + remain;
       c[i] = tmp / b;
       remain = (tmp % b) * 10000;
   }
}

• Java

public class BigNumber {
   public static int[] add(int[] a, int[] b) {
       int carry = 0;
       int[] c = new int[a.length];

       for(int i = a.length - 1; i >= 0; i--) {
           c[i] = a[i] + b[i] + carry;
           if(c[i] < 10000)
               carry = 0;
           else { // 進位
               c[i] = c[i] - 10000;
               carry = 1;
           }
       }
      
       return c;
   }

   public static int[] sub(int[] a, int[] b) {
       int borrow = 0;
       int[] c = new int[a.length];
      
       for(int i = a.length - 1; i >= 0; i--) {
           c[i] = a[i] - b[i] - borrow;
           if(c[i] >= 0)
               borrow = 0;
           else { // 借位
               c[i] = c[i] + 10000;
               borrow = 1;
           }
       }
      
       return c;
   }

   public static int[] mul(int[] a, int b) { // b 為乘數
       int carry = 0;
       int[] c = new int[a.length];
      
       for(int i = a.length - 1; i >=0; i--) {
           int tmp = a[i] * b + carry;
           c[i] = tmp % 10000;   
           carry = tmp / 10000;
       }
      
       return c;
   }

   public static int[] div(int[] a, int b) {  // b 為除數
       int remain = 0;
       int[] c = new int[a.length];

       for(int i = 0; i < a.length; i++) {
           int tmp = a[i] + remain;
           c[i] = tmp / b;
           remain = (tmp % b) * 10000;
       }
      
       return c;
   }
  
   public static void main(String[] args) {
       int[] a = {1234, 5678, 9910, 1923, 1124};
       int[] b = {1234, 5678, 9910, 1923, 1124};
       int[] c = BigNumber.add(a, b);
      
       for(int i = 0; i < c.length; i++) {
           System.out.print(c[i]);
       }
       System.out.println();
   }
}