【演算】大數運算 Part 1

　　在之前的作品：大數運算中，提供了我所做的大數(large)的類別函式庫，但是並沒有仔細去深入「大數運算」這個內容。在發表96年的資訊學科試題：序列長度問題解題時，我也只是將這個類別函式庫拿來用而已。

　　因此，我承諾：要在這篇文章中，將大數做個比較詳盡的介紹。由於怕一次篇幅太大(尤其又是字多圖少)，並且要考慮我的撰寫速度(似乎這才是主因)，內容我會分成幾段、分天張貼出來。


　　在一切開始之前，我們先來認識一下，什麼叫做大數？

　　由於要有效使用記憶體，許多程式語言的不同資料型態，其變數大小都是固定的。以C/C++來說，字元(char)就是1byte、整數(int)不是2byte(16位元環境)、4byte(32位元環境，目前佔多數)就是8byte(64位元環境)，浮點數就是4byte。

　　因此，變數能夠表達的範圍都是固定的。以4byte的整數來說，能表達的就只有2³²個數字。就算是目前C/C++中整數表達範圍最廣的Long型態，能表達的也只有2⁶⁴個數字。

　　運用數學對數的原理來看，對於序列長度問題122位的整數運算，顯然這些現有的資料型態已不敷使用。而為了解決這種問題，所做的"擴充整數"演算，就稱之為超長整數運算，或是大數運算。


　　一般而言，解決這種問題的方式是使用陣列(array)，利用文字拼湊的方式"拼"出一個大數來。不過實際上資料結構與運算的實作細節，其實可以說是各有不同的。

　　在之前有提過，我所使用的資料結構就不是一般的陣列，而C++標準樣板函式庫(STL)的容器：字元(char)型態的向量(vector)。每一個字元代表的是大數的每一位數。除此之外，再使用一個額外的布林(boolean)變數代表大數的正負號。如圖所示：

To Be Continued . . .