最近、整数演算だけで色々する話があったので、過去に作成したものを見直してみた。

・平方根
これは、ファミコン時代から使っていた方法をＣ＋＋（Ｃ）で表現したもので。
※アルゴリズムは、コンピューターが出現する以前から知られていた数学的手法を元に
しているようで、初期のデジタルコンピューターが出現する、数十年前に既に知られて
いた方法のようである。

過去には、色々なマイコン用（６５０２、６８０９、６８０００、Ｚ８０）アセンブラ
で書いた記憶がある。
Ｃなどの高級言語では、キャーリーの扱いが無い為、シフトや、ビット操作を行う場合
無駄が多い。
アセンブラで書けば、より一層の高速化ができるけど、互換性を考えて、Ｃで実装して
ある。
ハードウェアーにも実装しやすく、割り算よりリソースを使わないと思われる。
※整数計算なので、「余り」がある。

ゲームにおいて平方根は、必ず必要な「道具」で、シューティングゲームの誘導ミサイ
ル、正規化、ほぼありとあらゆる場面で使うと思われる。

template <typename T>
struct sqrt_t {
    typedef T value_type;

    T   val;    ///< 答え
    T   mod;	///< 余り

    sqrt_t(T v = 0, T m = 0) : val(v), mod(m) { }
};

static sqrt_t<uint16_t> sqrt16(uint16_t in)
{
    uint32_t a = in;
    uint32_t b = 0x4000;
    for(int i = 0; i < 8; ++i) {
        if(a >= b) {
            a -= b;
            b = ((b + b) & 0xfffe0000) + 0x10000 + (b & 0xffff);
        } else {
            b = ((b + b) & 0xfffe0000) + (b & 0xffff);
        }
        a <<= 2;
    }
    sqrt_t<uint16_t> ans(b >> 16, a >> 16);
    return ans;
}

・３２ビット版

static sqrt_t<uint32_t> sqrt32(uint32_t al)
{
    uint32_t ah, bh, bl;

    ah = bh = 0;
    bl = 0x40000000;
    for(int i = 0; i < 16; ++i) {
        if(al >= bl) {
            if(ah >= bh) {
                ah -= bh;
                al -= bl;
                bh += bh + 1;
            } else {
                bh += bh;
            }
        } else {
            if(ah >= (bh + 1)) {
                ah -= bh + 1;
                al -= bl;
                bh += bh + 1;
            } else {
                bh += bh;
            }
        }
        ah <<= 2;
        ah += al >> 30;
        al <<= 2;
    }

    sqrt_t ans(bh, ah);
    return ans;
}

intmath.hpp