2019年7月10日 星期三

到東京玩 B777-300ER 飛行模擬器

故事是這樣子的,因為一些個人因素,小弟會常常需要來往東京,幸好現在亞洲廉航選擇多,兩個月左右飛一次還可以承受。
在大概是今年一月回台灣的 Vanilla Air 上,看了它們的機上雜誌,內容是由 Vanilla Air 的員工介紹去東京有什麼可以玩的,裡面有一個 Skyart Japan 的介紹,還滿有趣的,服務是可以操縱貨真價實的 B777-300ER 模擬器,在擬真的機艙裡面拍照之類的。

今年六月的時候,預約了一趟飛機模擬的行程,寫篇文來介紹一下這個冷門的旅遊地點:

其實這家除了開模擬器,還有一些其他的服務,像是機師衣服出租、機艙空間出租、寵物攝影(?之類的,但這篇就專注在操縱模擬器上。
首先,這是真的 B777-300ER 的模擬器,所以玩起來其實不便宜,大家可以上官網看它的 plan 列表,最基本的體驗課程,30 分鐘要價是 11,000 JPY,最高開到 120 分鐘 36,000 JPY,有一些特別的方案,像是看富士山,雙人方案、開趴方案、四季景色方案、克服飛行恐懼症…,或者是可以附加的,像是機師制服出借、登機證、從啟動 engine 開始之類的。
順帶一提,它們是可以讓機師做模擬機訓練,像是起飛降落、惡劣天侯,我不確定是網頁(他們的網頁其實很亂,資訊太多沒有整理好)還是現場,有看到相關的規定:「如果你有機師的執照,是必須要出示的」,當然專業機師的方案會比較貴一點,比普通方案每 30 分鐘多 5,000 JPY,所以 120 分鐘就要 56,000 JPY 了。

從預約開始,他們官網有個詢問預約時間有沒有空的表單,不過我記得我填了之後也沒有人理我,直接 plan 選一選下訂比較乾脆,下訂之後就會有人來信跟你確認預約的時間,如果真的很怕訂了之後預約的時間沒空的話,也是可以去信詢問:info@skyart-japan.tokyo,寄信就真的有人會回了。

公司的地址在東京都品川区北品川6-7-29 ガーデンシティー品川御殿山,最近的車站就是品川站,走路大概要 15 分鐘,請自行參考 Google 街景,在一棟很氣派的建築物裡面。

很奇妙的我翻遍手機發現沒有他們客艙內景的照片,可能自行搭配官網的小圖,中間的桌子疑似是用引擎尾部改造而成,噢然後這個是 A320 的客艙,雖然是 A320 的客艙卻長了個 B777-300 的機頭
我們預約的方案是 1 小時的普通模擬方案,附加從停機坪發動引擎跟後推,總價是 26,000 JPY,在下訂的時候就用信用卡附款完成,模擬的時候會有一位真的機師在旁邊當副駕,可以用日文或是英文輔助駕駛,不過畢竟是在日本,一開始詢問方案的時候還是要用日文,我們 1 小時方案可以選擇的有:
* 從羽田機場起飛,繞一圈回到羽田機場降落
* 從羽田機場起飛到成田機場降落
* 從羽田機場起飛到世界上任一個機場降落,當然中間的巡航會省掉,瞬間移動到當地上空

女友選了從羽田起飛/降落三次(兩次 GA)的方案,這樣操作到最多東西。


這張應該就是羽田後推時的照片,一開始先是一位日本機師當副駕用日文帶飛,基本上什麼都不會也沒差,副駕會幫你搞定一切(好啦開引擎他會讓你開一邊),呆呆的看著他跟電腦對話就行了;上跑道飛機自己會緩速前進,正駕駛用一根桿子控制方向。

起飛之後真的能感受到模擬機的厲害,大型的建築物都是建模出來,能看到晴空塔跟迪士尼樂園,夜間飛行還可以加上煙火XDD;不過這台模擬機只有畫面,不會有真正的前後傾斜。

飛完第一圈之後,換旁邊待機的土耳其(? 機師上去,用英文帶飛。我這時跟日本機師問東問西,順便玩我女友:

Q:為什麼雷達圖上面沒有飛機?
A:喔,那只是我們沒開:(轉一個開關)飛機就顯示出來啦wwww
會顯示編號,比我們高,正在下降之類的資訊,故意飛太近的話還會有碰撞警告

Q:剛剛跟後推車的對話是真人還是錄音?
A:錄音,要的話我們也可以(轉另一個開關)機艙內開始放 ATC 跟飛機對話的錄音,好像是紐約那邊的 ATC,播下去之後真的超有實感

其他一些雜雜:
現在飛機都全自動了,三個儀表版可以設定速度、高度跟方位,高度跟方位只會影響儀錶版上的顯示,提醒你要飛到多高跟往哪裡飛,速度設下去電腦會自動接手引擎,所以會看到油門把手自己在那邊動來動去OAO,連降落都是到最後一刻才解除自動駕駛。
轉彎如果超過 35 度,會跳警告:Bank Angle ~ Bank Angle ~,其實我比較想聽 Pull Up ~ Pull Up ~,我滿好奇 35 度到底急不急… 看航跡圖的轉彎半徑都超級小,在旁邊看轉彎半徑還沒有照著航跡圖轉過 owo

總之體驗一下是滿有趣的,如果真的不知道在東京想幹啥,或者想要體驗看看開噴射飛機的話,可以到 Skyart 試試看,預約跟一進去多少需要一些日文對話能力,但我猜他們英文會話應該是能通的。
沒開飛機還是坐個駕駛座過過乾癮,這張是降落之後停在滑行道上,結束時拍的,看看這複雜的儀錶板:

2019年4月22日 星期一

第一次教召就上手

我想是這樣子的,如果你進到這個頁面,有很高的機會你是因為收到後備指揮部寄來的神祕信件,很不巧的機票又沒有訂下去,開始無助的在網路上收集各種相關資訊,或者已經到了鬼門開的前一天,要準備好收行李的時候。
其實小弟也差不多,我是在 2 月底的時候接到後備指揮部確認資料的電話,過不久通知書就寄到家裡,4/15-4/19 要被教召,看看反正就進去國軍養個肝,在那邊躲來躲去的也不是辦法,反正雖然是南部但 4 月中還不算太熱,就乖乖的去召一下保衛台灣獨立。

從拿到召訓說明書開始說起,其實召訓說明書上已經寫清楚要準備什麼了:
  • 身分證/健保卡/駕照三選一,身分證當然是最好,但只要能證明身分的都OK。
  • 私章,領薪餉用:沒帶也可以簽名所以沒差。
  • 個人所需藥品:有病就該吃藥(欸。
  • 盥洗用具:要不要用新訓那種洗頭髮洗身體二合一的看個人,教召洗澡時間比較多沒必要洗戰鬥澡;大概就是沐浴乳、洗髮精、牙膏跟牙刷,刮髮刀想帶就帶一支。
個人衣物,這部分可能是大家最想知道的?當初我有查這個查了一下:
基本上進去會領到公發的兩雙黑襪、兩件內衣、兩件內褲跟一條毛巾,我的策略就是衣服完全不洗,時間省下來看書,我是這樣帶:
  • 一套離營時穿的衣服:星期一報到的時候身上穿的衣服褲子,到營區之後就脫掉放進塑膠袋裡包好,因為天氣熱的話,星期一的衣服吸飽到營區的汗水,放到星期五會非常的臭(我服役的時候試過一次會有像大便的味道,然後我還穿那個去搭捷運回家wwww),簡單作法就是密封起來不再穿了。
  • 保暖用的外套:我是沒帶畢竟南國 4 月就不用再穿外套了。
  • 毛巾:公發的就省下來,解召前繳回去,少浪費一點資源。
  • 五件內衣:同理,不過我日常沒內衣所以就是兩件公發的穿五天這樣。
  • 五件內褲:公發的我繳回去了。
  • 五雙黑襪:公發的我繳回去,如果要自備的話建議買好一點,或是用已經穿舊的,我買了新的結果非常咬腳,覺得沒有很舒服,襪口上面一點有腫起來,雖然我不確定會不會是有跳蚤。
  • 睡覺穿的短褲:這次我忘了帶,只好都穿迷彩褲睡覺…。
衣服之外就是要帶塑膠袋裝髒衣服。

其他:
  • 書:殺時間用的(其實跟同袍哈啦也很殺時間),輕小說我就覺得不錯,小本又可以看很久,像隔壁的大兵帶了<刀劍神域 18、19>,五天下來也快看完了。
  • 充電線:如果你手機續航力不夠,應該會開放中山室讓大家在使用時間充點電,但如果保持關機手機應該不至於每天用幾小時就沒電啦。
  • 水壺:裡面會發保特瓶的腰間水壺,我自己的水壺是晚上在寢室用的。
  • A4 資料夾:裝教召令跟手機三聯單等文件,進去會發一個牛皮紙袋不過我覺得資料夾比較好用。
  • 手錶:我的手錶進去前壞掉了,體會到各種不方便,要一直跟人借錶看時間。
我這次有個第三次被召的自備延長線跟電扇,這就看個人有沒有需要了,如果是 7, 8 月也許有需要。
教召基本上沒有髮禁跟鬍子的要求,裡面也有看到染金髮跟馬尾,要不要剪三分頭的答案應該很明顯了,我是順道去剪短一些,這樣比較不會熱。
連著教召單寄到的包含一張交通兌換券,填好之後可以換台鐵的票,理論上只能換莒光但我換到自強號他也沒跟我收錢owo,而且明明薪餉的錢是來回都有算,那我去程票用換的不是變成國家補助了召員兩次車錢?

教召其實就輕鬆過就好了,稱謂從新訓的編號->部隊的姓名->各位伙伴,一開始聽到怎麼聽怎麼不習慣XD;協訓幹部對大家也很客氣,大家至少都20多歲也都成熟多了,反正大家都當過兵也知道要怎麼做,撐一下五天就過去了。雖然如此教召也不是在玩,該練的都有練,該打靶的就打 25/175 的靶,打完該擦槍的就擦槍,砲操該跳的就連跳三天。
生活上來說下課可以投飲料(我覺得軍中的販賣機一定超級賺…),可以上營站,上下午20 分鐘的下課也會有小蜜蜂販售熱食冷飲,小心不要吃胖了。
手機收繳放養機場之後,每天中午跟晚上兩次有三個時段可以用手機,我自己是覺得領手機麻煩,統一在晚上用手機。
這次的飯(不知道為什麼)很難吃,跟新訓、通校、前運隊、部隊比起來,就教召的飯最難吃,醃漬品特多,新鮮的菜很少很像伙房在省錢,偏偏炒菜又很常燒焦變臭灰搭口味,如果真的忍不住就買營站的泡麵來吃,出來之後我現在吃什麼都覺得是人間美味wwww。

其實教召跟其他人聊一下,也是不錯的體驗,每個人各有不同的退伍年次,服役時的單位也都不同,有的人真的超級操,下部隊遇到聯勇,打完之後一個月再接漢光,結束一周後開始準備聯信(名字跟順序我不確定),幸好在開打前他退了;跟我這種在部隊上做九個月文書退伍的不一樣,這次都是另外兩位下過基地的人在罩我,動作做起來超純熟的。
可能就跟這部微電影說的一樣吧:一次當兵下過聯勇,一生回憶抬頭挺胸。

這次教召小弟的公司那邊正好要發新版軟體,正在緊鑼密鼓的測試跟解 bug,我一被召就躲了五天的工作 lol,然後久違的得到一堆時間可以專心做自己的事,就把很早以前拿到的<時間管理-給系統管理員>給看完了,雖然說一次把書看完好像不是作者的本意啦XDD。
不管怎麼樣進去養個肝也不錯,出來我晚上 10 點眼皮自動變沉重,倒下去一覺到天亮,健康到肝臟都會發光呢。

2019年4月6日 星期六

自幹發光眼鏡

故事是這樣子的,去年十月跟傳說中的幣圈大佬小新大大弄完 Nixie Tube Clock,從小新大大那邊拿到一團剩餘零件,剛好裡面有一批 1206 的白光 LED,想說丟回收前還是可以利用一下,不如就來做個發光眼鏡好了。

準備材料:不要的眼鏡一副、描圖紙、1206 白光 LED、電線、強力膠、220 Ohm 電阻、供電用的 arduino、焊接工具。

首先要把 1206 發光側貼在眼鏡周邊,我試過一定要用強力膠才能黏得住,保麗龍膠跟雙面膠都無法,焊上電線之後扯 LED 的力道出乎意料的強,光電線本身的彈力就能把 LED 再扯下來,其實就算是強力膠用力扯還是會脫下來,使用上要小心一點。
註:強力膠與保麗龍膠感謝強者我室友贊助。
鏡面的部分要貼上描圖紙,才能把光擋下來做出發光的效果,當然貼上描圖紙之後眼鏡就看不到東西了…;最後是把 LED 上焊上電線,焊上之後就要特別小心別把 LED 扯下來了。
最後接上電源,記得 LED 要串聯 220 Ohm 的限流電阻,這樣發光眼鏡就完成啦。

成品:

來看看效果:
啊發光有點不均勻……不過就算了,真的要均勻就要多一點 LED 才行,至少內側也要一組,接線會變很麻煩,直接買燈條應該會簡單很多啦,連焊接都省了,但燈條就是比較貴一點就是…。
至於醜醜的電線…如果有閒的話是可以拉去後面,但有點懶得弄,總之有效果了,我們可以來玩一些東西,像是:

認真發光:

眼神閃爍(物理)
眼神高頻閃爍(物理)

好啦…其實這個東西只是來亂的,大家可以不用這麼認真XD。

2019年3月19日 星期二

維基百科上繁簡內容的修訂

故事是這樣子的,最近小弟在看 github 上一個 os 的教學,跟 jserv 大大的 mini-arm-os 有點像,都是教你從頭幹一個作業系統出來,只不過這個是幹在 X86 處理器上,某種程度上我覺得在 X86 上寫開機程式根本是各種考古,還要從 real mode 一路開上來(yay
最近剛寫好小弟第一個 X86 kernel ,結果因為在 link kernel 的時候,object 檔案的順序寫錯,害我 de 了一輪搖曳露營 OST的 bug,超白痴。

扯遠了,其實這篇是要講 wiki 的,在寫作業系統的時候不免會去查一些 wiki 資料,然後就發現某些條目充滿了中國風格的用語,當然上面選擇台灣正體也不是看不懂但就是煩,於是把過去註冊密碼忘了的 wiki 帳號找了回來,自己來做個編輯,這裡記錄一下流程,希望大家有看到類似的狀況也可以順手修正一下。
我看到的文章是這篇:X86 呼叫慣例

參考用的資料:wiki 繁簡處理說明

首先先打開上例的 X86 呼叫慣例的頁面,會發現網址的部分,其實是 zh-tw/X86调用约定,這是因為 wiki 的規定是所有的中文頁面都是同樣的內容,再用之後會提到的轉換方式,轉換為中國(zh-cn)、新加坡(zh-sg)及馬來西亞(zh-my)三種簡體中文;台灣(zh-tw)、香港(zh-hk)和澳門(zh-mo)三個繁體中文。
所以在條目上變成先佔先贏,也就是有了「X86调用约定」的頁面的話,就不能新建「X86呼叫約定」的條目,必須只能編輯這個頁面,請見繁簡轉換的條目標題
然後編輯內容也不能隨意將簡體轉成繁體或反向轉換,否則會被視為破壞;另外文中的異體字、日本漢字也都有自己的處理方式,不過這裡我們今天不會提到。

這麼做的好處,就是無論簡體或繁體都會貢獻中文的所有頁面,壞處就是用語、行文等習慣,會需要花費時間轉換,而且我很懷疑能不能轉得好,像是文字轉過去了文法卻沒法用轉換的,對編輯者來說也很麻煩,像我如果要編輯簡體先到先得的頁面,就得要用簡體編輯才行,我個人是覺得壞處是大過好處的…但總之這是現下 wiki 的政策,再怎麼智障也只能先遵循(我其實找不太到這個政策形成的過程,也許有知道的人可以補個脈絡)。

再來就要到所謂地區詞處理了,請見wiki 地區詞處理說明:例如 stack 繁體為堆疊,中國簡體則是堆栈或栈,現下 wiki 的做法就是本文一律先到先得,編輯者是簡體中文就寫簡體中文,讀者選擇台灣正體的時候,再轉換成繁體頁面。
這裡的系統畫成階層圖大概是這樣:

愈下面的地區碼針對性就愈強,指定 zh-mo 就只會在澳門繁體頁面才會轉換,但指定繁體中文就會在下面三個語言都轉換;另外 wiki 有幾個不同階層的轉換:由上而下為全域轉換、全文轉換、公共組轉換、單獨轉換來處理。

  • 全域轉換就是超暴力所有 wiki 範圍內的文字都轉換,誤殺率很高,只有非常針對絕對不會誤殺的詞才能進去,例如台灣正體轉換表的:米芝蓮=>米其林。
  • 全文轉換雷同,只是在一篇文章內通殺。
  • 公共轉換組應該是最實用的,也就是針對資訊科技,定義好一系列的對照表,這些對照表就能套用到跟資訊科技相關的文章中。
  • 單獨轉換就是用來針對固定位置的詞來做轉換

我在看到 X86调用约定的時候,就是因為沒上資訊科技的公共轉換組:IT,以致雖然是繁體頁面內容卻都是中國用語(例如標題轉換成 X86調用約定),修正方式也很簡單,在原始碼的部分加上 NoteTA 的轉換模版就好:
{{noteTA
|T=zh-hans:X86调用约定; zh-hant:X86呼叫慣例;
|G1=IT
}}

其中 T 表示標題的轉換
G1~Gn 則是引用公共轉換組,這裡引用一個 IT 的,至於你說為什麼我知道要引用這個…呃…目前我只知道從類似條目去找,或者從全部的列表裡去找(yay

其實只要加上公共轉換組,看起來就會順眼很多了,自然會有一些詞沒修正到,只能之後手動下去修,像公共轉換組只定義堆栈要轉成堆疊,但原始碼有人只寫栈就轉不過去了。
大概就是這樣,要讓 wiki 用詞跟習慣一樣,還是需要大大們多多動手做點小修改,我個人還是覺得把簡體跟繁體頁面合併滿白痴的,你看我們定義了這麼多的公共轉換組,其實連個 X86呼叫慣例都轉換不好,說到底簡體中文跟繁體中文已經不是文字上的差別,而是連文法上都有差異了吧

2019年2月12日 星期二

關於費式數列的那些事

最近費式數列實在有點紅,讓小弟忍不住也來玩一下。
費式數列給一個初學程式的人都能寫得出來,例如早年我忘了哪位大大在推坑我 python 的時候,就寫了個只要 4 行列出費氏數列的 python 程式,一方面展現 python 在大數運算上的實力,一方面展視了它的簡潔,像是 a , b = a+b, a 這種寫法。
a = b = 1
while b < 1000000000000:
  print(b)
  a, b = a+b, a
當然會寫是一回事,深入進去就沒那麼簡單了,詳細請參考這個網頁
最簡單、最直覺的遞迴寫法,但這其實是會噴射的,每次遞迴都會做重複的計算,於是計算以指數的方式成長,比如說我用 python 的 timeit 去測一個遞迴的費式數列函式,很快執行時間就會爆炸,大概到了 fib(30) 以上就會跑得很吃力了。
如果我們用單純的加法,從 1 開始往上加,其實只要進行 n 次的加法就能得到 fib(n) 了,執行複雜度為 O(n);如果再套用更快的 fast fibonacci,更可以把執行時間拉到 O(lg n) 的程度,只要 fib(94) 就超過 64 bits 的整數的情況下,用 O(lg n) 的演算法其實跟常數時間所差無幾。
不過呢,費式數列還有一個公式解呢,也就是:
$fib(n) = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
為什麼不用這個算式算呢?公式解不是常數時間嗎?

數學上來說:是的,但實際上會遇上一些問題,例如我們看看 64 bits 整數裡面最大的 fib(93) 為例,整數算的解為:
12200160415121876738
如果是 python 寫的公式解呢?
def fib(n):
    return (math.pow((1+math.sqrt(5))/2, n) - math.pow((1-math.sqrt(5))/2, n)) / math.sqrt(5)
print(int(fib(93)))
12200160415121913856
登登,問題大條了,答案不一樣。
何以致此,問題就來到浮點數的不精確問題,這時候就要先來一張經典的漫畫了:
我們在計算完 sqrt(5) 之後,只能用一個近似的值來表達結果,在 python 內預設是以雙精度浮點數在儲存,它跟真正的 sqrt(5) 還是有細微的差距,在隨後的 n 次方、除法上,這個細微的誤差都會被慢慢的放大,最終導致這個巨大的誤差。

幸好我們不是沒有解法的,參考了 C/C++ 版上,傳說中的 Schottky 大大曾經分享如何使用 gmp 或 mpfr 兩個函式庫,算出 e 到小數點下一億位pi 到小數點下一億位,這兩個 gnu 函式庫是所謂的<無限>位數的整數跟<無限>精確度的浮點數,當然他們不是真的無限,只是完全壓榨記憶體來記錄儘可能多的位數以求精確,理論上記憶體撐上去就能把精確度逼上去,只是有沒有那個必要就是,像是把一些無理數算到一億位(欸。
究竟這個函式庫有多麼的強大呢?我們可以來寫個簡單的,例如來算個黃金比例,只要這樣就結束了:
mpfr_t phi;
unsigned long int precision, x=5;
uint64_t digits = DIGITS;

precision = ceill((digits+1)*logl(10)/logl(2));
mpfr_init2(phi, precision);
mpfr_sqrt_ui(phi, x, MPFR_RNDN);
mpfr_add_ui(phi, phi, 1.0, MPFR_RNDN);
mpfr_div_ui(phi, phi, 2.0, MPFR_RNDN);
mpfr_printf("%.10000Rf\n", phi);
mpfr_clear(phi);
唯一要注意的是 mpfr 內部用的 precision 是以 2 進位為底,所以我們在十進位需要的精確度,要先換算為 2 進位的位數,再來就能直接算出 phi 啦,試著算過 50000 位數再對個網路上找的答案,數字是完全一樣的。
這個 library 算得非常快,一百萬位的 phi 也是閃一下就出來了,一億位在我的 64 bit Linux, 2 GHz AMD Ryzen 5 需時 37s,相比 e, pi 這類超越數,phi 只需要 sqrt(5) 真的是非常簡單的了。

扯遠了拉回來,如果我們要用 mpfr 這個函式庫,利用公式解來算 fib(93),要怎麼做呢?
fib(93) 到底有多少位數呢?我們可以用 2^n 作為 F(n) 的上界,最後所需的位數至少就是 ceill(n*log(2)),相對應的我們運算中的浮點數精確度的要求,2^n 這個上界有點可恥粗糙但有用,頂多會浪費點記憶體,最後除出來的小數點後面多幾個零而已,如果能套用更精確的上界當然更好。
mpfr 的函式庫設計精良,呼叫上非常直覺,這段程式碼其實就是寫公式解,應該滿好懂的,程式碼在此。有了這個就可以亂算一堆 fib 了,基本上要算費式數列第一億項 fib(100,000,000) 也是 OK 的(好啦我不保證答案是對的XD,至少 fib(10000) 是對的)。

But,人生最厲害的就是這個 But,公式解真的有比較快嗎?
我個人認為答案是否定的,我們同樣可以用 fast-fibonacci 搭配 gmp 函式庫來計算,因為都是整數的運算可以做到非常快,我的測試程式碼在此

同樣是計算 fib(100,000,000):
formulafib.c: 57.39s user 2.04s system 97% cpu 1:01.09 total
fastfib.c: 4.70s user 0.20s system 75% cpu 6.524 total
O(lg n) 的 fast-fibonacci 遠比<O(1)>的公式解來得快。
問題就在於,到了所謂的大數區域,本來我們假定 O(1) 的加法、乘法都不再是常數時間,而是與數字的長度 k (位元數)有關。而上面我們有提到,基本上可以用 2^n 作為費式數列的上界,也因此費式數列的數字長度 k ~= n,加法、乘法複雜度就會視實作方式上升到 O(n) 跟 O(n^2) 或 O(n lg n) 左右。
在 fast-fibonacci,我們需要做 lg n 次的 iteration,每次三個乘法兩個加減;公式解雖然沒有 iteration,但需要計算兩次次方運算,也等於是 lg n 次的乘法跟加法,然後還有除法,我們運算的又不是整數而是浮點數,這又需要更多的成本,一來一往之間就抵消了公式解直接算出答案的優勢了。

在通常的應用上以及現今電腦的實作,我們還是可以假設整數的加減乘都能在近乎常數時間內結束,這樣我們才能好好討論資料結構與演算法的複雜度,進而把複雜度學好。費氏數列的問題在於,在數字小不用考慮運算複雜度的時候,公式解和 O(lg n) 的 fast-fibonacci 看不出差異,等到 n 終於大到看得出 O(lg n) 跟 O(1) 的差異時,已經要把運算複雜度納入考量了。
理論上我們當然可以假設有個計算模型,無論有多少位的數字,無論浮點數有多少精確度要求,四則運算與次方都能在常數時間內結束,這時公式解就能來到 O(1),但這樣的假設不像停機問題假設的萬能機器,在學術討論上看來不太有意義。
利用 gmp, mpfr 這樣的函式庫,插滿記憶體甚至把硬碟當記憶體來用、把記憶體當 cache 用,浪費幾個星期跟一堆電力,我們可以把無理數算到小數點下一億位、十億位,這是前人們精心為我們建的巨塔,可是數字還是無窮無盡,站在巨塔上反而才看得出我們跟無限有多麼遙遠,誠然人腦可以透過思考一窺數學之奧妙,但不代表我們能超脫數學的嚴格限制浮空而起,妄想記錄無限,我認為是對數學的一種褻瀆。

看了這麼多碎碎念大家想必也累了,總而言之本文透過兩個實作,讓大家體會一下所謂 O(1) 公式解並不一定是 O(1),背後一定有對應的成本;還有就是把費式數列算到一億位真的有點爽,不過我想是沒什麼公司在實務上有在賣 fibonacci 相關的產品啦,除非你想像日本一樣出個寫滿 e, pi 到一百萬位的書讓人當亂數表來用。

Related Posts Plugin for WordPress, Blogger...