もっと難読 FizzBuzz: ふるあだー活用

昨日の続き。

モダンな CPU にはせっかく1クロックで動く32bitフルアダーが載っているんですから、それを有効活用しないともったいない、ということで、もっと難読 FizzBuzz。

#!/bin/env perl

my $bits = 16;
my @strs = ( undef, "Fizz\n", "Buzz\n", "FizzBuzz\n" );

for ( my $i = 1; $i < 100; $i++ )
{
    $bits += 17;
    my $tmp = ($bits + 33) & 132;
    $bits += $tmp >> 2;
    $bits |= $tmp >> 3;
    $bits &= 115;

    $tmp = ((((($bits | 8) - 33) & 132) * 17) >> 6) & 3;
    print $tmp ? $strs[$tmp] : "$i\n";
}

出力は $strs[$tmp] || "$i\n" でもいいんですが、もっとも多い $i の表示の際に配列参照を起こさないことを意識してみました。

最後だけ分岐レスにはできませんでしたが、C に落とした際には、ループのお尻に分解されて jmp 命令は1つ減りそうです。

高速化なんて考えても、print が圧倒的なボトルネックなのでまったく意味ないんですけど、きもちだけ。

今度のカウンタは、諸般の都合で 00->01->10->00, 001->010->011->100->101->001 とビットは変わっていきます。

ちょっとだけ補足

2進数表記でネタばらし。

my $bits = 0b00010000;         # 上位ニブルを5のカウンタに、下位ニブルを3のカウンタに

    $bits += 0b00010001;       # 上位ニブルと下位ニブルのカウンタをインクリメント

    # 以下、上位ニブルに対しては 110 -> 001, 下位ニブルに対しては 11 -> 00 と置換
    my $tmp = $bits + 0b00100001; # b7 = (b5 == 1 && b6 == 1), b2 = (b0 == 1 && b1 == 1)
    $tmp &= 0b10000100;        # b7 と b2 だけ抽出
    $bits += $tmp >> 2;        # 上位ニブル: 0110 -> 1000 / 下位ニブル 0011 -> 0100 
    $bits |= $tmp >> 3;        # 上位ニブル: 1000 -> 1001
    $bits &= 0b01110011;       # 余計なビットをマスク

    # 上位ニブルが 001 である / 下位ニブルが 00 である という条件を 0〜3 の数値に変換
    $tmp = $bits | 0b00001000; # 次の引き算でボローが上位ニブルに伝播しないように
    $tmp -= 0b00100001;        # b7 = (b5 == 0 && b6 == 0), b2 = (b0 == 0 && b1 == 0) 
    $tmp &= 0b10000100;        # b7 と b2 だけを抽出
    $tmp *= 0b00010001;        # b6 = b2 (shift して or したほうが速いかも)
    $tmp >>= 6;                # b0 = b6, b1 = b7
    $tmp &= 0b00000011;        # b0, b1 以外をマスク

マスクを明示的にしている部分がいくつかあるのが汚いですね……。気合を入れれば、わざとらしいマスク操作をもっと削れるかもしれません。才能ある方の仕事に期待します（笑）

また、4bitで切らずに16bitでカウンタを分けるようにすることで最後にマスクが要らなくなりますが、*17 が *65537 になってしまうことによって、ニモニック内で即値であらわせない CPU が出てきたり、掛ける数が大きくなると掛け算にかかるサイクル数が増える CPU があったり、とデメリットが脳裏を去来したのでやめておきました。

もっとマニアックなビットオペレーションが知りたい方には以下の書籍がお勧めです:
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか