No Such Blog or Diary

Template でプログラム中の条件分岐を全てやってしまうことはできないだろうか？　最近こんなことを考えていたのだが，if 文だけなら何とかなるなぁと思ってみた．各処理ブロックをTemplate にして，必要な変数を全て Template 引数にして，条件分岐に Selector を使って条件に応じて適した Template クラスの calc() メソッドを呼ばせると．このとき，else 節がいらない場合には， Nothing という何もしない Template を使うと．たとえば，x が y より小さいときだけ出力する場合には，こんなかたちでできるはず．

template <bool judge, typename T, typename F>
struct Selector{ typedef T val; };
 
template <typename T, typename F>
struct Selector<false, T, F>{   typedef F val; };
 
struct Nothing{ inline static void calc(){}};
 
template<unsigned int x, unsigned int y>
struct Printer{
  inline static void calc(){
    cout << x << " < " << y << endl;
  }
};
 
template<unsigned int x, unsigned int y>
struct MinThenPrint<x, y >{
  inline static void calc(){
    Selector<(x < y), Printer<x,y>,Nothing>::val::calc();
  }
};

テンプレートでプログラムするための部品として if に相当する Select なるものがある．これを使うと then 節と else 節の一方のみの評価ができるので安全．ためしに Collatz 予想のやつで遊んでみた．

template<bool, typename T, typename F>
struct Select{
    typedef T val;
};
template<typename T, typename F>
struct Select<false, T, F>{
    typedef F val;
};
template <int n>
struct Collatz {
    const static int val = Select<(n&1)==0, Collatz<n/2>, Collatz<3*n+1> >::val::val + 1;
};
template <>
struct Collatz<1> {
    const static int val = 0;
};
int main(int argc, char *argv[])
{
    cout << Collatz<3>::val << endl;
    return 0;
}

覆面算の計算で各桁をテンプレートで生成してやることにした．これでソースは見やすくなった．しかも，全部を展開してあった前のコードより若干速いらしい．ちなみに，関数テンプレートの部分特化(Partial Specialization)は禁止されているようなので，部分的にインスタンス化するため仕方なくクラスを使う羽目になった．ま，次は答えをテンプレートで生成だな．

#include <iostream>
using namespace std;
template<const int m, const int l>
class Calc{
public:
    inline void calc(unsigned int &x, unsigned int &y, unsigned int (&digits)[m])
    {
        const int n = m/4*3 - l*3;
        unsigned int d0 = digits[n];
        for(int i0 = n; i0 < m; i0++){
            digits[n] = digits[i0];
            digits[i0] = d0;
            x = (digits[n]<<(4*(n/3))) | (x&((1<<(4*(n/3)))-1));
            unsigned int d1 = digits[n+1];
            for(int j0 = n+1; j0 < m; j0++){
                digits[n+1] = digits[j0];
                digits[j0] = d1;
                y = (digits[n+1]<<(4*(n/3))) | (y&((1<<(4*(n/3)))-1));
                if(n==0 && y >= x) {            // omit symmetric pattern
                    digits[j0] = digits[n+1];
                    continue;
                }
                unsigned int z1 = ((x * y) >> (4*(n/3)))& 0xf;
                int k1 = n+2;
                for(; k1 < m; k1++) if (digits[k1]==z1) break;
                if(k1 >= m) {
                    digits[j0] = digits[n+1];
                    continue;
                }
                digits[k1] = digits[n+2];
                digits[n+2] = z1;
                Calc<m,l-1>().calc(x, y, digits);
                digits[n+2] = digits[k1];
                digits[k1] = z1;
                digits[j0] = digits[n+1];
            }
            digits[n+1] = d1;
            digits[i0] = digits[n];
        }
        x &=((1<<(4*(n/3)))-1);
        digits[n] = d0;
    }
};
template<const int m>
class Calc<m,0>{
public:
    inline void calc(unsigned int &x, unsigned int &y, unsigned int (&digits)[m])
    {
        const int n = m/4*3;
        unsigned int z4 = ((x * y) >> (4*(n/3)));
        unsigned int ds[m-n];
        for(int i = 0; i < (m-n); i++){
            ds[i] = digits[i+n];
        }
        int i = 0;
        for(; i < m-n; i++){
            int k4 = i;
            unsigned int z5 = z4&0xf;
            z4>>=4;
            for(; k4 < m-n; k4++) if (ds[k4]==z5) break;
            if(k4 >= m-n) break;
            ds[k4] = ds[i];
        }
        if(i >=m-n && ds[m-n-1]!=0){
            cout << x << " * " << y << " = " << x*y << endl;
            cout << y << " * " << x << " = " << x*y << endl;
        }
    }
};
int main(int argc, char *argv[])
{
    const int m = 16;
    cout << hex;
    unsigned int digits[m];
    for(int i = 0; i < m; i++){
        digits[i] = i;
    }
    unsigned int x = 0;
    unsigned int y = 0;
    Calc<m,m/4>().calc(x,y,digits);
    return 0;
}

ということで，１６進の覆面算プログラムを作業の合間に組んでみた．８重の for ループでぶん回す．裏で別のプログラムが走ってるけど Pen4 2.6C で0.8秒ぐらい．ま，こんなもんか．

