Library: Math

Code documentation: Math.

This is a header-only library, containing mathematical functions. Currently it has the following headers:

• bounded_arithmetic.h: multiplication and addition, capped at a max value.
• int_pow.h: Functions to compute powers and logarithms for integers efficiently:
  • int_pow(a, b) computes a to the power b. For constexpr arguments, reduces to a compile-time constant. Otherwise, logarithmic in the exponent. The exact number of multiplications is equal to the 2-logarithm of the exponent, plus the number of 1-bits in the exponent.
  • int_log<N>(a) computes the base-N logarithm of a. For constexpr arguments, reduces to a constant. Otherwise, logarithmic in the base logarithm of std::numeric_limits<Value_t>::max(). The exact number of divisions is the floor of log2(int_log_max<Value_t, base>()) and in each division, the denominator is a compile-time constant which is a power of base, so that the compiler may use denominator-specific optimizations such as shift-right instead of division operations.
  • int_log_max<T>() reduces to a compile-time constant, which is the floor of the logarithm of the maximum value representable in type T.
• summation.h: Two algorithms to compute the sums of sequences: kahan_sum uses the Kahan summation algorithm to compute the sum of floating-point numbers with very low numeric error. sequence_sum_difference computes the difference of the sums of two sequences of nonnegative integers, guaranteeing exact results when the sums are close to each other, even if each sum is huge.