看板 Gossiping作者 jserv (松鼠)標題 Re: [問卦] 不用函數庫和亂數 寫程式求pi值的方法?時間 Fri Apr 19 02:27:45 2019
※ 引述《fragmentwing (片翼碎夢)》之銘言:
: 小弟程式設計新手
: 看到後面的講義習題要算圓周率
: 如果不用亂數,也不用函數庫的話
: 我自己用了一個在寫之前就覺得很浪費電腦能力的方法
: 在電腦能力處理極限,還沒法精確到小數點後第二位呢
: 鄉民會怎麼用程式求圓周率呢?
這裡提供一種途徑,只用到 C 語言標準函式庫裡頭的以下函式:
* fopen / fclose
* getc / putc
既然上述說要「浪費電腦能力」,那我們不妨試試這個策略:
a. 實作符合 Turing completeness (圖靈完備) 的 Brainfuck 程式語言 [1]
執行環境;
b. 撰寫 Brainfuck 程式,使其得以計算圓周率,並用十進位浮點數輸出;
可將 Brainfuck 的執行環境設想為一台機器,擁有一個讀寫頭及無限長的紙帶,
機器會依下列指令進行操作:
> : 使讀寫頭在紙帶上前進一格
< : 使讀寫頭在紙帶上後退一格
+ : 對目前讀寫頭下的值,進行遞增 1 的運算
- : 對目前讀寫頭下的值,進行遞減 1 的運算
. : 將目前讀寫頭下的值,以對應的字母輸出
, : 將目前讀寫頭下的字母讀入並轉為數字後寫回
[ : 比較目前的值,若不為 0 即前進,若為 0 就略過指令,直到遇上匹配的 ]
] : 比較目前的值,若不為 0,指令要跳回上個出現 [ 的位置
不難發現,作為一個「知易行難」的程式語言,Brainfuck 僅有 8 個指令,其中
2 個是 I/O 動作。作為 Turing machine 的實踐,Brainfuck 對記憶體單元作直接
存取,對應到 C 語言的概念來說,如果 char *p 指向記憶體區塊的話,Brainfuck
語言的 8 個指令可對照為以下 C 等價敘述:
也就是說,下方的 Brainfuck 程式碼:
+++++[-]
對應到 C 語言程式碼為:
*p = +5;
while (*p != 0) {
*p--;
}
既然有了指令對照表,我們即可著手建構小型的 Brainfuck 直譯器: (檔名為 bf.c)
#include <stdio.h>
#include <stdlib.h>
static int p[64 * 1024], d[1024 * 1024], r, t, e;
int main(int c, char *v[]) {
if (c < 2) exit(1);
for (FILE *f = fopen(v[1], "r"); f && (c = getc(f)) != EOF; p[r++] = c);
}
for (; c == ']' && d[t]; r--) {
if (p[r] == ']') e++;
if ((p[r] == '[') && (e-- == 1)) break;
}
}
}
回到一開始提到的 Turing completeness,Brainfuck 與其說是程式語言,不如說是
一台理想機器的描述:機器具有無限的儲存 (storage,也就是無限長的紙帶)、運算
(arithmetic,如遞增和遞減)、條件判斷 ([ ] 涉及目前值是否為 0 的判斷) 以及
重複 (repetition,這也是 [ ] 的行為),Brainfuck 這台機器具備上述四項特徵,
是 Turing completeness。依據 Alan Turing 的觀點,這樣的一台機器,即可模擬
人類所能進行的任何計算過程,自然就包含圓周率的計算。
Felix Nawothnig 撰寫出可依據給定位數要求,計算並輸出十進位表示法的 Brainfuck
程式 [2],我略作調整,如下: (檔名為 pi.b)
> +++++ +++++ +++++ +++++ +++++ (25 digits)
[<+>>>>>>>>++++++++++<<<<<<<-]>+++++[<+++++++++>-]+>>>>>>+[<<+++[>>[-<]<[>]<-]>
>[>+>]<[<]>]>[[->>>>+<<<<]>>>+++>-]<[<<<<]<<<<<<<<+[->>>>>>>>>>>>[<+[->>>>+<<<<
]>>>>>]<<<<[>>>>>[<<<<+>>>>-]<<<<<-[<<++++++++++>>-]>>>[<<[<+<<+>>>-]<[>+<-]<++
<<+>>>>>>-]<<[-]<<-<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+<<<-[>>+<<-]<]<<<<+>>>
>>>>>[-]>[<<<+>>>-]<<++++++++++<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+>[<<+<+>>>
-]<<<<+<+>>[-[-[-[-[-[-[-[-[-<->[-<+<->>]]]]]]]]]]<[+++++[<<<++++++++<++++++++>
>>>-]<<<<+<->>>>[>+<<<+++++++++<->>>-]<<<<<[>>+<<-]+<[->-<]>[>>.<<<<[+.[-]]>>-]
>[>>.<<-]>[-]>[-]>>>[>>[<<<<<<<<+>>>>>>>>-]<<-]]>>[-]<<<[-]<<<<<<<<]++++++++++.
乍看鬼畫符的程式,注意到最後一個字元是 . (將目前讀寫頭下的值,以對應的字母輸出)
編譯 Brainfuck 直譯器並載入圓周率計算程式:
$ gcc -o bf bf.c
$ ./bf pi.b
在我的電腦 (AMD Ryzen Threadripper 2990WX 32-Core Processor, AMD 重返榮耀!) 搭配
Ubuntu Linux 18.04 LTS,執行時間約為 0.3 秒,ELF 執行檔約佔 6KB 空間。
參考執行輸出如下:
3.141592653589793238462643
若要提高圓周率計算的有效位數,那麼修改 pi.b 的第一行,把 + 指令的數量增加即可。
用雙手駕馭電腦的滋味,真是美妙 :-)
[1] brainf*ck:
https://esolangs.org/wiki/brainfuck
[2]
https://copy.sh/brainfuck/prog/yapi.b
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.246.163
※ 文章代碼(AID): #1SkC6d5C (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1555612071.A.14C.html
→ tyrande: 恩恩 昨晚媽祖也是跟我講這個答案1F 04/19 02:28
推 minifat: 今天還有一萬多人 都被柴員了嗎4F 04/19 02:29
→ cisbpmtw: google pi ten thousand digits11F 04/19 02:34
→ Wand …
推 Wand: 半夜大神出巡,推。13F 04/19 02:39
→ jserv: @q14721472, 回歸初心 (?)16F 04/19 02:43
→ jserv: @a3831038, 那我忘了附上「真香警告」
第一頁要標註「Brainfuck不是Pornhub的新分類」(嗶!)20F 04/19 02:47
→ jserv: @lovesooman, 其實這篇沒寫完,數學原理還沒探討,我正在排版,作為新教材。從 Turing 機器到征服圓周率運算25F 04/19 02:56
→ jserv: @newland, 夜睡不著覺,把 pi 哼成 C 程式28F 04/19 02:58
推 xru03: 強31F 04/19 03:03
→ jserv: @jj1379746, 也是可改用 BF 來講32F 04/19 03:03
推 q0500: 推35F 04/19 03:05
推 Aerci: 恩...略懂39F 04/19 03:12
推 Dinenger: 我修過資訊概論兩學期,跟我想得差不多嘛41F 04/19 03:16
→ jserv: @smallcar801, www.slideshare.net/jserv/vm-construct #43F 04/19 03:19
推 adifdtd: 還真的有brainfuck XDD44F 04/19 03:20
→ jserv: 才能若要充分「浪費」,應該先從設計高階描述轉BF的編譯器開始,過程中可搭配特定的巨集或工具集設計,並且改善虛擬機器的執行效能,甚至設計profiler來追蹤hotspot,當然JIT45F 04/19 03:20
推 DLHZ: 獻出我的膝蓋48F 04/19 03:21
→ jserv: 或AOT編譯器的實作也很吸引人,最後再附上形式化驗證49F 04/19 03:22
推 dsct: 先推 假裝看得懂52F 04/19 03:24
→ jserv: @Splash5, 若要為了嘉瑜設計BF的方言(變種),我好有興趣53F 04/19 03:26
推 drajan: 想不到brainfuck這麼有內涵 看wiki還以為只是來鬧場的55F 04/19 03:31
推 WYchuang: [-[-[-[-[-[-[-[-[-<->[-<+<->>]]]]]]]]]] 這回圈好噁心56F 04/19 03:35
→ jserv: @woifeiwen, 我不是故意跟你的大腦交流的...59F 04/19 03:39
El Brainfuck
A Brainfuck editor & optimizing interpreter, written in JavaScript. It's pretty fast. ...
→ wei115: 為什麼用這直譯器得出的直是3.141135232456912829104152?值62F 04/19 03:45
→ jserv: @wei115, 好問題!Brainfuck的執行結果依賴cell size而定64F 04/19 03:48
→ jserv: 這是BF實作上一個致命的問題,往往導致non-portable
由執行結果可推知,copy.sh的BF實作和我給予的程式對於cell66F 04/19 03:48
→ jserv: size規範不同,8-bit cell會導致4個位數後就有overflow
16-bit cell的BF則會讓537位數後發生overflow
倘若改為32-bit cell,overflow就會在數百萬位數後才發生@twosheep0603, Wikipedia的Brainfuck詞目提到Portabilityissues: Cell size, Array size, End-of-line code,
End-of-file behavior.
@wei115, 若這樣的解釋你可理解,歡迎撰寫可變更cell size的直譯器並調整pi.b的實作,來驗證上述overflow議題69F 04/19 03:50
推 wei115: 喔喔,感謝解惑,之前我寫的都是8bit現在改成16bit和32bit執行結果都與範例一致77F 04/19 03:58
→ jserv: 所以說,BF真是「知易行難」,理解指令的意義只要三分鐘
但涉及到可攜性、最佳化,還有轉譯現有應用,都很難
@tyrande, 昨天媽祖提醒我要自幹C語言編譯器,所以我就趕出一個原始程式碼約2千5百行的小型C語言編譯器,稍後我貼出來79F 04/19 04:00
推 LuMya: 跟我想的差不多 給推84F 04/19 04:20
→ aeolus811tw: 要是你把BBP改成BF就能準確計算了, 不過那個大小應該很變態88F 04/19 05:14
推 abram: 何不 print(“3.1415”)91F 04/19 05:34
→ jserv: HN一則評語很傳神: "Ah yes, Brainfuck. For when assemblyis too easy."97F 04/19 06:16
推 h73o1012: 8==============D~0103F 04/19 06:32
推 traboffic: 我的brainfucked up了109F 04/19 07:34
推 eggbird: 完全不懂,只能推115F 04/19 08:00
推 jhangyu: 是來自新世界的神117F 04/19 08:08
推 ck517: 強119F 04/19 08:16
推 erre: 還是輸陳博,看不到車尾燈124F 04/19 08:28
→ mynewid: 嗯嗯,算寫得不錯125F 04/19 08:28
推 ura1210: 想請問怎麼不用fclose 不需要釋放嗎131F 04/19 08:54
推 yeh0416: hello world139F 04/19 09:33
推 Raynor: 不用fclose是因為FILE *f宣告在for迴圈內的關係嗎?
我記得迴圈結束會自動釋放141F 04/19 09:35
推 ant0210: 嗯嗯 完全看不懂147F 04/19 10:04
推 jwchao: 大神凌晨出巡148F 04/19 10:05
推 coburn: 摸透C語言摸不到C罩杯 推導方程式推不倒小學妹 推一個157F 04/19 10:55
→ jserv: @ura1210, 為了縮減行數,我就偷懶假設底層作業系統能釋放stream I/O資源
@bonfferoni, 一句話: Brainfuck (不是雙關語)
@coburn, 感謝提醒,之後我會補充方程式推導
小學妹也可以談啦,數學軼事挺多
@jhangyu, 人人都該是電腦的主人158F 04/19 10:55
推 conq: 好…好猛164F 04/19 11:04
→ jserv: @amethystboy, 我雙手駕馭後,現在成為專職奶爸165F 04/19 11:05
→ jserv: @iambillno1la, 好的,歡迎發文推坑,我可以多多練習打字167F 04/19 11:09
推 Meerz: 講中文好嗎?169F 04/19 11:33
推 a2470abc: brainfuck也能自幹0.0 AMD重返榮耀了170F 04/19 11:35
推 usoko: 幹既神又無聊XDDDDD172F 04/19 11:40
→ jserv: @usoko, 之後補幾個non-trivial應用,就不會無聊了173F 04/19 11:46
推 penta: 老師 我資質真的不夠ww174F 04/19 11:47
虛擬機器設計與實作 - HackMD
# 虛擬機器設計與實作 :::info 本講座專注在 process virtual machine,像是 JVM 和 Ethereum VM,而非 system virtul machine,後者 ...
推 chigi: 跪了178F 04/19 12:14
推 rog43: 老師又被釣出來了179F 04/19 12:28
--