怎么快速計(jì)算乘法？

計(jì)算乘方是有快速算法的，并不是一個(gè)一個(gè)蠻力乘上去的。比如想算2^10000，計(jì)算機(jī)先算2^5000，再算一次平方，即兩個(gè)數(shù)的乘法。而為了計(jì)算2^5000，計(jì)算機(jī)會(huì)先算2^2500再算一次平方。這個(gè)算法叫快速冪算法，對(duì)于2^N的計(jì)算，如果認(rèn)為每次乘法的時(shí)間復(fù)雜度是O(1)的話，那整體的時(shí)間復(fù)雜度只有O(logN)級(jí)別。

一般來(lái)說(shuō)，為了實(shí)現(xiàn)快速冪算法，首先把指數(shù)做二進(jìn)制表示，比如你要算A的23次方，可以把23分解為16+4+2+1。然后計(jì)算B=A^2，C=B^2=A^4，D=(C^2)^2=A^16。最終結(jié)果為ABCD相乘。

但這里乘法的復(fù)雜度并不是O(1)，因?yàn)樗菬o(wú)限精度的，也就是所謂的大數(shù)乘法。大數(shù)乘法也有很多算法，最樸素的，類似手算的方法，復(fù)雜度是O(N^2)，其他一些方法有分治法，復(fù)雜度O(N^1.58)，F(xiàn)FT方法，復(fù)雜度O(N logN loglogN)等。快速冪的O(logN)次大數(shù)乘法中，最復(fù)雜的只有最后一次，也就是2^5000的那次，前面的復(fù)雜度幾何級(jí)數(shù)衰減，所以整體復(fù)雜度也就是最后一次計(jì)算的復(fù)雜度。如果你用FFT方法的話，復(fù)雜度也就是比線性多了一點(diǎn)點(diǎn)，一般計(jì)算機(jī)上隨便算算就出來(lái)了。

CPU沒(méi)有全速運(yùn)行是因?yàn)檫@個(gè)程序只用了1個(gè)核心在做計(jì)算，而你顯示的是總的使用率，所以大概會(huì)保持在四分之一的水平。

是否用到了移位操作涉及Python大數(shù)運(yùn)算的具體設(shè)計(jì)，我不是很懂就不多講了。但原理上講也是很有可能的，如果用比特串存儲(chǔ)大數(shù)的話，那么計(jì)算2^N只需要在數(shù)組的第N位設(shè)置一個(gè)1，其余設(shè)置為0即可，那么轉(zhuǎn)換到十進(jìn)制是這段代碼中最消耗計(jì)算量的部分。