最近、整数演算だけで色々する話があったので、過去に作成したものを見直してみた。
・平方根
これは、ファミコン時代から使っていた方法をＣ＋＋（Ｃ）で表現したもので。
※アルゴリズムは、コンピューターが出現する以前から知られていた数学的手法を元に
しているようで、初期のデジタルコンピューターが出現する、数十年前に既に知られて
いた方法のようである。
過去には、色々なマイコン用（６５０２、６８０９、６８０００、Ｚ８０）アセンブラ
で書いた記憶がある。
Ｃなどの高級言語では、キャーリーの扱いが無い為、シフトや、ビット操作を行う場合
無駄が多い。
アセンブラで書けば、より一層の高速化ができるけど、互換性を考えて、Ｃで実装して
ある。
ハードウェアーにも実装しやすく、割り算よりリソースを使わないと思われる。
※整数計算なので、「余り」がある。
ゲームにおいて平方根は、必ず必要な「道具」で、シューティングゲームの誘導ミサイ
ル、正規化、ほぼありとあらゆる場面で使うと思われる。
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;
}