大數(shù)乘法用什么算法?。看髷?shù)乘法基本上就是乘法的垂直計(jì)算編碼。有三個(gè)基本功能1。大數(shù)的數(shù)組表示。2. 將大的數(shù)字乘以小數(shù)得到大的數(shù)字。3. 大數(shù)字，大數(shù)字，大數(shù)字。對于1，意味著int數(shù)組的每個(gè)元素都存

大數(shù)乘法用什么算法啊？

大數(shù)乘法基本上就是乘法的垂直計(jì)算編碼。

有三個(gè)基本功能

1。大數(shù)的數(shù)組表示。

2. 將大的數(shù)字乘以小數(shù)得到大的數(shù)字。

3. 大數(shù)字，大數(shù)字，大數(shù)字。

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

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

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

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

那么2345*9999=？23447655，加上剛才結(jié)轉(zhuǎn)的6788，得到2345443，其中4443保存在產(chǎn)品的[1]中（大數(shù)），2345結(jié)轉(zhuǎn)到[2]。

等等。

對于3，基本上只是一個(gè)For，添加位，然后注意進(jìn)位。

將一個(gè)大數(shù)乘以一個(gè)大數(shù)意味著將第一個(gè)大數(shù)乘以第二個(gè)大數(shù)的[0]（大數(shù)乘以小數(shù)點(diǎn)后，上面的2）得到一個(gè)大數(shù)A0；然后將第一個(gè)大數(shù)乘以第二個(gè)大數(shù)的[1]，得到一個(gè)大數(shù)A1，最后是A0，A1相加（即大數(shù)相加，3以上）。添加時(shí)，請注意A1的[0]應(yīng)與A0的[1]對齊，A2的[0]應(yīng)與A1的[1]和A0的[2]對齊這與我們的垂直計(jì)算相同。

PS：以上算法基本上是“萬位小數(shù)”的計(jì)算方法。如果數(shù)組的每個(gè)元素只包含一個(gè)十進(jìn)制位，那么它就是一個(gè)十進(jìn)制數(shù)。我們使用10000系統(tǒng)的原因是程序員感覺更好。最有效的省電方法是使用32762的電源。需要注意的是，如果采用十進(jìn)制進(jìn)行計(jì)算，程序的計(jì)算時(shí)間將是10000系統(tǒng)的16倍，即效率為1/16。

PS2：使用int數(shù)組時(shí)，位數(shù)最多只能為4。因?yàn)?位數(shù)相乘可能得到11位數(shù)，這超出了int的范圍。

大數(shù)相乘，快速算法？

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