大數(shù)相乘，快速算法？有一個快速算法來計算功率，它不是用暴力一個接一個地乘以。例如，如果你想計算2^10000，計算機將首先計算2^5000，然后計算平方，即兩個數(shù)的乘法。為了計算2^5000，計算機將

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

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