エジプト乗法とは

この記事は「Alexander A. Stepanov, Daniel E. Rose . その数式、プログラムできますか？ . 翔泳社 . 2015」を参考に作成しました。

概要

エジプト乗法（Egyptian multiplication）は、古代エジプト人の間で用いられていた乗算の最適化アルゴリズムであり、現代ではロシア農民のアルゴリズム（Russian Peasant Algorithm）としても知られています。

本題

乗法を砕けた言い方で定義すると次のようになります。
「何かをそれ自身に複数回足す」
以下では$\#_+(n)$でnにある数字を掛けたときの加算の回数を表すとします。

愚直な実装

int mul_naive(int n, int a){
    if(n==1) return a;
    return mul(n-1, a) + a;
}

加算回数

$$\#_+(n) = n$$

例

$$\begin{equation*} \begin{split} \mathrm{mul_naive}(3,5) &= \mathrm{mul_naive}(2,5) + 5 \\ &= (\mathrm{mul_naive}(1,5) + 5) + 5 \\ &= 5+5+5 \\ &= 15 \end{split} \end{equation*}$$

エジプト乗法

bool odd(int n) { return n & 0x1; }
int half(int n) { return n >> 1; }
int mul(int n, int a){
    if(n==1) return a;
    if(odd(n)) return mul(half(n), a+a)+a;
    else return mul(half(n), a+a)
}

加算回数

$$\#_+(n) = \lfloor \log n \rfloor + (\nu(n)-1)$$

ただし、$\nu(n)$はポップアップカウントと呼ばれ、2進数表記における1の数を表します。

例

$$\begin{equation*} \begin{split} \mathrm{mul}(6,2) &= \mathrm{mul}(3,2+2) \\ &= \mathrm{mul}(3,4) \\ &= \mathrm{mul}(1,4+4)+4 \\ &= \mathrm{mul}(1,8)+4 \\ &= 8+4 \\ &= 12 \\ \end{split} \end{equation*}$$

加算回数の計算の補足

再帰のたびに値が半分にされるため、$\lfloor \log n \rfloor$回関数が呼び出されます。
odd(n)がtrue、すなわち最下位のビットが1の時は加算回数が1つ増えますが、n=1のときはreturnされるのでその分は含めません。
よって、$\lfloor \log n \rfloor + (\nu(n)-1)$回となります。

（補足）加法連鎖

実は、エジプト乗法よりも最適なアルゴリズムが存在します。
例えば、15を掛ける場合、エジプト乗法を用いると足す回数は6回になります。

$$\#_+(15) = \lfloor \log 5 \rfloor + (\nu(5)-1) = 3+4$$

これを5回にする方法があります。

int mul_15(int a){
    int b = (a+a)+a;  // b == 3*a
    int c = b+b;      // c == 6*a
    return (c+c)+b;   // 12*a + 3*a
}

こうした連続する加算を加法連鎖と呼びます。
しかし大抵の目的の場合にはエジプト乗法をで十分です。

参考文献

Alexander A. Stepanov, Daniel E. Rose . その数式、プログラムできますか？ . 翔泳社 . 2015