割り算を使わずに割り算する

前回から間が開いてしまいましたが、やっと当初のゴール=割り算を使わずに割り算をしてみましょう。

まずは補助関数を1つ定義しましょう。

int msb(int a)
{
    int c = 0;
    while (a != 0)
    {
        a >>= 1;
        ++c;
    }
    return c;
}

この msb() は most significant bit の位置を求める関数です。 加えて前回の引き算で定義した sub() を使います。

以上を踏まえて mydiv() を見てみましょう。 この関数では商(戻り値) q = a / b と余り *r = a % b の両方が求まります。

int mydiv(int a, int b, int *r)
{
    int q = 0;
    int c = msb(a) - msb(b);
    for (; c >= 0; --c)
    {
        int d = sub(a, b << c);
        if (d >= 0)
        {
            a = d;
            q |= 1 << c;
        }
    }
    *r = a;
    return q;
}

これ今までに比べるとちょっと複雑ですが原理は簡単で、小学校の時にだれでもやった 筆算による割り算 を2進数でやっているだけなんです。

まとめ

ここまで四則演算を四則演算を使わずに行ってきました。

こうして見てくると、コンピュータの中で行われている計算方法、手順は人間のソレとまったく同じであることに気がついたと思います。唯一違っていたのは人間が使う数字は0から9の10進数なのに対し、コンピュータが使う数字は0と1だけの2進数であるということだけでしょう。

単にコンピュータは速いのです。人間がやっているのと同じ計算を人間よりも圧倒的に速くできるから便利なのです。その根本的なところが認識できると、随分とコンピュータやプログラムが違って見えてはきませんか? アルゴリズムの重要性もより際立つでしょう。

これまで見てきたとおり特に掛け算とわり算は手数が多く、そのためにかかる時間も足し算や引き算と比べ物にならないほど大きく=遅くなります。人間だって掛け算を計算するのは面倒臭いですが、割り算はもっと手間ですが、コンピュータであったとしてもそれはまったく同じです。