Integer Powers Unraveled

Logarithms and powers (exponents) are occasionally useful in Bitcoin work, especially base (radix) 2. But C++ log functions are all floating point. There is not much call for floating point calculation in Bitcoin, and using the wrong data types causes code bloat due to type casting, and compiler warnings otherwise. It can also result in logic errors due to unexpected rounding behavior. Floating point operations may also be more CPU intensive than those necessary for integer operations. So we cleaned up some code by implementing a proper suite of integer exponentiation functions.

Natural logarithms are inherently floating point (base e) and logarithms of negative numbers are non-continuous functions, so implementation of these is a non-objective.

Objectives

• Provide power and log, for all integer types.
• Provide simplified base 2 variants of power and log.
  • log2(n) identical in behavior to log(2, n).
  • power2(n) identical in behavior to power(2, n).
• Provide both ceilinged and floored logarithm variants.
• Allow result type specification with appropriate defaults.
• Maintain overflow behavior of native operators.
• Return a common sentinel for undefined operations.
• Avoid unnecessary computation.

Power

Integer powers are implemented as repeated multiplication of the base by itself.

Base 2 power is repeated multiplication by 2, so the left shift operator (<<) may be used as a performance optimization. While the compiler may optimize for multiplication by 2 at run time, compiling for it explicitly precludes at least one condition and branch in the object code.

All integer power parameters are defined with the exception of power(0, 0). Apart from an overflow, 0 is the valid result only for any power of 0. So 0 is used as the invalid parameter sentinel for consistency with the logarithm functions. As with all native operators, overflow guards are left to the caller. The implementation may not cause an overflow that is not inherent in the parameterization.

The result type is the value type, as the value is multiplied by itself.

Log

Integer logarithms are implemented as repeated division of the value by the base. Native C++ division is truncated. However logarithms allow only positive value and base. Truncation of a positive quotient is floored, so only floored and ceilinged functions are required to support the three common rounding methods.

Base 2 logarithm is repeated division by 2, so the right shift operator (>>) may be used as a performance optimization. While the compiler may optimize for division by 2 at run time, compiling for it explicitly precludes at least one condition and branch in the object code.

The logarithm of a base less than 2 or a value less than 1 is undefined. Apart from an overflow, there is no valid 0 result. So 0 is used as the invalid parameter sentinel. As with all native operators, overflow guards are left to the caller. The implementation may not cause an overflow that is not inherent in the parameterization.

Iteration counting implies that the the result type is a non-negative arbitrary integer.

Implementation

These templates determine the odd-ness, sign, and absolute value of a signed or unsigned integer type.

#include <type_traits>

template <typename Integer, if_integer<Integer> = true>
constexpr bool is_odd(Integer value) noexcept
{
    return (value % 2) != 0;
}

template <typename Integer, if_signed_integer<Integer> = true>
constexpr bool is_negative(Integer value) noexcept
{
    return value < 0;
}

template <typename Integer, if_unsigned_integer<Integer> = true>
constexpr bool is_negative(Integer value) noexcept
{
    return false;
}

template <typename Integer,
    typename Absolute = std::make_unsigned<Integer>::type,
    if_signed_integer<Integer> = true>
constexpr Absolute absolute(Integer value) noexcept
{
    return is_negative(value) ? -value : value;
}

template <typename Integer,
    typename Absolute = Integer,
    if_unsigned_integer<Integer> = true>
constexpr Absolute absolute(Integer value) noexcept
{
    return value;
}

These templates implement the power functions.

#include <cstddef>

// Returns 0 for undefined (0, 0).
template <typename Value = size_t, typename Base, typename Exponent,
    if_integer<Value> = true, if_integer<Base> = true, if_integer<Exponent> = true>
inline Value power(Base base, Exponent exponent) noexcept
{
    if (base == 0)
        return 0;

    if (exponent == 0)
        return 1;

    if (is_negative(exponent))
        return absolute(base) > 1 ? 0 :
            (is_odd(exponent) && is_negative(base) ? -1 : 1);

    Value value = base;
    while (--exponent > 0) { value *= base; }
    return value;
}

template <typename Value = size_t, typename Exponent,
    if_integer<Value> = true, if_integer<Exponent> = true>
inline Value power2(Exponent exponent) noexcept
{
    if (exponent == 0)
        return 1;

    if (is_negative(exponent))
        return 0;

    Value value = 2;
    while (--exponent > 0) { value <<= 1; };
    return value;
}

These templates implement the logarithm functions.

#include <cstddef>

// Returns 0 for undefined (base < 2 or value < 1).
template <typename Exponent = size_t, typename Base, typename Value,
    if_integer<Exponent> = true, if_integer<Base> = true, if_integer<Value> = true>
inline Exponent ceilinged_log(Base base, Value value) noexcept
{
    if (base < 2 || value < 1)
        return 0;

    Exponent exponent = 0;
    while (value > 0) { ++exponent; value /= base; }
    return exponent;
}
    
// Returns 0 for undefined (value < 1).
template <typename Exponent = size_t, typename Value,
    if_integer<Exponent> = true, if_integer<Value> = true>
inline Exponent ceilinged_log2(Value value) noexcept
{
    if (is_negative(value))
        return 0;

    // C++ 20 (std::bit_width).
    using exponent = std::make_unsigned<Exponent>::type;
    const auto from = static_cast<exponent>(value);
    return static_cast<Exponent>(std::bit_width(from));
}

