[an error occurred while processing this directive]

整数除算の高速化

一般的にコンピュータの除算は、他の演算に比べて非常に遅いです。 その割りに、量子化、正規化、透視変換など、多くの場所で使われ、 高速化が望まれることも少なくありません。

除数(割る数)が毎回変わるような場合は、通常の除算を避けることはできませんが、 同じ値で繰り返し除算を行う場合は、工夫することで高速化ができます。

まず、基本的なテクニックとして、

というものがあります。

浮動小数の除算は精度が厳密である必要が無い場合が多く、単純に逆数を乗算すればいい場合が多いのですが、 整数の除算では、誤差が許されない場合が少なくありません。 基本的には、浮動小数の場合の場合と同様、逆数(固定小数)の乗算と、ビットシフトで実現しますが、 そのままでは誤差により通常の整数の除算と違う値になる場合があります。

そこで、計算結果が整数の除算結果と完全に一致する方法を説明します。

コーディング

扱う値の範囲が 0 〜 2n-1 、除数となる定数を D とします。計算用の逆数を R として以下の式で求めます。

R = (2m - 1) / D

ただし、m=2n

これで準備ができました。被除数を X として、実際の除算である、Q = X / D を次の乗算に置き換えます。

Q = (R * X + 2n) >> m

ただし、m=2n

実際のコードの例を以下に示します。

32bit除算のプログラム例

typedef unsigned __int64 QWORD;

QWORD GetReciprocalDivisor32(DWORD dwDivisor)
{
    QWORD qwReciprocalDivisor = 0xffffffffffffffff;
    return qwReciprocalDivisor / dwDivisor;
}

DWORD DivideFixed32(DWORD dwDividend, QWORD *pReciprocalDivisor)
{
    __asm{
        mov     esi, pReciprocalDivisor
        mov     eax, [esi]
        mul     dwDividend
        lea     ebx, [edx+1]
        mov     eax, [esi+4]
        mul     dwDividend
        add     eax, ebx
        adc     edx, 0
        mov     eax, edx
   }
}

void main(void)
{
    DWORD dwQ, dwD, dwX;
    QWORD qwRD = GetReciprocalDivisor32(dwD);

    dwQ = DivideFixed32(dwX, &qwRD); // dwQ = dwX / dwD;
}

16bitの範囲の除算なら、さらに簡略化できます

DWORD GetReciprocalDivisor16(DWORD dwDivisor)
{
    DWORD dwReciprocalDivisor = 0xffffffff;
    return dwReciprocalDivisor / dwDivisor;
}

DWORD DivideFixed16(DWORD dwDividend, DWORD dwReciprocalDivisor)
{
    __asm{
        mov     eax, dwReciprocalDivisor
        mul     dwDividend
        add     eax, 010000h
        adc     edx, 0
        mov     eax, edx
   }
}

32bitの除算をするのに、逆数も32bitだけの値しか使わず、場合分けにより高速化を実現している方法は こちらを参照してください。 固定小数の位置をずらす事で処理を見事に32bitに納めています。

単発で使う場合は、上記サイトの方法の方がいい場合があるのですが、 実際にはこういった除算はマルチメディア関連処理で使われ、 MMXやSSE命令と組み合わせて処理することも多いと思います。 場合分けによる分岐処理が敬遠されることも少なくなく、 その場合は、ここで説明した方法が有効ではないでしょうか。