C/C++ 库函数和运算符是最优的吗？

Question

因此，在分而治之的课程中，我们被教导：

Karatsuba 乘法
快速求幂

现在，给定 2 个正整数 a 和 b operator::* 比 karatsuba(a,b) 快或者 pow(a,b) 比

快

int fast_expo(int Base, int exp)
{
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return Base
    }
    if (exp % 2 == 0) {
        return fast_expo(Base, exp / 2) * fast_expo(Base, exp / 2);
    }
    else {
        return base * fast_expo(Base, exp / 2) * fast_expo(Base, exp / 2);
    }
}

我问这个是因为我想知道他们是否只是为了教学目的，或者他们已经在 C/C++ 语言

中实现了基础

Answer 1

检查操作速度的一个好方法是测量它。如果您运行通过十亿次左右的计算，看看执行需要多少时间，您就有答案了。

有一点要注意。我导致相信 % 相当昂贵。有一种更快的方法来检查某些东西是否可以被 2 整除：

check_div_two(int number)
{
    return ((number>>1) & 0x01);
}

这样你就完成了位移并与掩码进行了比较。我认为这是一个更便宜的操作。

Answer 2

Karatsuba 乘法是一种用于大整数的特殊技术。它无法与内置的 C++ * 运算符相比，后者将 int 和 double.

等基本类型的操作数相乘

要利用 Karatsuba，您必须使用至少由大约 8 个单词组成的多精度整数。（512 位，如果这些是 64 位字）。根据 .

的公认答案，Karatsuba 变得有利的收支平衡点在 8 到 24 个机器字之间的某个位置

使用一对 double 类型的浮点操作数的 pow 函数与使用 [=11] 类型的操作数的 fast_expo 无法比较=].它们是具有不同要求的不同功能。用pow，可以计算出5的立方根：pow(5, 1/3.0)。如果那是你想要计算的，那么 fast_expo 无论多快都没有用。

无法保证您的编译器或 C 库的 pow 绝对是您的机器对两个双精度浮点数取幂的最快方法。

浮点优化声明可能很棘手，因为 "same" 函数的多个实现经常不会给出完全相同的结果直到最后一位。您可能可以编写一个快速的 my_pow ，其精度仅为五位十进制数字，并且在您的应用程序中，该近似值可能绰绰有余。你打败了图书馆吗？几乎不;您的快速函数不符合将其作为库中 pow 的替代品的要求。

Answer 3

operator::* 和其他标准运算符通常映射到硬件提供的原语。如果不存在这样的原语（例如 IA32 上的 64 位 long long），编译器会以性能损失来模拟它们（gcc 在 libgcc 中这样做）。

std::pow 相同。它是标准库的一部分，并不强制以某种方式实施。 GNU libc 将 pow(a,b) 实现为 exp(log(a) * b)。 exp and log 非常长，并且在考虑 IEEE754 浮点数的情况下编写以获得最佳性能。

关于您的建议：

小数的 Karatsuba 乘法不值得。处理器提供的乘法机器指令已经针对使用中的标准数据类型的速度和功耗进行了优化。数字越大，寄存器容量的 10-20 倍，it starts to pay off:

In the GNU MP Bignum Library, there used to be a default KARATSUBA_THRESHOLD as high as 32 for non-modular multiplication (that is, Karatsuba was used when n>=32w with typically w=32); the optimal threshold for modular exponentiation tending to be significantly higher. On modern CPUs, Karatsuba in software tends to be non-beneficial for things like ECDSA over P-256 (n=256, w=32 or w=64), but conceivably useful for much wider modulus as used in RSA.

这里有一个list with the multiplication algorithms，GNU MP的用途和他们各自的门槛。

快速取幂不适用于非整数幂，因此它与 pow 没有可比性。

Answer 4

内置类型的 * 运算符几乎肯定会作为单个 CPU 乘法指令实现。所以最终这是一个硬件问题，而不是语言问题。在没有直接硬件支持的情况下，可能会生成更长的代码序列，可能是函数调用。

可以肯定地说，芯片制造商（英特尔、AMD 等）花费大量精力使算术运算尽可能高效。

C/C++ 库函数和运算符是最优的吗？

Are C/C++ library functions and operators the most optimal ones?

c++

divide-and-conquer