Binary Exponentiation is not working properly when the base is a float/double

Question

I learned how to implement binary exponentiation in c++ from this site. I used the recursive algorithm:

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

In my situation, I need a to be a double value. I did this to do that:

double binpow(double a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

I do not need b to be a double, and I know that if b were a double, I would need to use a different approach to get the real value.

When I ran the code with: binpow(3.1, 3), the correct answer would be 29.79, but the binpow algorithm gave me 27.9. I also tried binpow(9.23, 3), and it gave me 747.63, while the real answer was 786.33.

Also, when i switch to the naive method:

double naive(double a, long long b) {
    
    double final = 1;
    
    for (;b > 0; b--) {
        final*=a;
    }
    
    return final;
}

I get the correct answer of 786.33

What is the issue here, and is there a way to fix this?

Answer 1

You are converting the result of binpow to a long long here:

long long res = binpow(a, b / 2);

which changes the result.

Instead, you need to do:

double res = binpow(a, b / 2);

or even better

auto res = binpow(a, b / 2);  // so res has the same type that binpow returns

which fixes the issue. Here's a demo.