---

※ 引述《fragmentwing (片翼碎夢)》之銘言：
: 小弟程式設計新手
: 看到後面的講義習題要算圓周率
: 如果不用亂數，也不用函數庫的話
: 我自己用了一個在寫之前就覺得很浪費電腦能力的方法
: 在電腦能力處理極限，還沒法精確到小數點後第二位呢
: 鄉民會怎麼用程式求圓周率呢?

這裡提供一種途徑，只用到 C 語言標準函式庫裡頭的以下函式:
* fopen / fclose
* getc / putc

既然上述說要「浪費電腦能力」，那我們不妨試試這個策略:
a. 實作符合 Turing completeness (圖靈完備) 的 Brainfuck 程式語言 [1]
   執行環境;
b. 撰寫 Brainfuck 程式，使其得以計算圓周率，並用十進位浮點數輸出;

可將 Brainfuck 的執行環境設想為一台機器，擁有一個讀寫頭及無限長的紙帶，
機器會依下列指令進行操作:
    > : 使讀寫頭在紙帶上前進一格
    < : 使讀寫頭在紙帶上後退一格

    , : 將目前讀寫頭下的字母讀入並轉為數字後寫回

    [ : 比較目前的值，若不為 0 即前進，若為 0 就略過指令，直到遇上匹配的 ]
    ] : 比較目前的值，若不為 0，指令要跳回上個出現 [ 的位置

不難發現，作為一個「知易行難」的程式語言，Brainfuck 僅有 8 個指令，其中



也就是說，下方的 Brainfuck 程式碼：
    +++++[-]

對應到 C 語言程式碼為：
    *p = +5;
        *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[]) {
    for (FILE *f = fopen(v[1], "r"); f && (c = getc(f)) != EOF; p[r++] = c);
        }
        }
    }
}


重複 (repetition，這也是 [ ] 的行為)，Brainfuck 這台機器具備上述四項特徵，
是 Turing completeness。依據 Alan Turing 的觀點，這樣的一台機器，即可模擬
人類所能進行的任何計算過程，自然就包含圓周率的計算。

Felix Nawothnig 撰寫出可依據給定位數要求，計算並輸出十進位表示法的 Brainfuck
程式 [2]，我略作調整，如下: (檔名為 pi.b)

>  +++++ +++++ +++++ +++++ +++++ (25 digits)

[<+>>>>>>>>++++++++++<<<<<<<-]>+++++[<+++++++++>-]+>>>>>>+[<<+++[>>[-<]<[>]<-]>
]>>>>>]<<<<[>>>>>[<<<<+>>>>-]<<<<<-[<<++++++++++>>-]>>>[<<[<+<<+>>>-]<[>+<-]<++
-]<<<<+<+>>[-[-[-[-[-[-[-[-[-<->[-<+<->>]]]]]]]]]]<[+++++[<<<++++++++<++++++++>
>>>-]<<<<+<->>>>[>+<<<+++++++++<->>>-]<<<<<[>>+<<-]+<[->-<]>[>>.<<<<[+.[-]]>>-]
>[>>.<<-]>[-]>[-]>>>[>>[<<<<<<<<+>>>>>>>>-]<<-]]>>[-]<<<[-]<<<<<<<<]++++++++++.



    $ ./bf pi.b

在我的電腦 (AMD Ryzen Threadripper 2990WX 32-Core Processor, AMD 重返榮耀!) 搭配
Ubuntu Linux 18.04 LTS，執行時間約為 0.3 秒，ELF 執行檔約佔 6KB 空間。

參考執行輸出如下:
    3.141592653589793238462643



[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