電腦程式在進行整數數值計算的時候,會受到變數型別的記憶體空間使用大小而有數值表示範圍的限制,所以當遇到過長的數值時,就無法正常地運算出結果。



以一個8位元的整數來說,它最多可以表示28種不同的整數。如果是無號整數的話,數值表示範圍就是0 ~ 255,如果是有號整數的話,數值表示範圍就是-128 ~ 127。以一個16位元的整數來說,它最多可以表示216種不同的整數,如果是無號整數的話,數值表示範圍就是0 ~ 65535;如果是有號整數的話,數值表示範圍就是-32768 ~ 32767。依此類推,有的程式語言(例如Java)內建的基本整數型別最大是64位元,而有的程式語言(例如Rust)內建的基本整數型別最大是128位元。不過即便是128位元的整數,最多也只能表示39個位數(38個位數以下才是安全範圍)而已,還算不上是本篇文章要介紹的「大數」。

事實上,很多程式語言的標準函式庫已有內建超長整數的運算功能,我們只需要按照API文件來調用就好了。不過如果只關心加、減、乘、除運算的話,其實它們也沒有到難以實作的地步,我們還是可以嘗試自己動手寫程式實作看看,來增進對數值計算的認識。

在開始想辦法撰寫程式前,先來簡單了解一下數字系統(Numeral System)吧!

數字系統(Numeral System)

數字系統就是表示數字的方法。常用的表示方法有十進制、二進制、八進制和十六進制。

進制(進位)表示法

所謂進制(進位)表示法,就是在定義一個數在大於或等於某數的時候必須進位。好比我們最常用的十進制(十進位),當#{{9 + 1}}#要用數字表示為「十」的時候,因為#{{9 + 1}}#已經等於「十」,必須再往左進位,因此表示為#{{10}}#。如果是八進制要表示「十」,可以看成#{{7+1+2}}#,#{{7+1}}#等於「八」,必須要進位,表示為#{{10}}#,最後再加#{{2}}#的話就是#{{12}}#。

以上的解釋其實還是很模糊,來看看進制的兩個通式吧!

通式一:一般式

#{{{
M_r = (a_n a_{n-1} \dots a_1 a_0 \text{ . } a_{-1} \dots a_{-(m - 1)} a_{-m})_r
}}}#

上面公式中,各代數的定義如下:

  • #{{M}}#:所要表示的數值。
  • #{{r}}#:底數(radix)。十進制以10為底;八進制以8為底,依此類推。
  • #{{n}}#:最高位的位數。(小數點前從0開始算)
  • #{{a}}#:每位數的數值。
  • #{{m}}#:小數點後最低位的位數。(小數點後從1開始算)
通式二:加權式

#{{{
M_r = a_n r^n + \dots + a_1 r^1 + a_0 r^0 + a_{-1} r^{-1} + \dots + a_{-m} r^{-m}
}}}#

上面公式中,各代數的定義同上面的通式一。

任何進制皆可藉由加權式將值轉換為十進制。例如有個八進制的數表示為173(8),那麼他的加權式就可以寫成:

#{{{
173_{(8)} = 1 \times 8^2 + 7 \times 8^1 + 3 \times 8^0 = 123_{(10)}
}}}#

常用進制

十進制(Decimal)

十進制為我們最常用的進制系統,日常生活中所見的數字幾乎都是以十進制來表示,例如金錢的數目、年齡、年份、數學。一般來說,未特別指定其進制的數值都會當作是十進制。十進制數值的表示方法如:789、789D、(789)10、789(10)

二進制(Binary)

在數位的世界中常利用高電位(hi)和低電位(lo)來當作邏輯訊號(沒有電位稱為高阻抗)。正邏輯1表示高電位,0表示低電位;負邏輯1表示低電位,0表示高電位。在一般情況下我們都是使用正邏輯。由於電子電路中的邏輯只有高電位1和低電位0,故運算方式採用只有10的二進制系統。二進制數值的表示方法如:10110B、(10110)2、10110(2)、0b10110。

