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

Question

So, at the divide & conquer course we were taught:

1. Karatsuba multiplication
2. Fast exponentiation

Now, given 2 positive integers a and b is operator::* faster than a karatsuba(a,b) or is pow(a,b) faster than

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

I ask this because I wonder if they have just a teaching purpose or they are already base implemented in the C/C++ language

Answer 1

Karatsuba multiplication is a special technique for large integers. It is not comparable to the built in C++ * operator which multiplies together operands of basic type like int and double.

To take advantage of Karatsuba, you have to be using multi-precision integers made up of at least around 8 words. (512 bits, if these are 64 bit words). The break-even point at which Karatsuba becomes advantageous is at somewhere between 8 and 24 machine words, according to the accepted answer to this question.

The pow function which works with a pair of floating-point operands of type double, is not comparable to your fast_expo, which works with operands of type int. They are different functions with different requirements. With pow, you can calculate the cube root of 5: pow(5, 1/3.0). If that's what you would like to calculate, then fast_expo is of no use, no matter how fast.

There is no guarantee that your compiler or C library's pow is absolutely the fastest way for your machine to exponentiate two double-precision floating-point numbers.

Optimization claims in floating-point can be tricky, because it often happens that multiple implementations of the "same" function do not give exactly the same results down to the last bit. You can probably write a fast my_pow that is only good to five decimal digits of precision, and in your application, that approximation might be more than adequate. Have you beat the library? Hardly; your fast function doesn't meet the requirements that would qualify it as a replacement for the pow in the library.