大數乘法用什么算法??？大數乘法基本上就是乘法的垂直計算編碼。有三個基本功能1。大數的數組表示。將大數乘以2。3. 大數字，大數字，大數字。對于1，意味著int數組的每個元素都存儲若干位。例如，每個元素

大數乘法用什么算法啊？

大數乘法基本上就是乘法的垂直計算編碼。

有三個基本功能

1。大數的數組表示。

將大數乘以2。

3. 大數字，大數字，大數字。

對于1，意味著int數組的每個元素都存儲若干位。例如，每個元素包含四個十進制數字。[0]商店數萬，[1]商店數萬、數十萬、百萬、千萬，依此類推。一個數組包含一個很大的數。因此需要一個額外的int變量來記錄當前數組中使用了多少元素（類似于字符串長度）。

對于2，“decimal”是指可以用int保存的數字。請注意，只有四個二進制位（與1中提到的數字一致）。

例如，對于數字123456789，[0]保存6789，[1]保存2345，[2]保存1。長度3。

這個大數乘以一個十進制數，如9999，其過程是[0]*9999，即6789*9999=67883211。乘積的下四位（ 000）3211保存到乘積的[0]（大數），6788的進位保留到[1]。

那么2345*9999=？23447655，加上剛才結轉的6788，得到2345443，其中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系統(tǒng)的原因是程序員感覺更好。最有效的用法是將每個int保存到2的15次方，即32768。需要注意的是，如果采用十進制進行計算，程序的計算時間將是10000系統(tǒng)的16倍，即效率為1/16。

PS2：使用int數組時，位數最多只能為4。因為5位數相乘可能得到11位數，這超出了int的范圍。

大數相乘，快速算法？

有一個快速算法來計算冪，它不是用蠻力一個一個地乘以。例如，如果你想計算2^10000，計算機將首先計算2^5000，然后計算平方，即兩個數的乘法。為了計算2^5000，計算機將首先計算2^2500，然后將其平方。這種算法稱為快速冪算法。對于2^n的計算，如果每次乘法的時間復雜度為O（1），則總體時間復雜度僅為O（logn）級。R一般來說，為了實現快速冪算法，我們首先對指數進行二進制表示。例如，如果要計算a的23次方，可以將23分解為16421。然后計算B=a^2，C=B^2=a^4，d=（C^2）^2=a^16。最后的結果是ABCD的乘法。但這里乘法的復雜度不是o（1），因為它是無限精度的，稱為大數乘法。大數乘法也有許多算法。最簡單的方法類似于手工計算。復雜度為O（n^2）。其它方法有分治法、復雜度O（n^1.58）、FFT法、復雜度O（n logn logn）等，在快冪大數乘法的O（logn）次中，最復雜的是最后一次，即2^5000次。前一個幾何級數的復雜度會衰減，因此總體復雜度就是最后一次計算的復雜度。如果使用FFT方法，復雜度比線性的要高一些。一般來說，它可以在計算機上隨意計算。R CPU不能全速運行，因為這個程序只使用一個內核進行計算，而您顯示的是總利用率，所以它將保持在大約四分之一的水平。R是否使用shift操作涉及Python大數操作的具體設計，我不太了解。但原則上，這也是很有可能的。如果位串用于存儲大量數字，則2^n的計算只需在數組的第n位設置1，其余可以設置為0。然后轉換成十進制是這段代碼中計算成本最高的部分。右