八進制(Octal)

為了方便讓程式設計者控制記憶體的內容,可以將二進制數的3個連續的數字合併為1個(例如:10110(2)=26(8)),用8進制來表示,才不用輸入一大串的01。八進制數值的表示方法如:567O、(567)8、567(8)、0o567。

十六進制(Hexadecimal)

將二進制數的4個連續的數字合併為1個,即為十六進制。十六進制系統可以用在許多地方,除了前面說的可以簡化二進制方便程式設計者控制記憶體的內容外,也可以用於色碼(例如:#CFE0EA)。

十六進制的每個位數的最大值為「十五」,但一個阿拉伯數字並沒有「十五」這種數值,故在9之後的數值會以英文字母來代替,例如「十」會寫成A、「十一」寫成B、「十二」寫成C、「十三」寫成D、「十四」寫成E、「十五」寫成F,依此類推。十六進制數值的表示方法如:3A2BH、(3A2B)16、3A2B(16)、0x3A2B。

例如要利用十六進制來指定某個16位元(2個位元組)的記憶體存入1010101010101010B(1、0交錯)的數值,使用二進制來表示會顯得很冗長,而且容易寫錯,這時可以改存入AAAAH(1010(2)=A(16)),會清楚很多,且不易寫錯。

進制換算

為了能在撰寫程式時在適當的時機運用各個進制來表示數值,學會進制的轉換是必須的。

十進制轉任何進制

十進制要轉換成其他進制,整數部份可以利用連除法(可用短除法)來輕鬆達成,小數部份則需使用連乘法。

例題一:68.375轉2進制

首先將整數68做連除法(68為被除數、2為除數)運算,需將餘數(remainder)寫出來,除到被除數比除數小為止。

#{{{
\begin{eqnarray}
{68 \over 2} = 34 &\text{ ...}& 0 \nonumber \\
{34 \over 2} = 17 &\text{ ...}& 0 \nonumber \\
{17 \over 2} = 8 &\text{ ...}& 1 \nonumber \\
{8 \over 2} = 4 &\text{ ...}& 0 \nonumber \\
{4 \over 2} = 2 &\text{ ...}& 0 \nonumber \\
{2 \over 2} = 1 &\text{ ...}& 0
\end{eqnarray}
}}}#

此時只要將運算結果倒過來取最後的商(quotient)和所有餘數值即可得到68的2進制值:

#{{{
68 = 1000100_{(2)}
}}}#

整數的部份轉好後再來是小數的部份,將0.375的小數部份做連乘(乘以2)計算,直到小數部份為0

#{{{
\begin{eqnarray}
0.375 \times 2 &= 0&.75 \nonumber \\
0.75 \times 2 &= 1&.5 \nonumber \\
0.5 \times 2 &= 1&.0
\end{eqnarray}
}}}#

此時只要將運算結果按照順序取運算後的整數值即可得到0.375的2進制值:

#{{{
0.375 = 0.011_{(2)}
}}}#

合併上面的結果:

#{{{
68.375 = 1000100.011_{(2)}
}}}#

例題二:75.625轉16進制

首先將整數75做連除法(75為被除數、16為除數)運算,需將餘數寫出來,除到被除數比除數小為止。

#{{{
\begin{eqnarray}
{75 \over 16} = 4 &\text{ ...}& 11
\end{eqnarray}
}}}#

可知整數部份:#{{75 = 4B_{(16)}}}#。

整數的部份轉好後再來是小數的部份,將0.625的小數部份做連乘(乘以16)計算,直到小數部份為0

#{{{
\begin{eqnarray}
0.625 \times 16 &= 10&
\end{eqnarray}
}}}#

可知小數部份:#{{0.625 = A_{(16)}}}#。

合併上面的結果:

#{{{
75.625 = 4B.A_{(16)}
}}}#

任何進制轉十進制

套用前面提到的加權式即可轉換。

例題一:1000100.011(2)轉十進制

#{{{
\begin{eqnarray}
1000100.011_{(2)} &=& 1 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 \nonumber \\
&\text{ }& + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 \nonumber \\
&\text{ }& + 0 \times 2^0 + 0 \times 2^{-1} + 1 \times 2^{-2} \nonumber \\
&\text{ }& + 1 \times 2^{-3} \nonumber \\
&=& 64 + 4 + 0.25 + 0.125 = 68.375
\end{eqnarray}
}}}#

例題二:4B.A(16)轉十進制

#{{{
\begin{eqnarray}
4B.A_{(16)} &=& 4 \times 16^1 + 11 \times 16^0 + 10 \times 16^{-1} \nonumber \\
&=& 64 + 11 + 0.625 = 75.625
\end{eqnarray}
}}}#

進制的加減法

平常我們算數學都是使用十進制來計算,在加法若遇到大於或等於10的情況必須要進位;減法若遇到小於0的情況必須要借位。這個規則在其他進制也是一樣,只不過加權值不同罷了。

加法

直接舉個例子來講解:

#{{{ 10111_{(2)} + 1011_{(2)} }}}#

從最小的位數(第0位)開始相加,#{{ 1 + 1 \geq 2}}#,因此進位,可以把式子寫成:

#{{{ 10110_{(2)} + 1000_{(2)} + 10_{(2)} }}}#

往左一個位數(第1位),#{{1 + 0 + 1 \geq 2}}#,因此進位,可以把式子寫成:

#{{{ 10100_{(2)} + 1000_{(2)} + 100_{(2)} }}}#

再左一個位數(第2位),#{{1 + 0 + 1 \geq 2}}#,因此進位,可以把式子寫成:

#{{{ 10000_{(2)} + 1000_{(2)} + 1000_{(2)} }}}#

再左一個位數(第3位),#{{0 + 1 + 1 \geq 2}}#,因此進位,可以把式子寫成:

#{{{ 10000_{(2)} + 10000_{(2)} }}}#

再左一個位數(第4位),#{{1 + 1 \geq 2}}#,因此進位,故最後算出來的結果為#{{ 100000_{(2)} }}#。

減法

直接舉個例子來講解:

#{{{ 10111_{(2)} - 1001_{(2)} }}}#

從最小的位數(第0位)開始相減,#{{ 1 - 1 = 0 }}#,可以把式子寫成:

#{{{ 10110_{(2)} - 1000_{(2)} }}}#

往左一個位數(第1位),#{{1 - 0 = 1}}#,式子不變。再往左一個位數(第2位),#{{1 - 0 = 1}}#,式子不變。

再往左一個位數(第3位),#{{0 - 1 <0}}#,因此借位,可以把式子寫成: #{{{ 1110_{(2)} + 1000_{(2)} - 1000_{(2)} }}}# 故最後算出來的結果為#{{ 1110_{(2)} }}#。

補數(complement)

任何#{{r}}#進制均有「#{{r-1}}#的補數」與「#{{r}}#的補數」。

例如一個二進制數,擁有1的補數(1's complement)和2的補數(2's complement);一個十進制數,擁有9的補數(9's complement)和10的補數(10's complement)。

#{{r - 1}}#的補數

計算一個#{{r}}#進制數的#{{r - 1}}#的補數,只要將該數的每個位數分別當作減數,並以#{{r - 1}}#做為被減數來計算補數的每個位數。將#{{r}}#進制數與其#{{r - 1}}#的補數相加所得到的數,每個位數都會是#{{r - 1}}#。

二進制的1的補數

計算一個二進制數的1的補數,只要將該數的「#{{0}}#變#{{1}}#、#{{1}}#變#{{0}}#」就好了。

例如1100(2)的1的補數為0011(2)

十進制的9的補數

計算一個十進制數的9的補數,只要分別用#{{9}}#減去該數的每個位數,把計算出來的每個差值(difference)作為補數的每個位數。

例如123456789的9的補數為876543210

#{{r}}#的補數

