Recursively calculating powers by squaring

Question

Consider the following function that implements optimised O(log n) exponentiation by squaring:

#include <cstdint> // uintmax
// log-n optimised integer power function. Computes x to the power of y
constexpr std::uintmax_t pow(std::uintmax_t x, std::uintmax_t y) {
    // base cases for efficiency and guaranteed termination
    switch (y) {
    case 0:
        return 1;
    case 1:
        return x;
    case 2:
        return x * x;
    case 3:
        return x * x * x;
    }
    // OTHERWISE:
    std::uintmax_t square_root = pow(x, y / 2);
    // otherwise, work out if y is a multiple of 2 or not
    if (y % 2 == 0) {
        return square_root * square_root;
    } else {
        return square_root * square_root * x;
    }
}

The base cases switch could be rewritten to take advantage of deliberate fallthrough between the various cases to "aggregate" the exponentiation of x from the 0th up to the 3rd power:

// log-n optimised integer power function. Computes x to the power of y
constexpr std::uintmax_t pow(std::uintmax_t x, std::uintmax_t y) {
    // base cases for efficiency and guaranteed termination
    std::uintmax_t result = 1;
    switch (y) {
    case 3:
        result *= x;
        [[fallthrough]];
    case 2:
        result *= x;
        [[fallthrough]];
    case 1:
        result *= x;
        [[fallthrough]];
    case 0:
        return result;
    }
    // OTHERWISE:
    std::uintmax_t square_root = pow(x, y / 2);
    // otherwise, work out if y is a multiple of 2 or not
    if (y % 2 == 0) {
        return square_root * square_root;
    } else {
        return square_root * square_root * x;
    }
}

Now, I am aware that the general consensus is that such use of fallthrough in a switch-case is seen as a cardinal sin. I am also aware that the function would work if base cases were provided for just the zeroth and first power (or even just for the zeroth!). The reason I provide base cases up to the third is that it feels just a bit of a waste of a function call to recur into to calculate such simple powers, although perhaps to the third power is a bit overkill..?

So my question is primarily:

• Is such use of deliberate fallthrough justifiable here, or could it be justifiable for a similarly-structured example that's a bit more elaborate than chaining multiplication but which still has the commutative chaining as a property?

Secondarily:

• What do you think about the number of base cases provided here? Is this astute use of deliberately avoiding recursive calls for such simple cases, or is it premature optimisation?

Answer 1

Firstly, I wouldn't call the function pow - that's confusingly similar to std::pow, which can be invoked with the same arguments.

In both cases, I expect the usual (iterative) binary exponentiation to be both faster and easier for readers to follow than this recursive implementation. Given that the question tags mention performance is important, I encourage you to benchmark both recursive and iterative functions.

---

Here's a simple implementation of the iterative method:

#include <concepts>

template<typename T>
constexpr T unit_value = 1;


// Return xⁿ
// If calculation overflows, behaviour may be undefined!
template<typename T>
constexpr auto ipow(const T x, std::unsigned_integral auto n)
    requires requires(T t) { t *= t; }
{
    auto result = unit_value<T>;
    for (auto y = x;  true;  y *= y) {
        if (n % 2 == 1) { result *= y; }
        if ((n /= 2) == 0) { break; }
    }
    return result;
}

The infinite loop with break is used rather than testing n > 0 in the for condition to avoid an unnecessary y *= y in the last iteration.

I provided the unit_value template so that it can be used with non-arithmetic types (complex numbers, square matrices, etc) by specialising that value with the appropriate multiplicative identity. For example:

#include <complex>
template<typename T>
constexpr std::complex<T> unit_value<std::complex<T>> = {1, 0};

(This one isn't strictly needed, since there's implicit conversion from T to complex<T>, but it demonstrates the point).

Answer 2

I would indeed not use [[fallthrough]] here, the version without is clearer in my opinion.

Instead though I would move everything inside the switch-statement:

switch (y) {
case 0:
    return 1;
case 1:
    return x;
case 2:
    return x * x;
case 3:
    return x * x * x;
default:
    return pow(x, y / 2) * pow(x, y - y / 2);
}

Also consider making it a template, possibly in combination with concepts to restrict the type of the exponent to unsigned integers:

template <typename T, std::unsigned_integral Exponent>
constexpr T pow(T x, Exponent y) {
    ...
}