埃及乘法代碼實現

什麼是埃及乘法

埃及乘法的思路是：反覆地將n減半，並將a加倍，同時求出a的各種倍數，這些倍數與a的比值都是2的整數次冪。n的值為奇數部分的a之和即為所求值

舉個慄子：41 x 59

1        41        59          √

2        20        118

4        10        236

8         5         472        √

16       2         944

32       1         1888      √

41 x 59 = (1 x 59) + (8 x 59) + (32 x 49)

遞歸實現

 1 bool odd(int n) { return n & 0x01; }    // n是否為奇數
 2 int half(int n) { return n >> 1; }    // n / 2
 3 int doubling(int n) { return n << 1; }    // n * 2
 4 int multiply1(int n, int a)
 5 {
 6     if (n == 1) return a;
 7     int ret = multiply1(half(n), double(a))
 8     if (odd(n)) ret += a;
 9     return ret;
10 }

 迴圈實現

bool odd(int n) { return n & 0x01; }    // n是否為奇數
int half(int n) { return n >> 1; }    // n / 2
int doubling(int n) { return n << 1; }    // n * 2
int multiply1(int n, int a)
{
    int ret = 0;
    while (true)
    {
        if (odd(n))
        {
            ret += a;
            if(n==1) break;
        }
        a = doubling(a);
        n = half(n);
    }
    return ret;
}

以上是閱讀《數學與泛型編程：高效編程的奧秘》所做的筆記，書上還提有更優化的方法，但本人覺得有點多餘，這樣就很簡潔高效了。