埃及乘法代码实现

什么是埃及乘法

埃及乘法的思路是：反复地将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;
}

 

以上是阅读《数学与泛型编程：高效编程的奥秘》所做的笔记，书上还提有更优化的方法，但本人觉得有点多余，这样就很简洁高效了。