【 □□好美 】
如果可以自行填空的話，你會填上什麼字詞?
前幾天上色鉛筆課時，我提到向日葵的花心似乎跟數學有關。
「費氏數列。」C是數學老師，馬上精準地回應，但我和其他人一頭霧水。
她接著說:「1，1，2，3，5，8，13，21……前兩個數字相加就是後面的數字，大自然有很多植物的生長方式與費氏數列有關，例如螺、鳳梨、松果，形成一種黃金比例。」
雖然我對數字不在行，但腦中浮現了複雜但有秩序性的畫面。
「數學很美。」C的眼神閃閃發亮。
我第一次聽到有人這樣形容數學。
身邊的朋友，幾乎都痛恨數學。老師在黑板上寫的數字、公式和符號，像是一串串解不開的密碼，三角函數和開根號更是壓垮駱駝的最後一根稻草。上高中後我的數學成績就沒有及格過了，數學是青春歲月裡的陰影，哪裡會美呢?
但C的口吻和表情讓我有一點動搖了。
我上網搜尋了有關費氏數列的影片，赫然發現，自然界的數學不僅是美，而且有趣且神祕。
想著C說話時的光采，思索著，真正讓自己雀躍的，是當下的「發現」吧。
發現自己所不知道的、發現討厭原來是因為不了解、發現沒興趣是因為沒找到動機、發現自己太早畫地自限、發現還有其他人可以幫助自己發現更多的發現。
這樣的發現，也如費氏數列般遞增。
＊費氏數列影片連結: https://www.youtube.com/watch?v=JPFYhyFnxVw
---------------------------------
有如此深度對話的色鉛筆課是由高師大附中老師預約的，她們分別教授不同的科目，有理化、國文、地理等，在談話中可以感受到每個人對專業科目皆萌生有趣、美麗、好玩的讚賞，她們閃閃發亮地將美好的發現傳遞給學子們。關於教育，我們好需要這樣的光亮。
----------------------------------------
工作室最近會再開一波色鉛筆課，是可以慢慢畫的媒材，在平靜中堆疊色彩，願意的話，也可以對話，一起發現新的發現。
◆8/22《水溶性色鉛筆系列課程—花卉篇》/一期3堂
＊https://reurl.cc/R4ZvK6
★8~10月的畫畫課: https://www.facebook.com/222768341407699/posts/1224926354525221/
費氏數列公式解 在 [閒聊] g++ 8.2.1 把O(n) code 轉成O(1) - 看板C_and_CPP 的推薦與評價
最近有個熱門的討論話題
就是計算費氏數列的複雜度到底是 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
... <看更多>