brainfuck

シクシク素数列 brainfuck版

シクシク素数列 Advent Calenderの25日目です。

最終日の今日は、みんな大好き(?)、brainfuckです。


シクシク素数のリストをコードに埋め込む

brainfuckのプログラミングでは一番愚直な恥ずかしくて誰もしなかった方法です。Nが100以下となっているので、予め100個のシクシク素数を計算しておくだけで済みます。

というわけで、100個のシクシク素数のリストを用意しました。

19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319

(これは、私が以前にbrainfuckで書いた素数を求める美しいプログラムを使って求めた素数から、4と9を含む数を抽出したものです。)

このリストを使えば、後は入力された数の分だけリストの先頭から順に出力していくだけです。(その辺りの詳しい説明は割愛します。)

完成したコードがこちらです。

>>,----------[>,----------]

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

>+>+++++++++>-
>++>+++++++++>-
>++++>+>-
>++++>+++>-
>++++>+++++++>-
>+++++>+++++++++>-
>+++++++>+++++++++>-
>++++++++>+++++++++>-
>+++++++++>+++++++>-
>+>>+++++++++>-
>+>+++>+++++++++>-
>+>++++>+++++++++>-
>+>+++++++>+++++++++>-
>+>+++++++++>+>-
>+>+++++++++>+++>-
>+>+++++++++>+++++++>-
>+>+++++++++>+++++++++>-
>++>++>+++++++++>-
>++>+++>+++++++++>-
>++>++++>+>-
>++>++++++>+++++++++>-
>++>+++++++++>+++>-
>+++>++++>+++++++>-
>+++>++++>+++++++++>-
>+++>+++++>+++++++++>-
>+++>+++++++>+++++++++>-
>+++>++++++++>+++++++++>-
>+++>+++++++++>+++++++>-
>++++>>+>-
>++++>>+++++++++>-
>++++>+>+++++++++>-
>++++>++>+>-
>++++>+++>+>-
>++++>+++>+++>-
>++++>+++>+++++++++>-
>++++>++++>+++>-
>++++>++++>+++++++++>-
>++++>+++++>+++++++>-
>++++>++++++>+>-
>++++>++++++>+++>-
>++++>++++++>+++++++>-
>++++>+++++++>+++++++++>-
>++++>++++++++>+++++++>-
>++++>+++++++++>+>-
>++++>+++++++++>+++++++++>-
>+++++>>+++++++++>-
>+++++>++++>+>-
>+++++>++++>+++++++>-
>+++++>++++++>+++++++++>-
>+++++>+++++++++>+++>-
>+++++>+++++++++>+++++++++>-
>++++++>+>+++++++++>-
>++++++>++++>+>-
>++++++>++++>+++>-
>++++++>++++>+++++++>-
>++++++>+++++>+++++++++>-
>++++++>+++++++++>+>-
>+++++++>>+++++++++>-
>+++++++>+>+++++++++>-
>+++++++>+++>+++++++++>-
>+++++++>++++>+++>-
>+++++++>++++++>+++++++++>-
>+++++++>+++++++++>+++++++>-
>++++++++>>+++++++++>-
>++++++++>++>+++++++++>-
>++++++++>+++>+++++++++>-
>++++++++>+++++>+++++++++>-
>+++++++++>>+++++++>-
>+++++++++>+>+>-
>+++++++++>+>+++++++++>-
>+++++++++>++>+++++++++>-
>+++++++++>+++>+++++++>-
>+++++++++>++++>+>-
>+++++++++>++++>+++++++>-
>+++++++++>+++++>+++>-
>+++++++++>++++++>+++++++>-
>+++++++++>+++++++>+>-
>+++++++++>+++++++>+++++++>-
>+++++++++>++++++++>+++>-
>+++++++++>+++++++++>+>-
>+++++++++>+++++++++>+++++++>-
>+>>>+++++++++>-
>+>>+>+++++++++>-
>+>>+++>+++++++++>-
>+>>++++>+++++++++>-
>+>>++++++>+++++++++>-
>+>>+++++++++>+>-
>+>>+++++++++>+++>-
>+>>+++++++++>+++++++>-
>+>+>>+++++++++>-
>+>+>++>+++++++++>-
>+>+>+++++++++>+++>-
>+>++>++>+++++++++>-
>+>++>++++>+++++++++>-
>+>++>+++++>+++++++++>-
>+>++>+++++++>+++++++++>-
>+>++>++++++++>+++++++++>-
>+>++>+++++++++>+>-
>+>++>+++++++++>+++++++>-
>+>+++>+>+++++++++>-

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

空白・改行を取り除けば2299バイトです。


なぜ普通に計算しないのか

普通に計算しない理由は2つあります。

1つ目は、今回扱う数が(一般的な処理系において)1バイトの整数で表せないからです。前述のbrainfuckで素数を求めるプログラムでは、数値の表現に2バイトを使っていますが、非常に効率が悪く、コードの量も嵩んでいます。

2つ目は、数値が4か9を含むかを調べる時と出力する時の2回、十進表現に変換する必要があるためです。素数かどうかを判定する計算においては、1バイト単位(256進数)で計算した方が繰り上がり等の処理に都合がいいので十進法に統一したとしてもかなりのコストがかかります。十進数と2バイト整数の両方を保持しておくという方法もありますが、今度は数値のインクリメントの処理が複雑化します。

リストを埋め込むのが、一番面倒くさくない方法だということです。そして、この方法が一番効率がよく、コードの量も少なくて済みます。


終わりに

最近は関数型のesolangにハマっていて、esolangを1つ自作してしまったので、そちらの方も見て頂けるとありがたいです。