OR-Tools  8.1
mathutil.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_BASE_MATHUTIL_H_
15 #define OR_TOOLS_BASE_MATHUTIL_H_
16 
17 #include <math.h>
18 
19 #include <algorithm>
20 #include <vector>
21 
22 #include "absl/base/casts.h"
25 #include "ortools/base/logging.h"
26 #include "ortools/base/macros.h"
27 
28 namespace operations_research {
29 class MathUtil {
30  public:
31  // CeilOfRatio<IntegralType>
32  // FloorOfRatio<IntegralType>
33  // Returns the ceil (resp. floor) of the ratio of two integers.
34  //
35  // IntegralType: any integral type, whether signed or not.
36  // numerator: any integer: positive, negative, or zero.
37  // denominator: a non-zero integer, positive or negative.
38  template <typename IntegralType>
39  static IntegralType CeilOfRatio(IntegralType numerator,
40  IntegralType denominator) {
41  DCHECK_NE(0, denominator);
42  const IntegralType rounded_toward_zero = numerator / denominator;
43  const IntegralType intermediate_product = rounded_toward_zero * denominator;
44  const bool needs_adjustment =
45  (rounded_toward_zero >= 0) &&
46  ((denominator > 0 && numerator > intermediate_product) ||
47  (denominator < 0 && numerator < intermediate_product));
48  const IntegralType adjustment = static_cast<IntegralType>(needs_adjustment);
49  const IntegralType ceil_of_ratio = rounded_toward_zero + adjustment;
50  return ceil_of_ratio;
51  }
52  template <typename IntegralType>
53  static IntegralType FloorOfRatio(IntegralType numerator,
54  IntegralType denominator) {
55  DCHECK_NE(0, denominator);
56  const IntegralType rounded_toward_zero = numerator / denominator;
57  const IntegralType intermediate_product = rounded_toward_zero * denominator;
58  const bool needs_adjustment =
59  (rounded_toward_zero <= 0) &&
60  ((denominator > 0 && numerator < intermediate_product) ||
61  (denominator < 0 && numerator > intermediate_product));
62  const IntegralType adjustment = static_cast<IntegralType>(needs_adjustment);
63  const IntegralType floor_of_ratio = rounded_toward_zero - adjustment;
64  return floor_of_ratio;
65  }
66 
67  // Returns the greatest common divisor of two unsigned integers x and y.
68  static unsigned int GCD(unsigned int x, unsigned int y) {
69  while (y != 0) {
70  unsigned int r = x % y;
71  x = y;
72  y = r;
73  }
74  return x;
75  }
76 
77  // Returns the least common multiple of two unsigned integers. Returns zero
78  // if either is zero.
79  static unsigned int LeastCommonMultiple(unsigned int a, unsigned int b) {
80  if (a > b) {
81  return (a / MathUtil::GCD(a, b)) * b;
82  } else if (a < b) {
83  return (b / MathUtil::GCD(b, a)) * a;
84  } else {
85  return a;
86  }
87  }
88 
89  // Absolute value of x.
90  // Works correctly for unsigned types and
91  // for special floating point values.
92  // Note: 0.0 and -0.0 are not differentiated by Abs (Abs(0.0) is -0.0),
93  // which should be OK: see the comment for Max above.
94  template <typename T>
95  static T Abs(const T x) {
96  return x > 0 ? x : -x;
97  }
98 
99  // Returns the square of x.
100  template <typename T>
101  static T Square(const T x) {
102  return x * x;
103  }
104 
105  // Euclid's Algorithm.
106  // Returns: the greatest common divisor of two unsigned integers x and y.
107  static int64 GCD64(int64 x, int64 y) {
108  DCHECK_GE(x, 0);
109  DCHECK_GE(y, 0);
110  while (y != 0) {
111  int64 r = x % y;
112  x = y;
113  y = r;
114  }
115  return x;
116  }
117 
118  template <typename T>
119  static T IPow(T base, int exp) {
120  return pow(base, exp);
121  }
122 
123  template <class IntOut, class FloatIn>
124  static IntOut Round(FloatIn x) {
125  // We don't use sgn(x) below because there is no need to distinguish the
126  // (x == 0) case. Also note that there are specialized faster versions
127  // of this function for Intel, ARM and PPC processors at the bottom
128  // of this file.
129  if (x > -0.5 && x < 0.5) {
130  // This case is special, because for largest floating point number
131  // below 0.5, the addition of 0.5 yields 1 and this would lead
132  // to incorrect result.
133  return static_cast<IntOut>(0);
134  }
135  return static_cast<IntOut>(x < 0 ? (x - 0.5) : (x + 0.5));
136  }
137 
138  static int64 FastInt64Round(double x) { return Round<int64>(x); }
139 };
140 } // namespace operations_research
141 
142 #endif // OR_TOOLS_BASE_MATHUTIL_H_
integral_types.h
logging.h
operations_research::MathUtil::LeastCommonMultiple
static unsigned int LeastCommonMultiple(unsigned int a, unsigned int b)
Definition: mathutil.h:79
operations_research::MathUtil::IPow
static T IPow(T base, int exp)
Definition: mathutil.h:119
macros.h
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::MathUtil::GCD64
static int64 GCD64(int64 x, int64 y)
Definition: mathutil.h:107
int64
int64_t int64
Definition: integral_types.h:34
operations_research::MathUtil::FastInt64Round
static int64 FastInt64Round(double x)
Definition: mathutil.h:138
DCHECK_NE
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
operations_research::MathUtil::Square
static T Square(const T x)
Definition: mathutil.h:101
a
int64 a
Definition: constraint_solver/table.cc:42
operations_research::MathUtil::FloorOfRatio
static IntegralType FloorOfRatio(IntegralType numerator, IntegralType denominator)
Definition: mathutil.h:53
operations_research::MathUtil
Definition: mathutil.h:29
basictypes.h
operations_research::MathUtil::Round
static IntOut Round(FloatIn x)
Definition: mathutil.h:124
operations_research::MathUtil::GCD
static unsigned int GCD(unsigned int x, unsigned int y)
Definition: mathutil.h:68
DCHECK_GE
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
operations_research::MathUtil::CeilOfRatio
static IntegralType CeilOfRatio(IntegralType numerator, IntegralType denominator)
Definition: mathutil.h:39
b
int64 b
Definition: constraint_solver/table.cc:43
operations_research::MathUtil::Abs
static T Abs(const T x)
Definition: mathutil.h:95