埃及乘法代码实现

野性酷女 2021-10-30 07:18 246阅读 0赞

### 什么是埃及乘法 ###

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

发表评论取消回复

表情：

评论列表（有 0 条评论，246人围观）

还没有评论，来说两句吧...

相关阅读

相关闲话中国人的竖式乘法和埃及人的二分乘法

世界上所有区域的文明发源地，均发展了数学，并且将数学发展到了异常发达的地步，无论是埃及，美索不达米亚，印度，还是较晚的中国。并且这些文明发展数学的目的，均是为了解决实际问题的。

╰+哭是因爲堅強的太久メ/ 2023年07月07日 12:33/ 0 赞/ 4 阅读

相关 java不用乘法运算符实现乘法计算

思路：通过左移操作完整代码如下： import java.util.Scanner; public class Example { pub

妖狐艹你老母/ 2023年05月29日 13:15/ 0 赞/ 27 阅读

相关埃及分数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

左手的ㄟ右手/ 2022年11月15日 03:41/ 0 赞/ 191 阅读

相关 python埃及分数_JAVA 把一个分数拆分成埃及分数

public class FsMethod \{ /\\ \ 分数拆分 \ @param fz 分子 \ @param fm 分母 \/ public static

「爱情、让人受尽委屈。」/ 2022年10月31日 13:57/ 0 赞/ 244 阅读

相关埃及分数

古埃及曾经创造出灿烂的人类文明，他们的分数表示却很令人不解。古埃及喜欢把一个分数分解为类似： 1/a + 1/b 的格式。这里，a 和 b 必须是不同

旧城等待，/ 2022年08月02日 12:40/ 0 赞/ 197 阅读

相关历届试题埃及分数（穷举）

古埃及曾经创造出灿烂的人类文明，他们的分数表示却很令人不解。古埃及喜欢把一个分数分解为类似： 1/a \+ 1/b 的格式。这里，a 和 b 必须是不同的两个整数，分子必

朴灿烈づ我的快乐病毒、/ 2022年07月12日 08:48/ 0 赞/ 250 阅读

相关 CUDA编程--实现并行矩阵乘法【80行代码】

简述这里只写了方阵之间的乘法，但是本质上都是一样的。我测试过100规模的方阵之间的乘法，没有问题。代码读取文件data.txt 数据格

- 日理万妓/ 2022年04月03日 15:19/ 0 赞/ 225 阅读

相关入门OJ 1261【埃及分数】

描述　　在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 ![1710567-20190710112732103-562115858

偏执的太偏执、/ 2021年11月10日 08:24/ 0 赞/ 319 阅读

相关埃及乘法代码实现

什么是埃及乘法埃及乘法的思路是：反复地将n减半，并将a加倍，同时求出a的各种倍数，这些倍数与a的比值都是2的整数次幂。n的值为奇数部分的a之和即为所求值举个栗子：4

野性酷女/ 2021年10月30日 07:18/ 0 赞/ 247 阅读

相关 MapReduce实现矩阵乘法

简单回顾一下矩阵乘法： ![C=AB][C_AB] 矩阵乘法要求左矩阵的列数与右矩阵的行数相等，m×n的矩阵A，与n×p的矩阵B相乘，结果为m×p的矩阵C。详细内容可以查看

川长思鸟来/ 2021年09月25日 15:56/ 0 赞/ 436 阅读