#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
    cout << hex;
    unsigned int digits[16];
    for(int i = 0; i < 16; i++){
        digits[i] = i;
    }
    unsigned int x = 0;
    unsigned int y = 0;
    unsigned int d0 = digits[0];
    for(int i0 = 0; i0 < 16; i0++){
        digits[0] = digits[i0];
        digits[i0] = d0;
        x = digits[0];
        unsigned int d1 = digits[1];
        for(int j0 = 1; j0 < 16; j0++){
            digits[1] = digits[j0];
            digits[j0] = d1;
            y = digits[1];
            if(y >= x) {            // omit symmetric pattern
                digits[j0] = digits[1];
                continue;
            }
            unsigned int z1 = (x * y) & 0xf;
            int k1 = 2;
            for(; k1 < 16; k1++) if (digits[k1]==z1) break;
            if(k1 >= 16) {
                digits[j0] = digits[1];
                continue;
            }
            digits[k1] = digits[2];
            digits[2] = z1;
            unsigned int d3 = digits[3];
            for(int i1 = 3; i1 < 16; i1++){
                digits[3] = digits[i1];
                digits[i1] = d3;
                x = (digits[3]<<4) | (x&0xf);
                unsigned int d4 = digits[4];
                for(int j1 = 4; j1 < 16; j1++){
                    digits[4] = digits[j1];
                    digits[j1] = d4;
                    y = (digits[4]<<4) | (y&0xf);
                    unsigned int z2 = ((x * y)>>4) & 0xf;
                    int k2 = 5;
                    for(; k2 < 16; k2++) if (digits[k2]==z2) break;
                    if(k2 >= 16) {
                        digits[j1] = digits[4];
                        continue;
                    }
                    digits[k2] = digits[5];
                    digits[5] = z2;
                    unsigned int d6 = digits[6];
                    for(int i2 = 6; i2 < 16; i2++){
                        digits[6] = digits[i2];
                        digits[i2] = d6;
                        x = (digits[6]<<8) | (x&0xff);
                        unsigned int d7 = digits[7];
                        for(int j2 = 7; j2 < 16; j2++){
                            digits[7] = digits[j2];
                            digits[j2] = d7;
                            y = (digits[7]<<8) | (y&0xff);
                            unsigned int z3 = ((x * y)>>8)&0xf;
                            int k3 = 8;
                            for(; k3 < 16; k3++) if (digits[k3]==z3) break;
                            if(k3 >= 16) {
                                digits[j2] = digits[7];
                                continue;
                            }
                            digits[k3] = digits[8];
                            digits[8] = z3;
                            unsigned int d9 = digits[9];
                            for(int i3 = 9; i3 < 16; i3++){
                                digits[9] = digits[i3];
                                digits[i3] = d9;
                                x = (digits[9]<<12) | (x&0xfff);
                                unsigned int d10 = digits[10];
                                for(int j3 = 10; j3 < 16; j3++){
                                    digits[10] = digits[j3];
                                    digits[j3] = d10;
                                    y = (digits[10]<<12) | (y&0xfff);
                                    unsigned int z4 = ((x * y) >>12)&0xfffff;
                                    unsigned int ds[5];
                                    for(int i = 0; i < 5; i++){
                                        ds[i] = digits[i+11];
                                    }
                                    int i = 0;
                                    for(; i < 5; i++){
                                        int k4 = i;
                                        unsigned int z5 = z4&0xf;
                                        z4>>=4;
                                        for(; k4 < 5; k4++) if (ds[k4]==z5) break;
                                        if(k4 >= 5) break;
                                        ds[k4] = ds[i];
                                    }
                                    if(i >= 5 && ds[4]!=0){
                                        cout << x << " * " << y << " = " << x*y << endl;
                                        cout << y << " * " << x << " = " << x*y << endl;
                                    }
                                    digits[j3] = digits[10];
                                }
                                digits[10] = d10;
                                digits[i3] = digits[9];
                            }
                            x &=0xfff;
                            digits[9] = d9;
                            digits[8] = digits[k3];
                            digits[k3] = z3;
                            digits[j2] = digits[7];
                        }
                        digits[7] = d7;
                        digits[i2] = digits[6];
                    }
                    x &=0xff;
                    digits[6] = d6;
                    digits[5] = digits[k2];
                    digits[k2] = z2;
                    digits[j1] = digits[4];
                }
                digits[4] = d4;
                digits[i1] = digits[3];
            }
            x &=0xf;
            digits[3] = d3;
            digits[2] = digits[k1];
            digits[k1] = z1;
            digits[j0] = digits[1];
        }
        digits[1] = d1;
        digits[i0] = digits[0];
    }
}

なげぇなぁ．

画像回転でデフォルト画像としてパターン画像を生成していたのだが，友人に美しいパターンの生成方法を教わった．生成式は x 座標と y 座標の XOR で．これをやると見事なパターンがでる．

モノクロならこんな感じで．（パターンを描いたスクリーンショット）

    for(int i = 0 ; i < ImageHeight ; i++) {
      for(int j = 0 ; j < ImageWidth ; j++) {
        *p++ = (i^j)&0xff;
      }
    }

色つけるならこんな感じで．

    for(int i = 0 ; i < ImageHeight ; i++) {
      int r = (i * 0xFF) / ImageHeight;
      for(int j = 0 ; j < ImageWidth ; j++) {
        int y = (i^j)&0xff;
        int ry = r * y/0xff;
        int gy = (( j * 0xFF ) / ImageWidth) * y/0xff;
        int by = (~r&0xff) * y/0xff;
        *p++ = 0xff000000 | ry << 16 | gy << 8| by;
      }
    }

画像回転のメインルーチンで double による計算をしていたのだが，この部分を固定小数演算に置き換えたら劇的に速くなった．キャスト要らずだし，やっぱ整数演算は速いなぁと思っていたら，コンパイル時に -msse2 をつければ double でも SSE2 命令で速くなった．同様に，double を float に置き換えても -msse (SSE) で速くなる．いまさらながらだが，これらの拡張命令のすごさを体験してみたり．ちなみに fps はノートPC で30に達した．描画しなければ 90 だけど．

ということで，記念にソースと実行ファイル一式を置いておこう．馬鹿みたいに重たいスクリーンセーバーもどきか？