把#{{r}}#進制數的#{{r - 1}}#的補數再加#{{1}}#,就是#{{r}}#的補數。不過還有個比較快的計算方式,那就是從#{{r}}#進制數最小的位數開始(往左),「遇#{{0}}#寫#{{0}}#,用#{{r - 1}}#減去第一個非#{{0}}#的位數再加#{{1}}#,然後用#{{r - 1}}#減去之後的每個位數」。

將#{{r}}#進制數與其#{{r}}#的補數相加所得到的數,每個位元都會是#{{0}}#。

二進制的2的補數

計算一個二進制數的2的補數,只要先從最小位元(LSB, Last Significant Bit)開始(往左),「遇#{{0}}#寫#{{0}}#,遇第一個#{{1}}#寫#{{1}}#,之後的位元#{{0}}#變#{{1}}#、#{{1}}#變#{{0}}#」。

例如10110100(2)的2的補數為01001100(2)

十進制的10的補數

計算一個十進制數的2的補數,只要先從個位數開始(往左),「遇#{{0}}#寫#{{0}}#,用#{{9}}#減去第一個非#{{0}}#的位數再加#{{1}}#,然後用#{{9}}#減去之後的每個位數」。

例如9876543210的10的補數為0123456790(2)

用#{{r}}#的補數表示負數

補數觀念最常用於二進制系統,用以進行有號(signed)數的計算。以3位元整數為例,若我們把最大位元(MSB, Most Significant Bit)定義為整數的正負號,0為正數;1為負數,則這3位元整數可以表示的數值如下:

#{{{
\begin{eqnarray}
000_{(2)} &=& +0 \nonumber \\
001_{(2)} &=& +1 \nonumber \\
010_{(2)} &=& +2 \nonumber \\
011_{(2)} &=& +3 \nonumber \\
100_{(2)} &=& -0 \nonumber \\
101_{(2)} &=& -1 \nonumber \\
110_{(2)} &=& -2 \nonumber \\
111_{(2)} &=& -3
\end{eqnarray}
}}}#

不過這樣的表示方式顯然無法進行加減法計算。例如#{{ 1 + (-1) = 001_{(2)} + 101_{(2)} = 110_{(2)} }}#,但#{{ 110_{(2)} \neq 0 }}#。

所以我們要用補數來表示某最大位元為0的數的負數。利用2的補數,可以讓3位元整數表示的數值如下:

#{{{
\begin{eqnarray}
000_{(2)} &=& +0 \nonumber \\
001_{(2)} &=& +1 \nonumber \\
010_{(2)} &=& +2 \nonumber \\
011_{(2)} &=& +3 \nonumber \\
100_{(2)} &=& -4 \nonumber \\
101_{(2)} &=& -3 \nonumber \\
110_{(2)} &=& -2 \nonumber \\
111_{(2)} &=& -1
\end{eqnarray}
}}}#

如此一來就可以正常地進行加減法計算了!例如:

#{{{ 1 + (-1) = 001_{(2)} + 111_{(2)} = 000_{(2)} = 0 }}}#

#{{{ 1 + (-3) = 001_{(2)} + 101_{(2)} = 110_{(2)} = -2 }}}#

#{{{ (-1) + (-3) = 111_{(2)} + 101_{(2)} = 100_{(2)} = -4 }}}#

十進制整數的大數運算

了解進制轉換和補數的概念後,就可以先來實作看看十進制整數的大數運算的程式啦!

我們可以利用程式語言的基本整數型別組成陣列,整個陣列用來表示一個整數。陣列的每個元素表示整數的每個「位數」,每個元素的最大值再加1表示這個整數的「底數」。陣列最左端(索引0的位置)為最大位數,最右端為最小位數。

以十進制來舉例,像是以下長度為10的陣列:

索引    0   1   2   3   4   5   6   7   8   9
數值    1   2   3   4   5   6   7   8   9   0

這個陣列所代表的整數即為1234567890

