Re: [問卦] 不用函數庫和亂數寫程式求pi值的方法?

看板Gossiping作者jserv (松鼠)時間5年前 (2019/04/19 02:27)推噓140(142推 2噓 101→)

留言245則, 156人參與討論串3/4 (看更多)

※ 引述《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; < --p; + ++*p; - --*p; . putchar(*p); , *p = getchar(); [ while (*p) { ] } 也就是說，下方的 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 (r = 0; (c = p[r]); r++) { if (c == '>') t++; if (c == '<') t--; if (c == '+') d[t]++; if (c == '-') d[t]--; if (c == '.') putc(d[t], stdout); for (e = 0; c == '[' && !d[t]; r++) { if (p[r] == '[') e++; if ((p[r] == ']') && (e-- == 1)) break; } 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 ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1555612071.A.14C.html

→

tyrande

04/19 02:28, 5年前 , 1^F

04/19 02:28, 1^F

推

bibico0206

04/19 02:28, 5年前 , 2^F

04/19 02:28, 2^F

→

lovesooman

04/19 02:29, 5年前 , 3^F

04/19 02:29, 3^F