源碼乘法豎式

1. 我想問一下用C語言寫大數乘法有什麼方法可以計算呢可以由什麼想這個計算的方法！

大數乘法基本上是乘法豎式筆算的代碼化。

基本功能有3個

1. 大數的數組表示。

2. 大數乘以小數，得到大數。

3. 大數加大數，得到大數。

對於1，其實就是int數組的每個元素存儲若干位。比如每個元素保存4個十進制位。[0]存儲個十百千，[1]存儲萬、十萬、百萬、千萬，諸如此類。一個數組保存一個大數。因此需要一個額外的int變數記錄當前數組用了多少個元素（類似於字元串長度）。

對於2，「小數」指的是能用一個int保存的數。注意這里只限4個二進制位（和1里提到的位數一致）。

比如1 2345 6789這個數字，[0]保存6789，[1]保存2345，[2]保存1。長度3。

這個大數乘以小數，比如9999，過程就是[0] * 9999，即6789 * 9999 = 6788 3211，積的低四位（%10000）3211保存到積（大數）的[0]，剩下6788的進位到[1]。

然後2345 * 9999 =2344 7655，加上剛才進位上來的6788得到2345 4443，其中4443保存到積（大數）的[1]中，2345進位到[2]。

以此類推。

對於3，基本只要一個for，對位相加然後注意進位就行了。

大數乘以大數，其實就是第一個大數先乘以第二個大數的[0]（大數乘小數，上面的2），得到一個大數A0；然後第一個大數乘以第二個大數的[1]，又得到一個大數A1……最後再將A0、A1、……加起來（也就是大數加法，上面的3）。加的時候要注意，A1的[0]要和A0的[1]對齊，A2的[0]要和A1的[1]和A0的[2]對齊……這個也和我們豎式筆算一樣。

PS：上面的演算法基本上是「10000進制數」的計算方式。如果數組的每個元素只保存1個十進制位，那就是10進制數。之所以用10000進制，純粹是程序員感覺上好一些。最有效的利用，是每個int保存2的15次方，也就是32768進制。要注意到，如果用10進制計算的話，程序的計算耗時會變成10000進制的16倍，也就是效率變成1/16。

PS2：用int數組的話，位數最多隻能是4位。因為5位數相乘可能得到11位數，超出了int表示範圍。