mysql::math Namespace Reference

Namespaces
namespace	detail

Classes
class	Kahan_sum
	Tracks the state of the Kahan summation algorithm, which produces a sum over a sequence of floating point numbers with very low numeric error, using an internal error compensation term. More...

Functions
template<typename T , std::enable_if_t< std::is_integral< T >::value &&std::is_unsigned< T >::value, bool > = true>
constexpr T	add_bounded (const T x, const T y, const T maximum)
	Return x+y, limited to the given maximum. More...
template<typename T , typename T2 , std::enable_if_t< std::is_integral< T >::value &&std::is_unsigned< T >::value &&std::is_arithmetic< T2 >::value, bool > = true>
constexpr T	multiply_bounded (const T x, const T2 y, const T maximum)
	Return x*y, limited to the given maximum. More...
template<typename T , std::enable_if_t< std::is_integral< T >::value &&std::is_unsigned< T >::value, bool > = true>
constexpr T	ceil_div (const T x, const T y)
	Return ceil(x / y), where x and y are unsigned integer types. More...
template<class Value_t >
constexpr Value_t	int_pow (Value_t base, unsigned exponent)
	Return pow(base, exponent), where the exponent is an integer. More...
template<auto base> requires std::integral<decltype(base)> && (base >= 2)
constexpr unsigned	int_log_max ()
	Return the floor of the base-base logarithm of numeric_limits<decltype(base>)>max(). More...
template<auto base, std::unsigned_integral Value_t> requires std::same_as<decltype(base), Value_t> && (base >= 2)
constexpr unsigned	int_log (Value_t value)
	Return the base-base logarithm of value. More...
template<class Value_t = double, std::input_iterator Iterator_t>
Value_t	kahan_sum (const Iterator_t &first, const std::sentinel_for< Iterator_t > auto &last, Value_t init=0)
	Compute the sum of values in the given range, with very low numeric error. More...
template<class Result_t = long double, std::input_iterator Iterator1_t, std::input_iterator Iterator2_t> requires std::is_arithmetic_v<Result_t> && std::unsigned_integral<decltype(*std::declval<Iterator1_t>())> && std::unsigned_integral<decltype(*std::declval<Iterator2_t>())>
Result_t	sequence_sum_difference (const Iterator1_t &begin1, const std::sentinel_for< Iterator1_t > auto &end1, const Iterator2_t &begin2, const std::sentinel_for< Iterator2_t > auto &end2, uint64_t init=0)
	Compute the sum of values in the first sequence, minus the sum of values in the second sequence. More...

Function Documentation

add_bounded()

template<typename T , std::enable_if_t< std::is_integral< T >::value &&std::is_unsigned< T >::value, bool > = true>

constexpr T mysql::math::add_bounded ( const T  x, const T  y, const T  maximum  )

constexpr

Return x+y, limited to the given maximum.

Note

This works even when x+y would exceed the maximum for the datatype.

Template Parameters

T	Data type. Must be an unsigned integral datatype.

Parameters

x	The first term.
y	The second term.
maximum	The maximum allowed value.

Returns

The smallest of (x + y) and (maximum), computed as if using infinite precision arithmetic.

ceil_div()

template<typename T , std::enable_if_t< std::is_integral< T >::value &&std::is_unsigned< T >::value, bool > = true>

constexpr T mysql::math::ceil_div ( const T  x, const T  y  )

constexpr

Return ceil(x / y), where x and y are unsigned integer types.

int_log()

template<auto base, std::unsigned_integral Value_t>
requires std::same_as<decltype(base), Value_t> && (base >= 2)

constexpr unsigned mysql::math::int_log ( Value_t  value )

constexpr

Return the base-base logarithm of value.

Template Parameters

base	Base of the logarithm.
Value_t	The integral data type.

Parameters

value

Value to compute the logarithm for.

Returns

int(log_base(value)), or 0 if value == 0.

Complexity: For constexpr arguments, reduces to a constant. Otherwise, logarithmic in the base logarithm of std::numeric_limits<Value_t>::max(). The number of divisions is the floor of log2(int_log_max<Value_t, base>()), and 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()

template<auto base>
requires std::integral<decltype(base)> && (base >= 2)

constexpr unsigned mysql::math::int_log_max ( )

constexpr

Return the floor of the base-base logarithm of numeric_limits<decltype(base>)>max().

Template Parameters

base	base of the logarithm

Complexity: reduces to a compile-time constant.

int_pow()

template<class Value_t >

constexpr Value_t mysql::math::int_pow ( Value_t  base, unsigned  exponent  )

constexpr

Return pow(base, exponent), where the exponent is an integer.

This does not check for overflow.

Complexity: For constexpr arguments, reduces to a compile-time constant. Otherwise, logarithmic in the exponent. The number of multiplications is equal to the 2-logarithm of the exponent, plus the number of 1-bits in the exponent.

kahan_sum()

template<class Value_t = double, std::input_iterator Iterator_t>

Value_t mysql::math::kahan_sum	(	const Iterator_t &	first,
		const std::sentinel_for< Iterator_t > auto &	last,
		Value_t	init = 0
	)

Compute the sum of values in the given range, with very low numeric error.

multiply_bounded()

template<typename T , typename T2 , std::enable_if_t< std::is_integral< T >::value &&std::is_unsigned< T >::value &&std::is_arithmetic< T2 >::value, bool > = true>

constexpr T mysql::math::multiply_bounded ( const T  x, const T2  y, const T  maximum  )

constexpr

Return x*y, limited to the given maximum.

Note

This works even when x * y would exceed the maximum for any of the data type.

Template Parameters

T	Data type for the first factor, the maximum, and the result. This must be an unsigned integral.
T2	datatype for the second factor. This can be any arithmetic type, including floating point types.

Parameters

x	The first factor.
y	The second factor.
maximum	The maximum allowed value.

Returns

The smallest of (x + y) and (maximum), computed as if using infinite precision arithmetic; or 0 if y is negative.

sequence_sum_difference()

template<class Result_t = long double, std::input_iterator Iterator1_t, std::input_iterator Iterator2_t>
requires std::is_arithmetic_v<Result_t> && std::unsigned_integral<decltype(*std::declval<Iterator1_t>())> && std::unsigned_integral<decltype(*std::declval<Iterator2_t>())>

Result_t mysql::math::sequence_sum_difference	(	const Iterator1_t &	begin1,
		const std::sentinel_for< Iterator1_t > auto &	end1,
		const Iterator2_t &	begin2,
		const std::sentinel_for< Iterator2_t > auto &	end2,
		uint64_t	init = 0
	)

Compute the sum of values in the first sequence, minus the sum of values in the second sequence.

When the return type is floating point, the result is exact if it is at most mysql::math::max_exact_int<Return_t>.

This uses an algorithm that avoids overflow in intermediate computations as long as the exact result is small, and uses a summation algorithm that minmizes floating point errors if the result is large.

Template Parameters

Result_t	Numeric type for the result.
Iterator1_t	Type of iterator to first sequence.
Iterator2_t	Type of iterator to second sequence.

Parameters

begin1	Iterator to beginning of first sequence.
end1	Sentinel of first sequence.
begin2	Iterator to beginning of second sequence.
end2	Sentinel of second sequence.
init	Initial value. Defaults to 0.

Returns

Return_t The sum of all values in the range from begin1 to end1, minus the sum of all values in the range from begin2 to end2.