# Integer Powers Unraveled - libbitcoin/libbitcoin-system Wiki

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;

const auto log = floored_log<Exponent>(base, value);
return log + ((power<Value>(base, log) == value) ? 0 : 1);
}

// 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 (value < 1)
return 0;

const auto log = floored_log2<Exponent>(value);
return log + ((power2<Value>(log) == value) ? 0 : 1);
}

// 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;

Exponent exponent = 0;
while (((value >>= 1)) > 0) { ++exponent; };
return exponent;
}
``````

## 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 `< 1`condition 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.