<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # LargeNumber - 大數字 -------- #### 問題 計算兩個整數$$ a $$和$$ b $$的加減乘除，這些數字非常大到無法用內置的$$ int64 $$、$$ float64 $$存儲。 #### 解法 將每個數字分為符號、整數區兩個部分，模擬加減乘除的運算過程得到結果。設$$ a $$有$$ n_{a} $$位，$$ b $$有$$ n_{b} $$位。將$$ 0 $$視作與正數符號相同。 #### 取反 如果$$ a = 0 $$，$$ a $$的負值為它自己，如果$$ a \ne 0 $$，$$ a $$的負值為$$ -a $$。 #### 加法 加法$$ a + b $$有以下情況： $$ (1) $$ 相同符號的$$ a, b $$相加可以把整數部分直接相加，符號與$$ a, b $$的符號相同； $$ (2) $$ 不同符號的加法$$ a + b $$可以轉化為$$ a + b = a - (-b) $$，比如$$ 12 + (-4) \rightarrow 12 - 4 $$，$$ (-1) + 8 \rightarrow (-1) - (-8) $$，然后交給減法器處理； 對于相同符號的加法$$ c = a + b $$，設$$ a[0], b[0] $$為數字的最低位（個位），用下標$$ i $$從最低位到最高位開始遍歷$$ a, b $$的每一位（$$ i = 0 \rightarrow max(n_{a}, n_{b}) + 1 $$）。初始時設$$ c $$的每一位都為$$ 0 $$。則有： $$ \begin{matrix} c[i+1] = c[i+1] + ( c[i] + a[i] + b[i] ) \div 10 \\ c[i] = ( c[i] + a[i] + b[i] ) % 10 \end{matrix} $$ 下圖演示$$ 12583 + 9127 = 21710 $$的過程：  #### 減法 減法$$ a - b $$有以下情況： $$ (1) $$ 兩正整數相減$$ a - b $$且$$ 0 \leq b \leq a $$，可以把直接相減，符號為負； $$ (2) $$ 符號不同減法$$ a - b $$可以轉化$$ a - b = a + (-b) $$，比如$$ 12 - (-4) \rightarrow 12 + 4 $$，$$ -12 - 4 \rightarrow (-12) + (-4) $$，然后交給加法器處理； $$ (3) $$ 兩正整數相減$$ a - b $$且$$ 0 \leq a \lt b $$，可以轉化為$$ a - b = -(b - a) $$，比如$$ 3 - 7 \rightarrow - (7 - 3) $$，$$ 12 - 37 \rightarrow -(37 - 12) $$； $$ (4) $$ 兩負整數相減$$ a - b $$且$$ a \lt b \lt 0 $$，可以轉化為$$ a - b = -((-a) - (-b)) $$，比如$$ (-17) - (-9) \rightarrow -(17 - 9) $$，$$ (-82) - (-37) \rightarrow -(82 - 37) $$； $$ (5) $$ 兩負整數相減$$ a - b $$且$$ b \lt a \lt 0 $$，可以轉化為$$ a - b = (-b) - (-a) $$，比如$$ (-9) - (-17) \rightarrow 9 - 17 $$，$$ (-37) - (-82) \rightarrow 82 - 37 $$； 對于兩正整數$$ 0 \leq b \leq a $$的減法$$ c = a - b $$，設$$ a[0], b[0] $$為數字的最低位（個位），用下標$$ i $$從最低位到最高位開始遍歷$$ a, b $$的每一位（$$ i = 0 \rightarrow max(n_{a}, n_{b}) + 1 $$）。初始時設$$ c $$的每一位都為$$ 0 $$。則有： $$ c[i] = \begin{cases} c[i] + a[i] - b[i] & a[i] \ge b[i] \\ c[i] + a[i] + 10 - b[i], a[i+1] = a[i+1] - 1 & a[i] \lt b[i] \end{cases} $$ 下圖演示$$ 12583 - 9127 = 4456 $$的過程：  #### 乘法 乘法$$ a \times b $$把整數部分直接相乘。若兩數字符號相同其結果的符號為正，若兩數字符號不同其結果的符號為負。 對于乘法$$ c = a \times b $$，設$$ a[0], b[0] $$為數字的最低位（個位），用下標$$ i, j $$從最低位到最高位開始分別遍歷$$ a, b $$的每一位（$$ i, j = 0 \rightarrow max(n_{a}, n_{b}) + 1 $$）。$$ i, j $$的關系是兩層循環，當$$ i = max(n_{a}, n_{b}) + 1 $$時$$ j $$加1。初始時設$$ c $$的每一位都為$$ 0 $$。則有： $$ \begin{matrix} c[j + i+1] = c[j + i+1] + ( c[j + i] + a[i] \times b[j] ) \div 10 \\ c[j + i] = ( c[j + i] + a[i] \times b[j] ) % 10 \end{matrix} $$ 下圖演示$$ 12583 \times 9127 = 114845041 $$的過程：  #### 除法 除法$$ a \div b $$有些麻煩，我們會在后面補上。 -------- #### 源碼 [LargeNumber.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Calculation/LargeNumber.h) [LargeNumber.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Calculation/LargeNumber.cpp) #### 測試 [LargeNumberTest.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Calculation/LargeNumberTest.cpp)