欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

埃及乘法代码实现

程序员文章站 2022-05-16 11:34:27
什么是埃及乘法 埃及乘法的思路是:反复地将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 √ ......

什么是埃及乘法

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

 

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