比 * 更快的乘法

Question

我正在尝试找到一种比常规乘法更快的方法。我在 vscode 中运行代码，据我所知，我没有启用优化。我也尝试过gcc -O0 _.c -o _但仍然得到相同的结果。我还在 M0 Assembly 中编写了相同的代码，但常规乘法又是最快的。我是否遗漏了什么，也许是时间计算，或者常规乘法真的是最快的方法？

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

Answer 1

显然你的 karasuba 算法在这里很差，因为它涉及多个浮点对数和 pow 函数。其中每一个最多都与整数乘法一样快，因此这显然不是一种改进。

您的函数中的位移方法multiply过去在早期 CPU（例如 Intel 8086）上速度更快，其中单个 16 位 x 16 位乘法将花费大约 150 个时钟周期。但现代 CPU 已经进行了很多优化，因此乘法使用的周期要少得多。详细信息会因 CPU 类型和所使用的确切汇编指令而异，但对于非常短的整数（例如 8 或 16 位），位移方法最终可能会更快，但显然不适用于 64 位，因为循环开销只会增加开销。