※ 本文為 MindOcean 轉寄自 ptt.cc 更新時間: 2019-04-19 12:39:18
看板 Gossiping
作者 標題 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 的運算
. : 將目前讀寫頭下的值,以對應的字母輸出
- : 對目前讀寫頭下的值,進行遞減 1 的運算
. : 將目前讀寫頭下的值,以對應的字母輸出
, : 將目前讀寫頭下的字母讀入並轉為數字後寫回
[ : 比較目前的值,若不為 0 即前進,若為 0 就略過指令,直到遇上匹配的 ]
] : 比較目前的值,若不為 0,指令要跳回上個出現 [ 的位置
不難發現,作為一個「知易行難」的程式語言,Brainfuck 僅有 8 個指令,其中
2 個是 I/O 動作。作為 Turing machine 的實踐,Brainfuck 對記憶體單元作直接
存取,對應到 C 語言的概念來說,如果 char *p 指向記憶體區塊的話,Brainfuck
語言的 8 個指令可對照為以下 C 等價敘述:
存取,對應到 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 的判斷) 以及
一台理想機器的描述:機器具有無限的儲存 (storage,也就是無限長的紙帶)、運算
(arithmetic,如遞增和遞減)、條件判斷 ([ ] 涉及目前值是否為 0 的判斷) 以及
重複 (repetition,這也是 [ ] 的行為),Brainfuck 這台機器具備上述四項特徵,
是 Turing completeness。依據 Alan Turing 的觀點,這樣的一台機器,即可模擬
人類所能進行的任何計算過程,自然就包含圓周率的計算。
Felix Nawothnig 撰寫出可依據給定位數要求,計算並輸出十進位表示法的 Brainfuck
程式 [2],我略作調整,如下: (檔名為 pi.b)
> +++++ +++++ +++++ +++++ +++++ (25 digits)
[<+>>>>>>>>++++++++++<<<<<<<-]>+++++[<+++++++++>-]+>>>>>>+[<<+++[>>[-<]<[>]<-]>
>[>+>]<[<]>]>[[->>>>+<<<<]>>>+++>-]<[<<<<]<<<<<<<<+[->>>>>>>>>>>>[<+[->>>>+<<<<
]>>>>>]<<<<[>>>>>[<<<<+>>>>-]<<<<<-[<<++++++++++>>-]>>>[<<[<+<<+>>>-]<[>+<-]<++<<+>>>>>>-]<<[-]<<-<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+<<<-[>>+<<-]<]<<<<+>>>
>>>>>[-]>[<<<+>>>-]<<++++++++++<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]>[-]>+>[<<+<+>>>
-]<<<<+<+>>[-[-[-[-[-[-[-[-[-<->[-<+<->>]]]]]]]]]]<[+++++[<<<++++++++<++++++++>>>>-]<<<<+<->>>>[>+<<<+++++++++<->>>-]<<<<<[>>+<<-]+<[->-<]>[>>.<<<<[+.[-]]>>-]
>[>>.<<-]>[-]>[-]>>>[>>[<<<<<<<<+>>>>>>>>-]<<-]]>>[-]<<<[-]<<<<<<<<]++++++++++.
乍看鬼畫符的程式,注意到最後一個字元是 . (將目前讀寫頭下的值,以對應的字母輸出)
編譯 Brainfuck 直譯器並載入圓周率計算程式:
編譯 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
→ : 恩恩 昨晚媽祖也是跟我講這個答案1F 04/19 02:28
推 : 阿伯,早點睡 不要熬夜2F 04/19 02:28
→ : 幹 不要回這種好嗎 我還不想睡覺3F 04/19 02:29
推 : 今天還有一萬多人 都被柴員了嗎4F 04/19 02:29
推 : 先推再看5F 04/19 02:30
推 : 先推不然別人以為我看不懂6F 04/19 02:30
推 : 先推7F 04/19 02:31
→ : +<>< +<><8F 04/19 02:33
推 : jserv 先給推9F 04/19 02:33
推 : 松鼠竟然也投奔真香世界了10F 04/19 02:33
→ : google pi ten thousand digits11F 04/19 02:34
推 : cool12F 04/19 02:35
推 : 半夜大神出巡,推。13F 04/19 02:39
推 : AMD 重返榮耀!14F 04/19 02:42
推 : ...為什麼要這樣子算15F 04/19 02:42
→ : @q14721472, 回歸初心 (?)16F 04/19 02:43
推 : ......17F 04/19 02:45
推 : 跪著推18F 04/19 02:45
推 : 推19F 04/19 02:46
→ : @a3831038, 那我忘了附上「真香警告」20F 04/19 02:47
→ : 第一頁要標註「Brainfuck不是Pornhub的新分類」(嗶!)
→ : 第一頁要標註「Brainfuck不是Pornhub的新分類」(嗶!)
推 : 第一次前2022F 04/19 02:51
推 : 強23F 04/19 02:54
推 : 半夜睡不著覺24F 04/19 02:55
→ : @lovesooman, 其實這篇沒寫完,數學原理還沒探討,我正在25F 04/19 02:56
→ : 排版,作為新教材。從 Turing 機器到征服圓周率運算
→ : 排版,作為新教材。從 Turing 機器到征服圓周率運算
推 : 講中文好嗎27F 04/19 02:57
→ : @newland, 夜睡不著覺,把 pi 哼成 C 程式28F 04/19 02:58
推 : 朝聖推29F 04/19 03:01
推 : 狂30F 04/19 03:01
推 : 強31F 04/19 03:03
→ : @jj1379746, 也是可改用 BF 來講32F 04/19 03:03
推 : 厲害33F 04/19 03:04
推 : 推34F 04/19 03:05
推 : 推35F 04/19 03:05
推 : 跪36F 04/19 03:07
推 : ob'_'ov AMD讚37F 04/19 03:10
推 : 我老闆問我為啥要跪著上班38F 04/19 03:10
推 : 恩...略懂39F 04/19 03:12
推 : AMD YES40F 04/19 03:12
推 : 我修過資訊概論兩學期,跟我想得差不多嘛41F 04/19 03:16
推 : 還弄一個直譯器真的很浪費才能…跪著看完42F 04/19 03:17
→ : @smallcar801, www.slideshare.net/jserv/vm-construct #43F 04/19 03:19
推 : 還真的有brainfuck XDD44F 04/19 03:20
→ : 才能若要充分「浪費」,應該先從設計高階描述轉BF的編譯器45F 04/19 03:20
→ : 開始,過程中可搭配特定的巨集或工具集設計,並且改善虛擬
→ : 機器的執行效能,甚至設計profiler來追蹤hotspot,當然JIT
→ : 開始,過程中可搭配特定的巨集或工具集設計,並且改善虛擬
→ : 機器的執行效能,甚至設計profiler來追蹤hotspot,當然JIT
推 : 獻出我的膝蓋48F 04/19 03:21
→ : 或AOT編譯器的實作也很吸引人,最後再附上形式化驗證49F 04/19 03:22
推 : 跪求whitespace或chicken寫法50F 04/19 03:23
推 : 半夜看見神 這個好有趣51F 04/19 03:23
推 : 先推 假裝看得懂52F 04/19 03:24
→ : @Splash5, 若要為了嘉瑜設計BF的方言(變種),我好有興趣53F 04/19 03:26
推 : 半夜不睡看見神了54F 04/19 03:30
推 : 想不到brainfuck這麼有內涵 看wiki還以為只是來鬧場的55F 04/19 03:31
推 : [-[-[-[-[-[-[-[-[-<->[-<+<->>]]]]]]]]]] 這回圈好噁心56F 04/19 03:35
推 : 公 三小 阿我怎麼按推了57F 04/19 03:35
推 : 有神快拜58F 04/19 03:38
→ : @woifeiwen, 我不是故意跟你的大腦交流的...59F 04/19 03:39
推 : 太帥了60F 04/19 03:41
El Brainfuck
A Brainfuck editor & optimizing interpreter, written in JavaScript. It's pretty fast. ...
A Brainfuck editor & optimizing interpreter, written in JavaScript. It's pretty fast. ...
→ : 為什麼用這直譯器得出的直是3.141135232456912829104152?62F 04/19 03:45
→ : 值
→ : 值
→ : @wei115, 好問題!Brainfuck的執行結果依賴cell size而定64F 04/19 03:48
推 : 推宅色夫65F 04/19 03:48
→ : 這是BF實作上一個致命的問題,往往導致non-portable66F 04/19 03:48
→ : 由執行結果可推知,copy.sh的BF實作和我給予的程式對於cell
→ : 由執行結果可推知,copy.sh的BF實作和我給予的程式對於cell
→ : 理論上無限長的紙帶被直譯器限制了?68F 04/19 03:50
→ : size規範不同,8-bit cell會導致4個位數後就有overflow69F 04/19 03:50
→ : 16-bit cell的BF則會讓537位數後發生overflow
→ : 倘若改為32-bit cell,overflow就會在數百萬位數後才發生
→ : @twosheep0603, Wikipedia的Brainfuck詞目提到Portability
→ : issues: Cell size, Array size, End-of-line code,
→ : End-of-file behavior.
→ : @wei115, 若這樣的解釋你可理解,歡迎撰寫可變更cell size
→ : 的直譯器並調整pi.b的實作,來驗證上述overflow議題
→ : 16-bit cell的BF則會讓537位數後發生overflow
→ : 倘若改為32-bit cell,overflow就會在數百萬位數後才發生
→ : @twosheep0603, Wikipedia的Brainfuck詞目提到Portability
→ : issues: Cell size, Array size, End-of-line code,
→ : End-of-file behavior.
→ : @wei115, 若這樣的解釋你可理解,歡迎撰寫可變更cell size
→ : 的直譯器並調整pi.b的實作,來驗證上述overflow議題
推 : 喔喔,感謝解惑,之前我寫的都是8bit現在改成16bit和32bit77F 04/19 03:58
→ : 執行結果都與範例一致
→ : 執行結果都與範例一致
→ : 所以說,BF真是「知易行難」,理解指令的意義只要三分鐘79F 04/19 04:00
→ : 但涉及到可攜性、最佳化,還有轉譯現有應用,都很難
→ : @tyrande, 昨天媽祖提醒我要自幹C語言編譯器,所以我就趕出
→ : 一個原始程式碼約2千5百行的小型C語言編譯器,稍後我貼出來
→ : 但涉及到可攜性、最佳化,還有轉譯現有應用,都很難
→ : @tyrande, 昨天媽祖提醒我要自幹C語言編譯器,所以我就趕出
→ : 一個原始程式碼約2千5百行的小型C語言編譯器,稍後我貼出來
推 : 耶,每個字母我都看的懂耶!啾咪83F 04/19 04:05
推 : 跟我想的差不多 給推84F 04/19 04:20
推 : 釣到了==85F 04/19 04:34
推 : ...這什麼86F 04/19 04:50
推 : 推87F 04/19 05:08
→ : 要是你把BBP改成BF就能準確計算了, 不過那個大小應該88F 04/19 05:14
→ : 很變態
→ : 很變態
→ : 那部90F 04/19 05:22
推 : 何不 print(“3.1415”)91F 04/19 05:34
→ : @aeolus811tw, 量化分析很有趣呀92F 04/19 06:09
→ : @abram, printf函式內建的format string本質上也是Turing
→ : 完備,這意味著,上述的BF直譯器能透過printf來實作 (!)
→ : 詳見: https://github.com/HexHive/printbf
→ : @abram, printf函式內建的format string本質上也是Turing
→ : 完備,這意味著,上述的BF直譯器能透過printf來實作 (!)
→ : 詳見: https://github.com/HexHive/printbf
GitHub - HexHive/printbf: Brainfuck interpreter inside printf
Brainfuck interpreter inside printf. Contribute to HexHive/printbf development by creating an account on GitHub. ...
Brainfuck interpreter inside printf. Contribute to HexHive/printbf development by creating an account on GitHub. ...
推 : 好96F 04/19 06:15
→ : HN一則評語很傳神: "Ah yes, Brainfuck. For when assembly97F 04/19 06:16
→ : is too easy."
→ : is too easy."
推 : 啊啊 樓下說略懂略懂99F 04/19 06:25
推 : 先推再說100F 04/19 06:25
推 : 推101F 04/19 06:26
推 : 推102F 04/19 06:29
推 : 8==============D~0103F 04/19 06:32
推 : 我希望用雙手駕馭C 罩杯104F 04/19 06:55
推 : 好羨慕看得懂的人Q_Q105F 04/19 07:12
推 : 推106F 04/19 07:17
推 : 神人107F 04/19 07:30
推 : 嗯嗯108F 04/19 07:33
推 : 我的brainfucked up了109F 04/19 07:34
推 : 2990wx...110F 04/19 07:40
推 : 推111F 04/19 07:43
推 : 寫沙小112F 04/19 07:48
推 : 嗯 跟我想的差不多113F 04/19 07:50
推 : 教授好!114F 04/19 07:55
推 : 完全不懂,只能推115F 04/19 08:00
推 : 推116F 04/19 08:01
推 : 是來自新世界的神117F 04/19 08:08
推 : 推118F 04/19 08:11
推 : 強119F 04/19 08:16
推 : 有神快拜120F 04/19 08:21
推 : 大神受小弟一拜!!121F 04/19 08:23
推 : 神人出現122F 04/19 08:24
噓 : 公啥洨123F 04/19 08:26
推 : 還是輸陳博,看不到車尾燈124F 04/19 08:28
→ : 嗯嗯,算寫得不錯125F 04/19 08:28
推 : 有神快敗126F 04/19 08:39
推 : 快推127F 04/19 08:40
推 : 這!!強128F 04/19 08:44
推 : 跟我想的一樣129F 04/19 08:49
推 : 推130F 04/19 08:53
推 : 想請問怎麼不用fclose 不需要釋放嗎131F 04/19 08:54
推 : 完全看不懂=.=132F 04/19 08:59
推 : 推133F 04/19 09:02
推 : 推134F 04/19 09:04
推 : 靠 太專業了吧135F 04/19 09:06
推 : 松鼠重返榮耀136F 04/19 09:11
推 : 有神快拜:)137F 04/19 09:11
推 : 好噁138F 04/19 09:24
推 : hello world139F 04/19 09:33
推 : 老師超強140F 04/19 09:34
推 : 不用fclose是因為FILE *f宣告在for迴圈內的關係嗎?141F 04/19 09:35
→ : 我記得迴圈結束會自動釋放
→ : 我記得迴圈結束會自動釋放
→ : 推,長知識143F 04/19 09:40
推 : 跪惹144F 04/19 09:48
推 : 嗯嗯嗯嗯 中間那段再補充些 就更好了145F 04/19 10:00
推 : …好猛146F 04/19 10:03
推 : 嗯嗯 完全看不懂147F 04/19 10:04
推 : 大神凌晨出巡148F 04/19 10:05
推 : 推...辛苦了...149F 04/19 10:06
推 : 太屌= =150F 04/19 10:16
推 : 嗚wow152F 04/19 10:29
推 : 三小…153F 04/19 10:35
→ : 優文154F 04/19 10:49
推 : 神人 @@155F 04/19 10:49
推 : 太神啦156F 04/19 10:51
推 : 摸透C語言摸不到C罩杯 推導方程式推不倒小學妹 推一個157F 04/19 10:55
→ : @ura1210, 為了縮減行數,我就偷懶假設底層作業系統能釋放158F 04/19 10:55
→ : stream I/O資源
→ : @bonfferoni, 一句話: Brainfuck (不是雙關語)
→ : @coburn, 感謝提醒,之後我會補充方程式推導
→ : 小學妹也可以談啦,數學軼事挺多
→ : @jhangyu, 人人都該是電腦的主人
→ : stream I/O資源
→ : @bonfferoni, 一句話: Brainfuck (不是雙關語)
→ : @coburn, 感謝提醒,之後我會補充方程式推導
→ : 小學妹也可以談啦,數學軼事挺多
→ : @jhangyu, 人人都該是電腦的主人
推 : 好…好猛164F 04/19 11:04
→ : @amethystboy, 我雙手駕馭後,現在成為專職奶爸165F 04/19 11:05
推 : 恩恩 老師跟我想的一樣166F 04/19 11:07
→ : @iambillno1la, 好的,歡迎發文推坑,我可以多多練習打字167F 04/19 11:09
推 : 有神快拜168F 04/19 11:30
推 : 講中文好嗎?169F 04/19 11:33
推 : brainfuck也能自幹0.0 AMD重返榮耀了170F 04/19 11:35
推 : 朝聖推171F 04/19 11:40
推 : 幹既神又無聊XDDDDD172F 04/19 11:40
→ : @usoko, 之後補幾個non-trivial應用,就不會無聊了173F 04/19 11:46
推 : 老師 我資質真的不夠ww174F 04/19 11:47
→ : @penta, 歡迎一同學習: http://hackfoldr.org/dykc/175F 04/19 11:50
→ : @ant0210, 可參閱 https://hackmd.io/s/SkBsZoReb
→ : @ant0210, 可參閱 https://hackmd.io/s/SkBsZoReb
虛擬機器設計與實作 - HackMD
# 虛擬機器設計與實作 :::info 本講座專注在 process virtual machine,像是 JVM 和 Ethereum VM,而非 system virtul machine,後者 ...
# 虛擬機器設計與實作 :::info 本講座專注在 process virtual machine,像是 JVM 和 Ethereum VM,而非 system virtul machine,後者 ...
推 : push177F 04/19 12:05
推 : 跪了178F 04/19 12:14
推 : 老師又被釣出來了179F 04/19 12:28
--
回列表(←)
分享