我正在努力寻找一种比常规乘法更快的方法.我在vscode中运行代码,就我所看到的而言,我没有启用任何优化.我也试了gcc -O0 _.c -o _次,但还是得到了同样的结果.我也用M0汇编语言写了同样的代码,但规则乘法还是最快的.我有没有遗漏什么,可能是在时间计算方面,或者规则乘法真的是最快的方法?

#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

uint64_t karatsuba(uint64_t x, uint64_t y) {
    if (x < 10 || y < 10) {
        return x * y;
    }

    int n = max(log10(x) + 1, log10(y) + 1) / 2;

    uint64_t a = x / (uint64_t)pow(10, n);
    uint64_t b = x % (uint64_t)pow(10, n);
    uint64_t c = y / (uint64_t)pow(10, n);
    uint64_t d = y % (uint64_t)pow(10, n);

    uint64_t ac = karatsuba(a, c);
    uint64_t bd = karatsuba(b, d);
    uint64_t ad_bc = karatsuba(a + b, c + d) - ac - bd;

    return ac * (uint64_t)pow(10, 2 * n) + ad_bc * (uint64_t)pow(10, n) + bd;
}

uint64_t multiply(uint64_t x, uint64_t y) {
    uint64_t result = 0;

    while (x > 0) {
        if (x & 1) {
            result += y;
        }
        x >>= 1;
        y <<= 1;
    }

    return result;
}

int main() {
    uint64_t i = UINT64_MAX;
    uint64_t j = 10;

    clock_t t;
    clock_t m;
    clock_t l;
    int n = 9999999;

    t = clock();
    for (int k = 0; k < n; k++) {
        multiply(i, j);
    }
    t = clock() - t;
    double time_taken = ((double)t) / CLOCKS_PER_SEC;
    printf("Bit Manipulation Multiplication took %.15f seconds to execute in average\n", time_taken / n);

    m = clock();
    for (int k = 0; k < n; k++) {
        uint64_t k_result = i * j;
    }
    m = clock() - m;
    double time_taken2 = ((double)m) / CLOCKS_PER_SEC;
    printf("Regular Multiplication took %.15f seconds to execute in average\n", time_taken2 / n);

    l = clock();
    for (int k = 0; k < n; k++) {
        karatsuba(i, j);
    }
    l = clock() - l;
    double time_taken3 = ((double)l) / CLOCKS_PER_SEC;
    printf("Karatsuba Multiplication took %.15f seconds to execute in average\n", time_taken3 / n);

    printf("\nResults:\n");
    printf("Bit Manipulation Result: %llu\n", multiply(i, j));
    printf("Regular Multiplication Result: %llu\n", i * j);
    printf("Karatsuba Multiplication Result: %llu\n", karatsuba(i, j));

    return 0;
}

推荐答案

显然,您的Karatsuba算法在这里很差,因为它涉及多个浮点对数和幂函数.其中Each one的运算速度充其量和整数乘法一样快,所以这显然不是一个改进.

在早期的CPU(如Intel 8086)上,您的multiply函数中的位移位方法曾经更快,其中单个16位x 16位乘法将占用大约150个时钟周期.但现代的CPU已经进行了很多优化,所以乘法使用的周期要少得多.具体细节将因CPU类型和所使用的确切汇编指令而异,但位移位方法对于非常短的整数可能最终会更快,因此8位或16位,但通常不是64位,因为循环开销只会增加,嗯,开销.

C++相关问答推荐

Pure Win32 C(++)-除了替换控件的窗口程序之外,还有其他方法可以在输入时禁用按钮吗?

如何避免重新分配指针数组时,我们从一开始就不知道确切的大小

为什么下面的C代码会进入无限循环?

什么C代码将确定打开的套接字正在使用的网络适配器?

将指针作为参数传递给函数

带有sigLongjMP中断I/O的异常处理程序

在列表中插入Int指针(C)

我的程序在收到SIGUSR1信号以从PAUSE()继续程序时总是崩溃()

将数据移动到寄存器时出现分段故障

Kdb:仅升级指定的列

用C++从外部ELF符号读取值

我应该在递归中使用全局变量吗

合并对 struct 数组进行排序

如何使用WRITE()以指针地址的十六进制形式写入标准输出

在同一范围内对具有相同类型的变量执行的相同操作在同一C代码中花费的时间不同

C 语言中 CORDIC 对数的问题

当 n 是我们从用户那里获得的整数时,创建 n 个 struct 参数

Struct 内的数组赋值

全局变量 y0 与 mathlib 冲突,无法编译最小的 C 代码

文件指针引起的C程序分段错误