如果我們想要讓陣列能夠表示更長的整數,除了可以增加陣列的長度外,也可以增加陣列的每個元素所能儲存的數值長度。例如讓陣列的每個元素,最多都可以存十進制的兩個位數的數值,那麼這個陣列就等同於是使用一百進制,如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   12  34  56  78  90   1   2   3   4   5

以上陣列所代表的整數即為12345678900102030405

例如讓陣列的每個元素,最多都可以存十進制的三個位數的數值,那麼這個陣列就等同於是使用一千進制,如下:

索引    0   1   2   3   4   5   6   7   8   9
數值  123 456 789   1   2   3   4   5   6   7

以上陣列所代表的整數即為123456789001002003004005006007

若我們的陣列元素是32位元整數的話,最多可以安全地儲存十進制的9個位數的數值,不過考慮到在乘法運算的時候,#{{a}}#個位數的值乘上#{{b}}#個位數的值最多會有#{{a + b}}#個位數,為了避免溢位,每個元素最多就存十進制的4個位數的數值就好(也是可以存更多,只是乘法運算的時候要另外轉型就是了),也就是要使用一萬進位。然而,如果沒有乘法運算,只有加、減和除法的話,可以讓每個元素最多存十進制的9個位數的數值,這樣效能會比較好。

為了讓程式維護起來更方便,且更容易理解,我們將一個元素最多要儲存多少個十進制的位數和陣列的元素數量設成常數,並且如果方便的話,也定義出我們自己的BigInteger型別。程式碼如下:

如此一來,我們的大數運算程式能夠支援的十進制的最大位數就會是DIGIT_NUMBER_PER_ELEMENT * NUMBER_OF_ELEMENTS。如上面程式碼定義的值,就會是400位!

計算補數

補數的計算比較單純,可以先實作這個功能。根據上面的數字系統介紹,為了要讓我們的陣列可以被用來表示負數,我們需要去計算這個陣列的「#{{r}}#的補數」,也就是從#{{r}}#進制數最小的位數開始(往左),「遇#{{0}}#寫#{{0}}#,用#{{r - 1}}#減去第一個非#{{0}}#的位數再加1,然後用#{{r - 1}}#減去之後的每個位數」。至於這個「#{{r - 1}}#」就是MAX_VALUE_PER_ELEMENT

程式碼如下:

用字串表示整數(將陣列轉成整數字串)

為了方便我們知道陣列代表的整數數值到底是什麼,我們可以撰寫一個轉換功能來將陣列轉成整數,不過由於轉換出來的整數可能會很長,所以要用字串來表示(整數字串)。

一開始我們要先判斷這個陣列到底是不是負數,只要判斷陣列的最大位數有沒有超過MAX_VALUE_PER_ELEMENT的一半(可用>> 1來當作「除以2」的運算)即可。如果超過了就是負數,要先取一次補數(也就是轉正數)之後,讓字串以負號開頭,再用補數繼續轉出整數字串。

至於轉換的方式就是先從最大位數開始看,遇0就跳過,直到遇到非0的位數就填入字串。接下來的位數不管是不是0,都要填入字串,在填入之前要先以0來補不足的十進制的位數,因為一個元素就是要有DIGIT_NUMBER_PER_ELEMENT個十進制的位數。如果都沒遇到非0的位數,就回傳字串0

程式碼如下:

將整數字串轉成整數

為了方便將整數甚至是很長的整數轉成陣列,我們可以撰寫一個轉換功能來將整數字串轉成整數。

首先要先去判斷字串是否以負號-開頭,如果是的話,就記錄下來,並把-移除掉,當作正數來轉換,最後再去計算結果的補數就是負數了。

至於轉換的方式就是從字串結尾開始,讀取最多DIGIT_NUMBER_PER_ELEMENT個字元(長度最大為DIGIT_NUMBER_PER_ELEMENT的子字串),將子字串轉成整數存進陣列對應的索引位置中即可。

程式碼如下:

加法

計算兩陣列的相加結果很簡單,根據前面介紹的補數加減法概念,我們完全不需要去管傳進來的陣列所代表的整數到底是正是負,直接進行加法就對了。

