OR-Tools  8.2
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"
26#include "ortools/base/macros.h"
27
28namespace operations_research {
29class 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_
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
static int64 GCD64(int64 x, int64 y)
Definition: mathutil.h:107
static IntegralType CeilOfRatio(IntegralType numerator, IntegralType denominator)
Definition: mathutil.h:39
static unsigned int GCD(unsigned int x, unsigned int y)
Definition: mathutil.h:68
static T Abs(const T x)
Definition: mathutil.h:95
static T IPow(T base, int exp)
Definition: mathutil.h:119
static IntegralType FloorOfRatio(IntegralType numerator, IntegralType denominator)
Definition: mathutil.h:53
static T Square(const T x)
Definition: mathutil.h:101
static IntOut Round(FloatIn x)
Definition: mathutil.h:124
static unsigned int LeastCommonMultiple(unsigned int a, unsigned int b)
Definition: mathutil.h:79
static int64 FastInt64Round(double x)
Definition: mathutil.h:138
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...