埃及乘法代码实现

2019-08-16 07:54:32来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

埃及乘法代码实现

什么是埃及乘法

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

 

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

 


原文链接:https://www.cnblogs.com/HuangWj/p/11248411.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++复制构造函数,类型转换构造函数,析构函数,引用,指针常量和

下一篇:C++ Primer练习题day1