至於加法的方式,就是從最小位數開始,把兩陣列相同索引位置的元素相加,如果前次的加法運算有進位,還需要再將結果加1,最後再重新記錄有沒有進位。

程式碼如下:

減法

計算兩陣列的相加結果很簡單,根據前面介紹的補數加減法概念,我們完全不需要去管傳進來的陣列所代表的整數到底是正是負,直接進行減法就對了。

減法有兩種實作方式,一種是將a - bb取補數b'後,去計算a + b'(利用前面實作的add方法),因為b' = -b。不過這種方式的效能會比較不好一點,而且當b是「最小負數」時,會計算錯誤。

採取另一種方式會比較好。就是從最小位數開始,把兩陣列相同索引位置的元素相減,如果前次的加法運算有借位,還需要再將結果減1(減數加1),最後再重新記錄有沒有借位。

程式碼如下:

乘法

計算ab兩陣列的相乘的結果,即a * b。要從最小位數開始把b的每個位數分別與a的所有位數相乘(一樣從最小位數開始),並將結果加總。這邊比較需要注意到的是,若以十位數乘上百位數,則結果會是從千位數起跳,換句話說,b的第dy位數(0是最大位數)乘上a的第dx位數,所得的結果要加到乘積(product)的第NUMBER_OF_ELEMENTS - 1 - ((NUMBER_OF_ELEMENTS - 1 - dx) + (NUMBER_OF_ELEMENTS - 1 - dy))位,以d來表示這個式子算出來的值好了。如果這個d為負值,表示位數乘起來會超出陣列所能代表的整數的最大位數,就不必再去計算位數相乘的結果了。

位數相乘後還要加上前次相乘的進位結果,再加上目前已計算的乘積的第d位,最後再重新記錄進位的值,

在開始進行乘法計算前,要先判斷兩陣列的代表的整數是否為負數,如果是的話就要先轉補數,並且預測相乘結果會是正數還是負數,如果是負數的話,就必須還要再轉一次補數。至於要怎麼預測結果的正負,很簡單,遵循「正負得負、負負得正」的規律就好了。

程式碼如下:

除法

除法的實作會比較困難一點,我們會需要先實作一個比較兩個陣列的大小的功能。比較大小時可以不必去管它們代表的整數是正的還是負的,都當成正的即可。

程式碼如下:

接下來就是除法的程式實作了。一開始和乘法一樣要先把代表負整數的陣列轉補數,並預測結果是正的還是負的。

接著要持續把除數(b陣列)往左位移一個位數,找出最大但不超過被除數(a陣列)時的位移結果,以t來表示這個除數位移後的陣列,並以d來表示往左位移的次數好了。

若被除數等於t,除商(quotient)的第NUMBER_OF_ELEMENTS - d - 1位(0為最大位數)即為1,至此除商的結果就算完了。

若被除數大於t,要讓被除數持續與t相減,直到被除數小於t,減的次數即為除商的第NUMBER_OF_ELEMENTS - d - 1位。若在減的過程中,被除數等於t,則除商的第NUMBER_OF_ELEMENTS - d - 1位是減的次數再加1,至此除商的結果就算完了。

就重複上述步驟,若剩餘的被除數比除數小,除商的結果就算完了。

如果一開始預測的結果為負數的話,結果就必須要把除商的結果再轉一次補數。

任意進制整數的大數運算

事實上我們已經實作出了「任意進制」整數的大數運算了。只要把上面實作的程式的DIGIT_NUMBER_PER_ELEMENT常數刪掉,直接把陣列元素的最大值填進MAX_VALUE_PER_ELEMENT常數中即可。例如要十六進制,就直接將MAX_VALUE_PER_ELEMENT常數設為15

當然,修改為不是以10n為基底的進制的話,就不能沿用先前實作的「字串與整數互相轉換」的功能了。這也就是為什麼一開始要以計算「十進制整數」為目的來實作這個程式的原因,這樣偵錯起來才方便嘛!