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

Question

因此，在分而治之的类(class)中，我们被教导:

1. Karatsuba 乘法
2. 快速取幂

现在，给定 2 个正整数 a 和 b operator::* 比 a 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

Karatsuba 乘法是大整数的一种特殊技术。它无法与内置的 C++ * 运算符相比，后者将 int 和 double 等基本类型的操作数相乘。

要利用 Karatsuba，您必须使用至少由大约 8 个单词组成的多精度整数。 (512 位，如果这些是 64 位字)。根据对 this question 的公认答案，Karatsuba 变得有利的收支平衡点介于 8 到 24 个机器字之间。 .

pow 函数与一对 double 类型的浮点操作数一起工作，无法与您的 fast_expo 相提并论，它可以工作具有 int 类型的操作数。它们是具有不同要求的不同功能。使用 pow，您可以计算 5 的立方根:pow(5, 1/3.0)。如果这就是您要计算的内容，那么无论多快，fast_expo 都没有用。

无法保证您的编译器或 C 库的 pow 绝对是您的机器对两个 double float 取幂的最快方法。

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