#include <mathutil.h>

Static Public Member Functions
template<typename IntegralType>
static IntegralType	CeilOfRatio (IntegralType numerator, IntegralType denominator)

template<typename IntegralType>
static IntegralType	FloorOfRatio (IntegralType numerator, IntegralType denominator)

static unsigned int	GCD (unsigned int x, unsigned int y)
	Returns the greatest common divisor of two unsigned integers x and y.

static unsigned int	LeastCommonMultiple (unsigned int a, unsigned int b)

template<typename T>
static T	Abs (const T x)

template<typename T>
static T	Square (const T x)
	Returns the square of x.

static int64_t	GCD64 (int64_t x, int64_t y)

template<typename T>
static T	IPow (T base, int exp)

template<class IntOut, class FloatIn>
static IntOut	Round (FloatIn x)

template<typename IntType>
static IntType	RoundUpTo (IntType input_value, IntType rounding_value)

template<class IntOut, class FloatIn>
static IntOut	SafeCast (FloatIn x)

template<class IntOut, class FloatIn>
static IntOut	SafeRound (FloatIn x)

static int64_t	FastInt64Round (double x)

static double	Stirling (double n)

static double	LogCombinations (int n, int k)

template<typename T>
static bool	AlmostEquals (const T x, const T y)

Detailed Description

Definition at line 30 of file mathutil.h.

Member Function Documentation

◆ Abs()

template<typename T>

static T operations_research::MathUtil::Abs ( const T x )

inlinestatic

Absolute value of x. Works correctly for unsigned types and for special floating point values.

Note: 0.0 and -0.0 are not differentiated by Abs (Abs(0.0) is -0.0), which should be OK: see the comment for Max above.

Definition at line 96 of file mathutil.h.

◆ AlmostEquals()

template<typename T>

static bool operations_research::MathUtil::AlmostEquals	(	const T	x,
		const T	y )

inlinestatic

Tests whether two values are close enough to each other to be considered equal. This function is intended to be used mainly as a replacement for equality tests of floating point values in CHECK()s, and as a replacement for equality comparison against golden files. It is the same as == for integer types. The purpose of AlmostEquals() is to avoid false positive error reports in unit tests and regression tests due to minute differences in floating point arithmetic (for example, due to a different compiler).

We cannot use simple equality to compare floating point values because floating point expressions often accumulate inaccuracies, and new compilers may introduce further variations in the values.

Two values x and y are considered "almost equals" if: (a) Both values are very close to zero: x and y are in the range [-standard_error, standard_error] Normal calculations producing these values are likely to be dealing with meaningless residual values. -or- (b) The difference between the values is small: abs(x - y) <= standard_error -or- (c) The values are finite and the relative difference between them is small: abs (x - y) <= standard_error * max(abs(x), abs(y)) -or- (d) The values are both positive infinity or both negative infinity.

Cases (b) and (c) are the same as MathUtils::NearByFractionOrMargin(x, y).

standard_error is the corresponding MathLimits<T>::kStdError constant. It is equivalent to 5 bits of mantissa error. See util/math/mathlimits.cc.

Caveat: AlmostEquals() is not appropriate for checking long sequences of operations where errors may cascade (like extended sums or matrix computations), or where significant cancellation may occur (e.g., the expression (x+y)-x, where x is much larger than y). Both cases may produce errors in excess of standard_error. In any case, you should not test the results of calculations which have not been vetted for possible cancellation errors and the like.

Definition at line 326 of file mathutil.h.

◆ CeilOfRatio()

template<typename IntegralType>

static IntegralType operations_research::MathUtil::CeilOfRatio	(	IntegralType	numerator,
		IntegralType	denominator )

inlinestatic

CeilOfRatio<IntegralType> FloorOfRatio<IntegralType> Returns the ceil (resp. floor) of the ratio of two integers.

IntegralType: any integral type, whether signed or not. numerator: any integer: positive, negative, or zero. denominator: a non-zero integer, positive or negative.

Definition at line 40 of file mathutil.h.

◆ FastInt64Round()

static int64_t operations_research::MathUtil::FastInt64Round ( double x )

inlinestatic

FastInt64Round Fast routines for converting floating-point numbers to integers.

These routines are approximately 6 times faster than the default implementation of Round<int> on Intel processors (12 times faster on the Pentium 3). They are also more than 5 times faster than simply casting a "double" to an "int" using static_cast<int>. This is because casts are defined to truncate towards zero, which on Intel processors requires changing the rounding mode and flushing the floating-point pipeline (unless programs are compiled specifically for the Pentium 4, which has a new instruction to avoid this).

Numbers that are halfway between two integers may be rounded up or down. This is because the conversion is done using the default rounding mode, which rounds towards the closest even number in case of ties. So for example, FastIntRound(0.5) == 0, but FastIntRound(1.5) == 2. These functions should only be used with applications that don't care about which way such half-integers are rounded.

There are template specializations of Round() which call these functions (for "int" and "int64" only), but it's safer to call them directly.

Definition at line 272 of file mathutil.h.

◆ FloorOfRatio()

template<typename IntegralType>

static IntegralType operations_research::MathUtil::FloorOfRatio	(	IntegralType	numerator,
		IntegralType	denominator )

inlinestatic

Definition at line 54 of file mathutil.h.

◆ GCD()

static unsigned int operations_research::MathUtil::GCD	(	unsigned int	x,
		unsigned int	y )

inlinestatic

Returns the greatest common divisor of two unsigned integers x and y.