// Returns 0 for undefined (base < 2 or value < 1).
template <typename Exponent = size_t, typename Base, typename Value,
    if_integer<Exponent> = true, if_integer<Base> = true, if_integer<Value> = true>
inline Exponent floored_log(Base base, Value value) noexcept
{
    if (base < 2 || value < 1)
        return 0;

    Exponent exponent = 0;
    while (((value /= base)) > 0) { ++exponent; }
    return exponent;
}

// Returns 0 for undefined (value < 1).
template <typename Exponent = size_t, typename Value,
    if_integer<Exponent> = true, if_integer<Value> = true>
inline Exponent floored_log2(Value value) noexcept
{
    if (value < 1)
        return 0;

    // C++ 20 (std::bit_width).
    using exponent = std::make_unsigned<Exponent>::type;
    const auto from = static_cast<exponent>(value);
    return static_cast<Exponent>(std::bit_width(from) + 1);
}

Optimization

The use of std::signbit is avoided as it casts to double, though otherwise would be sufficient to replace the is_negative templates.

The inline keyword advises the compiler that inlining of the functions is preferred. This removes call stack overhead, assuming the compiler respects the request. Generally we prefer to let the compiler make these decisions, preserving code readability.

A compiler may warn (incorrectly) of division by zero "possibility" in a logarithm base const 0 test case, given that it is inlining (unreachable) division by literal 0. Removal of the inline keyword can prevent this if desired, but the warning is beneficial for production (vs. test) code. A better alternative may be to use a non-const, zero-valued base variable in the logarithm test cases.

The constexpr keyword ensures that functions can be evaluated at compile time. In C++14 the inlined functions above can also be changed to constexpr. This also allows the functions to be integrated into template type constraints and static_assert expressions.

The following section of power, and the corresponding but reduced section of power2, implement three short-circuits that also serve as necessary guards for the while loops.

    if (base == 0)
        return 0;

    if (exponent == 0)
        return 1;

    if (is_negative(exponent))
        return absolute(base) > 1 ? 0 :
            (is_odd(exponent) && is_negative(base) ? -1 : 1);

The base == 0 guard takes advantage of the fact that 0 to any power is 0, while also serving up the sentinel value for the power(0, 0) undefined condition. The exponent == 0 guard takes advantage of the fact that any value to the power of 0 is 1. The is_negative(exponent) guard takes advantage of the fact that any value to a negative power is between -1 and +1 (inclusive). Given integer operations, this is limited to { -1, 0, +1 }.

In each of the logarithm functions, there is a base < 2 (as applicable) and value < 1 condition. These are not optimizations, as they only determine parameter validity, but they do also serve as necessary guards for the while loops.

Both power2(n) and floored_log2(n) could simply call power(2, n) and floored_log(2, n) respectively. The implementations are nearly identical, with the exception of shift left or shift right vs. multiply by 2 or divide by 2. However there are optimizations in removing both unnecessary guards and the presumed run-time condition and branch to a shifted optimization.

Despite the relative verbosity of the templates the result should be as optimal as manually inlining the minimal necessary operations. A few runs through an NDEBUG build in a debugger confirm this.

Template Type Constraints

Without the template overloads there would be warnings on unsigned type power operands, as they all invoke value < 0, which is always false (tautological). It is trivial to replace all of these calls with value < 1 calls, as in each case 0 has been excluded. However, this materially impacts readability and there is no performance benefit. In fact, the inlined templates compile away for unsigned types whereas a < 1condition might not, so there is a potential performance advantage. For functions or operand combinations that are not referenced, the corresponding templates are not even compiled. The use of std::abs avoided as it is limited to signed types.

Template specialization could be further employed to reduce a couple calls when parameters are unsigned. However there is little to no actual performance optimization and the denormalization didn't seem like a worthwhile compromise.

The templates can be factored into header (.hpp) and implementation (.ipp) files, just be sure to remove the default template parameter values in the implementation.

See Type Constraints Unraveled for an explanation of the template type constraints used above.

Mixing Unsigned and Signed Operands

As the power result is always non-negative, the value type is defaulted to size_t. Ideally for powers it would default to Base, which may be unsigned and/or non-integral. However this would complicate providing a simple overridable default, as Value would have to follow Base in the template parameter list. As size_t is generally the largest integral type this is a reasonable default for all integral parameters, and can be overridden with a single template parameter as desired. The logarithm result defaults to size_t as it is a count, not based on any parameter.

Test Vectors

Exponents and logarithms are inverse functions, so these relations must hold for all defined { b, n }, excepting overflows.

• floored_log(b, power(b, n)) == n.
• ceilinged_log(b, power(b, n)) == n.

Conclusion

• Behavior satisfies the inverse relation for all sign combinations.
• Result type may be specified and defaults rationally.
• Behavior is consistent with native operators.
• The functions cannot cause overflows.
• There can be no "tautological compare" warnings from unsigned parameters.
• The functions return a common sentinel for undefined operations.
• Stack calls may be fully removed by inlining.
• All functions can be constexpr in C++14.
• The is_negative and absolute calls compile away for unsigned operators.
• The is_odd, is_negative, and absolute calls compile away for unsigned and constexpr parameters.
• All conditions compile away when the above render them tautological.
• All that remains is necessary.