計算機快速計算2^N是如何實現的？

01-14

看了大家的回答，感到十分羞愧。原來有這麼強大的快速冪演算法，而且列印輸出耗費了很多時間。謝謝大家的回答！
-------------------------以下為原問題-------------------------

Python3.6，CPU僅為酷睿i5-6200U,主頻2.3GHz。內存8GB。(密集恐懼症慎點圖片。。)(兩秒是用手機的秒錶記的)
估算了下，這個結果有48000位長。(十進位)
好奇的我又加了個0，2^10,000,000就慢多了，共用去了191秒。打開任務管理器後發現，而CPU並沒有全速運行，但筆記本風扇一直嗚嗚嗚的轉著。
最後，我注意到，結果中並沒有出現「2**10,000,000="，可能是結果位數已經突破命令提示符的限制了吧。。
我想知道現在的計算機運算速度到底有多快?

------------------以下為第二次實驗結果----------------

計算乘方是有快速演算法的，並不是一個一個蠻力乘上去的。比如想算2^10000，計算機先算2^5000，再算一次平方，即兩個數的乘法。而為了計算2^5000，計算機會先算2^2500再算一次平方。這個演算法叫快速冪演算法，對於2^N的計算，如果認為每次乘法的時間複雜度是O(1)的話，那整體的時間複雜度只有O(logN)級別。

一般來說，為了實現快速冪演算法，首先把指數做二進位表示，比如你要算A的23次方，可以把23分解為16+4+2+1。然後計算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 loglogN)等。快速冪的O(logN)次大數乘法中，最複雜的只有最後一次，也就是2^5000的那次，前面的複雜度幾何級數衰減，所以整體複雜度也就是最後一次計算的複雜度。如果你用FFT方法的話，複雜度也就是比線性多了一點點，一般計算機上隨便算算就出來了。

CPU沒有全速運行是因為這個程序只用了1個核心在做計算，而你顯示的是總的使用率，所以大概會保持在四分之一的水平。

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

用反覆平方法，計算 $2^N$ 大概需要計算 $O(log N)$ 次大數乘法，每次大數乘法的複雜度大概是 $O(N log N)$ ，所以總的複雜度在 $O(N log^2 N)$ 範圍內，隨著指數增長的速度不大。使用 $O(N^{1.58})$ 的乘法也差不多。

好好學演算法就不會瞎感嘆了。你算100000000個1加起來是多少也只要一下就能算出來，能說明你加法算得很快嗎……

In [3]: %time x=2**1000000 CPU times: user 3 μs, sys: 2 μs, total: 5 μs Wall time: 8.11 μs


In [4]: %time print(x)

...

CPU times: user 1.33 s, sys: 3.77 ms, total: 1.33 s

Wall time: 1.39 s

In [5]: %time s = str(x) CPU times: user 1.31 s, sys: 829 μs, total: 1.32 s Wall time: 1.32 s

所以這兩秒鐘並不是在做乘法運算：）

你試試下面這句, 才能說快得飛起

ky = 2 ** 10000000

有同學表示看不懂, 解釋一下吧

他慢是因為要顯示出來

實際上計算時間是 0

顯示時間 2 秒....

我這句把結果賦值給了一個變數, 就不用顯示了, 花費時間是 0

好吧。。。評論區有人指正了，python計算高精度的演算法是O(n^1.58)的Karatsuba Multiplication，不是FFT，不過在這種幾萬位的「小」數字上，顯然也是足夠快的

-----------------------------------------------------以下為原回答-----------------------------------------------------------

題主知道有個演算法叫做快速冪嗎。。。

題主知道還有個演算法叫做快速傅立葉變換嗎。。。

快速冪計算m^n的時間複雜度僅為O(logn)，雖然由於數字很大，高精度運算會花費比較多時間，但是高精度乘法這種卷積可以用FFT優化的，也只是O(nlogn)而已。。。

實際上的運算量根本不大，哪怕是老爺機帶起來也很輕鬆的其實，反而是輸出耗費了很多時間。

以及乘法慢是相對的，實際上並不慢。。。

「那幫無聊的程序員每天算2^1000…來考驗咱們的運算速度，怎麼辦？」

「返回二進位。」

首先，99%時間花在輸出上了，實際耗時我估計是在微秒單位上。

其次，雖然python內置無限精度計算，但依舊懷疑python的性能，而且這裡是簡單的單線程。如果用GMP + std::async的話，再高上一個數量級都不奇怪

求冪是有快速演算法的，下面給出了快速求冪的實現。時間複雜度是 O(logN)的。

long int pow(int x, unsigned int N){ int ans, n; ans = 1; n = x; while (N != 0){ if (N 1 == 1){ ans = ans * n; } n = n * n; N &>&>= 1; } return ans; }