Definition at line 69 of file mathutil.h.

◆ GCD64()

static int64_t operations_research::MathUtil::GCD64	(	int64_t	x,
		int64_t	y )

inlinestatic

Euclid's Algorithm. Returns: the greatest common divisor of two unsigned integers x and y.

Definition at line 108 of file mathutil.h.

◆ IPow()

template<typename T>

static T operations_research::MathUtil::IPow	(	T	base,
		int	exp )

inlinestatic

Definition at line 120 of file mathutil.h.

◆ LeastCommonMultiple()

static unsigned int operations_research::MathUtil::LeastCommonMultiple	(	unsigned int	a,
		unsigned int	b )

inlinestatic

Returns the least common multiple of two unsigned integers. Returns zero if either is zero.

Definition at line 80 of file mathutil.h.

◆ LogCombinations()

double operations_research::MathUtil::LogCombinations	(	int	n,
		int	k )

static

Returns the log of the binomial coefficient C(n, k), known in the vernacular as "N choose K". Why log? Because the integer number for non-trivial N and K would overflow.

Note: if k > 15, this uses Stirling's approximation of log(n!). The relative error is about 1/(1260*k^5) (which is 7.6e-10 when k=16).

use symmetry to pick the shorter calculation

If we have more than 30 logarithms to calculate, we'll use Stirling's approximation for log(n!).

Definition at line 33 of file mathutil.cc.

◆ Round()

template<class IntOut, class FloatIn>

static IntOut operations_research::MathUtil::Round ( FloatIn x )

inlinestatic

We don't use sgn(x) below because there is no need to distinguish the (x == 0) case. Also note that there are specialized faster versions of this function for Intel, ARM and PPC processors at the bottom of this file.

This case is special, because for largest floating point number below 0.5, the addition of 0.5 yields 1 and this would lead to incorrect result.

Definition at line 125 of file mathutil.h.

◆ RoundUpTo()

template<typename IntType>

static IntType operations_research::MathUtil::RoundUpTo	(	IntType	input_value,
		IntType	rounding_value )

inlinestatic

Returns the minimum integer value which is a multiple of rounding_value, and greater than or equal to input_value. The input_value must be greater than or equal to zero, and the rounding_value must be greater than zero.

Definition at line 144 of file mathutil.h.

◆ SafeCast()

template<class IntOut, class FloatIn>

static IntOut operations_research::MathUtil::SafeCast ( FloatIn x )

inlinestatic

Convert a floating-point number to an integer. For all inputs x where static_cast<IntOut>(x) is legal according to the C++ standard, the result is identical to that cast (i.e. the result is x with its fractional part truncated whenever that is representable as IntOut).

static_cast would cause undefined behavior for the following cases, which have well-defined behavior for this function:

If x is NaN, the result is zero.
If the truncated form of x is above the representable range of IntOut, the result is std::numeric_limits<IntOut>::max().
If the truncated form of x is below the representable range of IntOut, the result is std::numeric_limits<IntOut>::lowest().

Note: cases #2 and #3 cover infinities as well as finite numbers.

The range of FloatIn must include the range of IntOut, otherwise the results are undefined.

Special case NaN, for which the logic below doesn't work.

Negative values all clip to zero for unsigned results.

Handle infinities.

Set exp such that x == f * 2^exp for some f with f in [0.5, 1.0), unless x is zero in which case exp == 0. Note that this implies that the magnitude of x is strictly less than 2^exp.

Let N be the number of non-sign bits in the representation of IntOut. If the magnitude of x is strictly less than 2^N, the truncated version of x is representable as IntOut. The only representable integer for which this is not the case is kMin for signed types (i.e. -2^N), but that is covered by the fall-through below.

Handle numbers with magnitude >= 2^N.

Definition at line 175 of file mathutil.h.

◆ SafeRound()

template<class IntOut, class FloatIn>

static IntOut operations_research::MathUtil::SafeRound ( FloatIn x )

inlinestatic

SafeRound These functions round a floating-point number to an integer. Results are identical to Round, except in cases where the argument is NaN, or when the rounded value would overflow the return type. In those cases, Round has undefined behavior. SafeRound returns 0 when the argument is NaN, and returns the closest possible integer value otherwise (i.e. std::numeric_limits<IntOut>::max() for large positive values, and std::numeric_limits<IntOut>::lowest() for large negative values). The range of FloatIn must include the range of IntOut, otherwise the results are undefined.

Definition at line 234 of file mathutil.h.

◆ Square()

template<typename T>

static T operations_research::MathUtil::Square ( const T x )

inlinestatic

Returns the square of x.

Definition at line 102 of file mathutil.h.

◆ Stirling()

double operations_research::MathUtil::Stirling ( double n )

static

Returns Stirling's Approximation for log(n!) which has an error of at worst 1/(1260*n^5).

The formula is extracted from the following page http://en.wikipedia.org/w/index.php?title=Stirling%27s_approximation

Definition at line 26 of file mathutil.cc.

The documentation for this class was generated from the following files:

ortools/base/mathutil.h
ortools/base/mathutil.cc

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ Abs()

◆ AlmostEquals()

◆ CeilOfRatio()

◆ FastInt64Round()

◆ FloorOfRatio()

◆ GCD()

◆ GCD64()

◆ IPow()

◆ LeastCommonMultiple()

◆ LogCombinations()

◆ Round()

◆ RoundUpTo()

◆ SafeCast()

◆ SafeRound()

◆ Square()

◆ Stirling()