使用者3470650625294912019-10-16 06:58:11大數乘法基本上是乘法豎式筆算的程式碼化。
基本功能有3個
1。大數的陣列表示。
2。大數乘以小數，得到大數。
3。大數加大數，得到大數。
對於1，其實就是int陣列的每個元素儲存若干位。比如每個元素儲存4個十進位制位。［0］儲存個十百千，［1］儲存萬、十萬、百萬、千萬，諸如此類。一個數組儲存一個大數。因此需要一個額外的int變數記錄當前陣列用了多少個元素（類似於字串長度）。
對於2，“小數”指的是能用一個int儲存的數。注意這裡只限4個二進位制位（和1裡提到的位數一致）。
比如123456789這個數字，［0］儲存6789，［1］儲存2345，［2］儲存1。長度3。
這個大數乘以小數，比如9999，過程就是［0］*9999，即6789*9999=67883211，積的低四位（%10000）3211儲存到積（大數）的［0］，剩下6788的進位到［1］。
然後2345*9999=？23447655，加上剛才進位上來的6788得到23454443，其中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表示範圍。