« brainf*ck で計算機 | メイン | DNS ラウンドロビンと高可用性 (High Availability) »

2006年06月28日

brainf*ck でマジメに素数探索

　「キミならどう書く 2.0 - ROUND 1 - 」の〆切は過ぎていますが、逃避力を発揮して brainf*ck で書いてみました。

　竹迫さんのものとは違い、brainf*ck で素数探索を行っています。でも brute force なアルゴリズムなので遅いです (笑)

>++++[<++++++++>-]                          // 0 pm2 = ' '
>+++++++[<++++++++>-]<+>+++++++++>          // 1 pm1 = '9'  p0 = 9
>++++++++++[<++++++++++>-]<--               // 1 p1= 98  p2 = 0
[
  >[-]<[->+>+<<]>>[-<<+>>]<-                // 2  p2 = p1 m 1
  [
    >[-]<<[->>+>+<<<]>>>[-<<<+>>>]<+        // 3  p3 = p1 p 1  p4 = 0
    [                                      
      >>[-]>[-]<<[>+>+<<-]>>[<<+>>-]<       // 5  p5 = p4  p6 = 0
      >[-]+<[>-<[-]]>[-<                    // 5  if (p5 == 0) then
        <<<[->>+>>+<<<<]>>>>[-<<<<+>>>>]<<+>  // 5    p4 = p2 p 1
      >]<                                  
      <-                                    // 4  p4 m= 1
      <-                                    // 3  p3 m= 1
    ]
    > >[-]+<[[-]>-< ]>[-<                   // 4  if (p4 == 0) then
      >>[-]+<<                              // 4    p6 = 1
      <<[-]+>>                              // 4    p2 = 1
    >]<                                    
    <<-                                     // 2  p2 m= 1
  ]
  >>>> >[-]+<[[-]>-< ]>[-<                  // 6  if (p6 == 0) then
    <<<<<<<.>                               // 0    print pm1
    >>[-]++++++[<<++++++++>>-]              // 2    p2 = 0  p0 p= 48
    <<.>>                                   // 2    print p0
    ++++++[<<-------->>-]                   // 2    p2 = 0  p0 m= 48
    <<<<.>>>>>>>>                           // 6    print pm2
  >]<
  <<<<<-                                    // 1  p1 m= 1
  >>[-]<<<[->>+>+<<<]>>>[-<<<+>>>]<         // 2  p2 = p0  p3 = 0
  >+<[[-]>-<                                // 2  if (p2 == 0) then
    <<->>                                   // 2    p0 m= 1
  ]>[-<                                     // 2  else
    <<+++++++++                             // 0    p0 p= 9
    <->>>                                   // 2    pm1 m= 1
  >]<
  <                                         // 1
]

　これで 456 バイトです注。特にコードサイズの最適化はしていません。

　また、速度の最適化もしていないので、実行にあたっては高速な処理系をご用意ください。試した範囲では、BF online では10秒ほどで結果が表示されましたが、弾さんの処理系では、１分たっても終わらないような感じです。

　それでは、 Have fun!

注: 手で数えたので違うかも

投稿者 kazuho : 2006年06月28日 17:12 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/667

このリストは、次のエントリーを参照しています: brainf*ck でマジメに素数探索:

» brainfu.k - BF2JS opimizing compiler from 404 Blog Not Found
BFにはまっておられる奥さんに。 Kazuho@Cybozu Labs: brainf*ck でマジメに素数探索 また、速度の最適化もしていないので、... [続きを読む]

トラックバック時刻: 2006年07月04日 08:21

コメント

Language::BF で
Perlでコンパイル実行
> /usr/bin/time perl -Ilib t/prime.pl
> 97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 07 05 03 02
> 18.23 real 17.85 user 0.08 sys
C に変換
>/usr/bin/time ./a.out
>97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 07 05 03 02
> 0.39 real 0.38 user 0.00 sys

でした。compilerでこれですから、interpreterでは遅いのも納得。

Dan the Brainfu.ker

投稿者 弾 : 2006年06月28日 18:35

> compilerでこれですから、interpreterでは遅いのも納得。

ありがとうございます。コンパイラでもこれだけかかるのですね。

アルゴリズムと bf の冗長性、両方のせいでしょうか (^^;

投稿者 kazuho : 2006年06月28日 20:53