為什麼這篇費氏數列公式解鄉民發文收入到精華區：因為在費氏數列公式解這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者johnjohnlin ()看板C_and_CPP標題[閒聊] g++ 8.2.1 把 O(n)...
費氏數列公式解 在 ?賭Sir｜數學考試專家 Instagram 的最佳解答
2020-05-03 06:12:47
你學數列（Sequence）嘅時候，會遇到兩款資訊，符號係T(n)同S(n)，用人話講就係【第n個數係乜】同埋【頭n個數加埋係乜】。 . 喺話你知我中意T(n)定S(n)之前，我地舉個簡單嘅例子先，費事我地之間有誤會😚 . 舉個例：1, 3, 5, 7, 9, … . 第4個數係7，用數學嚇鬼符號寫...
最近有個熱門的討論話題
就是計算費氏數列的複雜度到底是 O(1) 還是 O(n)
剛好我前幾天在看 wiki 嘗試 compiler 的一些東西的時候
https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8
也遇到一些有趣的 O(1) 還是 O(n) 的問題
覺得很有趣所以就分享上來
我也有把問題丟在 stackoverflow 上面問
沒想到上面的反應也蠻熱烈的
https://stackoverflow.com/questions/54686395
讓我不小心賺到了一些 reputation，大概比我回答十個問題還多
---
不管複雜度是 O(1) 或是 O(n)，也不管 lookup table 到底要不要存在月球上
費氏數列遞迴的形式都是這條：F(x) = F(x-1) + F(x-2), F(1) = F(2) = 1
不過今天要討論的是一個更簡單的問題 F(x) = F(x-1)+1, F(0) = 0
學過中學以上歸納法的人類都能知道 F(x) = x
而學過 C++ 的人都可以把這個式子轉換變成程式碼
int Identity(int i) {
if (i == 1)
return 1;
else
return Identity(i-1)+1;
}
上面的 wiki 說明了這個並不是有效的 tail recursion 形式
理論上應該不會變成 for loop
會產生 O(n) memory, O(n) runtime 的程式
（PS: 如果是 for loop，應該是 O(1), memory O(n) runtime）
為了驗證，我用了 gcc 8.2.1 編譯看看，結果大出意外
% g++ a.cpp -c -O2 && objdump -d a.o
Disassembly of section .text:
0000000000000000 <_Z8Identityi>:
0: 89 f8 mov %edi,%eax
2: c3 ret
Linux 下 x64 的第一個整數是 %edi，回傳值放在 %eax
等等，所以我以為 O(n) 的問題，真的可以在 O(1) 解出來嗎（誤）
難道 compiler 做了一些數學計算，推出 F(x) = x 了嗎
該不會在這個大 AI 時代，compiler 也要內建高中生等級的 super AI 了吧
該不會我下次升級到 gcc 9 的時候，我的 compiler 就會跑去當 Youtuber 了吧？！
---
Sorry 扯遠了，回歸正題
我一開始的想法是
1. gcc 知道了 negative i 會撞到 UB，因此可以隨便回傳任何值
（PS: negative i 不會變成 infinite loop 的 UB，而是 overflow）
2. positive i 的情形 gcc 經過了某些數學推導算出 F(x) = x
但是怎麼看都覺得太神奇，感覺不會有人實做這種東西
總之經過 stackoverflow 一番討論之後
看起來的結論如下
首先，當代的 gcc 不只可以化簡基本的 tail recursion
就連上面那個形式都可以（可以去看 stackoverflow 的一些討論）
雖然詳細上原理我不太明白，但是應該、大約、好像會變成這樣子
int Identity(int i) {
int ans = 0;
for (; i != 0; i--, ans++);
return ans;
}
接著我猜測這個形式對 compiler 來說應該比較好化簡了
因為這種 for loop 非常常見，應該有機會做某種化簡得到 F(x) = x
順帶一題，直接寫這個程式的話，gcc 是可以化簡 O(n) -> O(1) 的
如果 i != 0 改成 i >= 0 的話，gcc 會變成 return i > 0 ? i : 0;
真的很厲害
---
另外 stackoverflow 裡面有人直接挖出 gcc code 來解釋
但是其實我不是 compiler 專家
所以我這篇主要還是單純分享一些我的觀察啦
如果這個版有人能做出更淺顯易懂，又更完整的解釋的話就太好了
謝謝大家～
--
Time waits for no one.
↑
(。Ａ。)ハァ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.89.176
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1550249453.A.382.html
推 KanzakiHAria: 你應該沒搞懂那個討論 02/16 06:33
→ KanzakiHAria: O(1)是說費式數列有一個公式解 02/16 06:33
→ KanzakiHAria: 可是裡面有開根號 所以實務上並不是O(1) 02/16 06:34
→ KanzakiHAria: 開根號速度跟數字長度有關係 02/16 06:34
→ KanzakiHAria: 那個作者非常智障的嗆人time it 實際上就不是O(1) 02/16 06:35
→ KanzakiHAria: 那個人履歷蠻漂亮的 電機出身+待過微軟開發過VS前期 02/16 06:36
→ KanzakiHAria: 看他講話好像連基本的計算機原理和演算法數學都不懂 02/16 06:36
→ KanzakiHAria: 連我以前當助教的學生都可以電爆他了XD 02/16 06:37
推 KanzakiHAria: 講錯了 不是開根號 是次方問題 02/16 06:41
推 KanzakiHAria: 然後O(n)裡的n 一種是編碼長度 一種是input數量 02/16 06:47
→ KanzakiHAria: 因為是編碼長度問題 所以實際上是O(lgn) 02/16 06:49
推 KanzakiHAria: 不過說不定原作者是想表達C++有編譯時期運算技術 02/16 06:52
→ KanzakiHAria: 所以不管n多大C++都會在編譯時期算好 02/16 06:52
→ KanzakiHAria: 所以run-time是O(1)wwwwwwwwww 02/16 06:52
推 alan23273850: 神奇給推！ 02/16 08:57
→ KanzakiHAria: 已經跟地球月球時間無關 而是根本上錯誤 02/16 08:57
推 steve8625: 真有趣~~ 02/16 11:55
推 b98901056: Vtuber compiler XD 02/16 12:44
推 firejox: 以編碼長度來看，也不會是O(lg n) 02/16 20:02
→ Sanvean: 我是不是錯過了什麼新聞？ 求費氏數列的討論串 pAq 02/17 14:45
→ Ommm5566: ㄟ 這是兩件事 1. O(logN) 是因為乘法有快速乘法logN 02/17 17:14
→ Ommm5566: 2. turing machine來看編碼長度確實是logN 02/17 17:16
→ Ommm5566: 然後巧合的是剛好這兩件事可以掛勾在一起 02/17 17:17
推 Ommm5566: 這個討論串居很無聊，居然這麼多人關注。 02/17 17:20
推 LPH66: 樓上的兩個 logN 是不同 N 吧? 02/17 20:02
→ LPH66: 你的"快速乘法"的 log N 的 N 是編碼長度 02/17 20:02
→ LPH66: turing machine 編碼的 logN 的 N 是數值本身 02/17 20:03
推 Ommm5566: Fabonacci(X) 這個是編碼長度logX 所以放在tap上是logX 02/17 20:19
→ Ommm5566: 然後公式解是一個const連乘X次 02/17 20:20
→ Ommm5566: 因為有快速乘法所以時間是logX 02/17 20:21
→ Ommm5566: 這題只是剛好快速乘法的行為跟二進為編碼直接有相關 02/17 20:21
推 Ommm5566: 1000 是四位數編碼 100是三位數編碼 10是兩位數編碼 02/17 20:24
→ Ommm5566: 放在tap上長度本來就是logN 02/17 20:24
推 KanzakiHAria: 所以正確來說編碼長度N的費氏數列時間複雜度O(N) 02/17 21:32
推 KanzakiHAria: 前面可能我表達不好 這個應該沒爭議了吧 02/17 22:36
推 AstralBrain: O(N)次乘法, 但是乘法的時間不一定是O(1), 看你要怎 02/18 02:33
→ AstralBrain: 麼算 02/18 02:33
→ AstralBrain: 算出沒誤差的精確值至少是O(2^N), 因為答案本身就有 02/18 02:34
→ AstralBrain: O(2^N)bit了 02/18 02:34
推 AstralBrain: 啊..修正一下, 底不確定是不是2, 但總之是指數級成長 02/18 02:53
→ gus2: 怎麼推文都在回討論串？本文重心是編譯器優化遞迴f(i)成i吧 02/18 03:13
推 gus2: 有趣給推 02/18 03:15
→ Caesar08: 請問Higana，這是在哪個社團，那麼有趣 XD 02/18 13:04
推 asd456fgh778: 樓上 Python台灣 02/18 14:42
推 Higana: 是的 但該篇他老早就刪了 剩一些後續討論這樣 02/20 01:44