比*更快的乘法实现探究：为何常规乘法仍最快？

我正在寻找比常规乘法（*）更快的实现方式。我在VSCode中运行未开启任何优化的代码，也尝试使用gcc -O0 _.c -o _命令编译，得到的结果一致。我还在M0汇编中编写了相同逻辑的代码，但常规乘法依旧是最快的。请问我是否在计时环节存在疏漏，还是常规乘法确实是当前场景下最快的乘法方式？

测试所用C语言代码 #

#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;
}

分析与结论 #

1. 常规乘法确实是当前场景下的最优选择 #

你的测试对象是64位整数乘法，现代CPU的硬件指令集直接支持64位乘法操作，这类指令通常只需要3~10个时钟周期就能完成，是硬件级别的极致优化：

• 你实现的位操作乘法本质是模拟二进制乘法的累加过程，对于UINT64_MAX这种全1的数，需要循环64次，每次还要执行移位、分支判断、加法操作，总耗时远高于硬件乘法指令。
• 你使用的Karatsuba算法完全没发挥出优势：Karatsuba是为远超CPU原生位宽的超大整数设计的，用它处理64位整数时，频繁的log10、pow浮点运算（这类操作耗时极长）、递归调用的开销，会让它的性能比常规乘法差几个数量级。

2. 计时环节存在的疏漏 #

• 无副作用代码被优化：虽然你用了-O0，但编译器仍可能对未使用计算结果的代码做优化。比如常规乘法的循环中，k_result没有被后续使用，编译器可能直接跳过整个乘法操作，导致计时结果失真。建议将每次计算的结果累加，最后输出累加值，避免被优化。
• 计时精度不足：单次乘法耗时极短，clock()的精度可能不足以准确测量，建议使用更精确的计时工具（比如Linux下的gettimeofday，ARM架构的周期计数器），或者大幅增加循环次数。
• 测试顺序影响结果：CPU的缓存、分支预测机制会影响后续测试的性能，建议打乱三个测试的执行顺序，或者多次测试取平均值。

3. 如何让非常规乘法体现优势 #

如果想测试非常规乘法的性能，需要调整测试场景：

• 测试超大整数：比如处理256位、512位甚至更长的整数，此时硬件乘法无法直接处理，Karatsuba、FFT乘法等软件实现才会体现出效率优势。
• 优化位操作乘法：针对特定场景（比如乘数是2的幂）做优化，这种情况直接用移位操作即可，不需要模拟乘法。
• 优化Karatsuba实现：改用二进制拆分替代十进制拆分，避免浮点运算的开销，同时设置合理的递归终止条件（比如当数的位宽小于CPU原生位宽时直接使用硬件乘法）。

内容的提问来源于stack exchange，提问作者4DescarTes