先舉個例子，假如希望求 5^62，也就是 5 的 62 次方。

5^62 = 5^(32+16+8+4+2) = 5^32 * 5^16 * 5^8 * 5^4 * 5^2

不管指數是多少，都可以將其分解為 2 的倍數的和，因為任何整數都能夠寫成 2 進位的形式，比如 62 = 00111110B。

以上演算法中，隨著迭代 n 會變成 x, x^2, x^4, x^8,…，我們只需要在合適的時候讓它和 ans 相乘即可。合適的時刻就是 N 的二進位表示的相應位上為 1 的時候，這裡使用了右移，只需要判斷最低位是不是 1 就好了。

這個演算法是 O(logN) 的。之所以輸入 2**100000 很久沒有出現答案，那是因為顯示出來要花費大量時間，輸入輸入 `a = 2**1000000` 那麼就立刻執行完畢了。

本身計算左移200000位很簡單，瞬間完成吧。

你應該感慨一下這麼大的數字Python都能弄成十進位展示出來 ←_←

魅藍metal 表示壓力非常大。

Google搜一個叫快速冪的東西…

2^1000000的運算量其實比你想像的要少得多

樓主應該沒讀過微機原理吧。

x進位的運算都是通過位移可以算出來的。甚至比加法還要快得多。

比如 2的二進位是 10，那麼2的10次方就是往左移10位，末尾自動補0。所以結果時候10000000000，然後讀取成十進位。

PS：我在自己的python2.7上，CPU接近滿載，而且算了好久結果才出來的呀！！！！！！！！！！！！！！！！！！！！！扣肉i5 4核 8GB 內存。

其實遠不用2秒，你大量的時間是耗費在結果的輸出，也就是第二行命令上的。你要看究竟有多塊，在ipython下用命令：%time a = 2**1000000，你會發現耗時僅僅是納秒級（單位應該是微秒，計算2^1000000大約需要10微秒，說得太誇張了，謝謝 @lixin liu 的指正。）級的。

以2.4GHz的i5 520為例，一個cycle佔用1/(2.4GHz)，那麼運行2.4萬個cycle耗時越為10萬分之一秒，約為10微秒。

這個例子真沒有什麼代表性和說服力。如果說m秒算出圓周率小數點以後n位，或許還比較靠譜。

我就補充兩句。

大整數按二進位存，乘方速度其實很快，只是列印出來要轉十進位。

而實際上，刨去列印時間，耗費第二的時間應該是在做除法。

如果你有興趣你還可以學學大整數轉十進位的log級別（大概是可能有兩個log）演算法。

我剛開始學習 Python 的時候，也發現這一點，以往沒有接觸計算機編程，只是聽說摩爾定律，計算機的性能不斷提升，但開始學習編程，才真切地體會到這一點，原來人與計算機的計算能力已經差了這麼多！非常震驚，突然感覺進入了一個新的世界。

前兩天看到的，2010年，Bellard 用一台 core i7 + 6G 內存的電腦，花了103天，把圓周率計算到了 2 * (10^12)位，是當時的世界記錄.

當然現在的記錄已經提高了十倍，但基本只是用小型計算機而已。至於超級計算機，已經超出想像了。

想知道現代CPU的計算能力，不僅是要學演算法，更重要是要學計算機體系結構，知道現代CPU是如何設計的。

2.3GHz的處理器，代表一秒鐘處理器晶振震動23億次，一次一般稱為一個時鐘周期。一般一個ALU可以在一個周期里完成一次32/64位數加法，但是乘除法往往要佔用數十個周期。不過最慢的還是內存訪問，一般要佔用數百個周期。

所以用快速冪把這個數轉換為十進位，肯定是要用高精度加法的。所以其實你看到的時間可能都用在內存讀寫上了，真正用於加法的時間並不是主體。

如果用快速冪的話，只需要LOG級的高精度加法，這一部分很可能只用了不到幾微秒就完成了，剩下的時間是為了讓你能在屏幕上看見。

而且你還用了Python，Python中的數據結構都是很複雜的結構體，所以計算實際上要對這些結構體進行操作，這些結構體都涉及到大量的內存讀寫和其他輔助函數的執行（比如對象體積計算、越界檢查等），更慢。

如果你真的想認真驗證這個問題，還是得用C語言實現快速冪才行，還不能計入printf的時間，因為printf是系統調用，佔用了大量時間。

簡單計算一下：頻率的倒數就是時鐘周期，然後一個加法或者乘法大概幾個時鐘周期（一般都是納秒級別），然後能算出來一秒鐘計算多少次了。

如果是2的N次冪的話……應該是位移運算吧

有點沒看懂樓上幾位答主的回答。

題主問計算機是怎樣實現2的n次方，但是大家都在說快速冪。計算機算2^n好像是通過二進位左移n吧？