aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
rational_tpl.h
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2026 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2026 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40
41#pragma once
42
43
49
50// To help IDE Parsers
51#include <agrum/agrum.h>
52
55
56namespace gum {
57
58 template < GUM_Numeric GUM_SCALAR >
59 void Rational< GUM_SCALAR >::farey(int64_t& numerator,
60 int64_t& denominator,
61 const GUM_SCALAR& number,
62 const int64_t& den_max,
63 const GUM_SCALAR& zero) {
64 bool isNegative = (number < 0) ? true : false;
65 GUM_SCALAR pnumber = (isNegative) ? -number : number;
66
67 if (std::abs(pnumber - GUM_SCALAR(1.)) < zero) {
68 numerator = (isNegative) ? -1 : 1;
69 denominator = 1;
70 return;
71 } else if (pnumber < zero) {
72 numerator = 0;
73 denominator = 1;
74 return;
75 }
76
77 int64_t a(0), b(1), c(1), d(1);
78 double mediant(0.0F);
79
80 while (b <= den_max && d <= den_max) {
81 // guard against int64_t overflow before computing a+c and b+d
82 if (c > std::numeric_limits< int64_t >::max() - a
83 || d > std::numeric_limits< int64_t >::max() - b)
84 break;
85 mediant = (GUM_SCALAR)(a + c) / (GUM_SCALAR)(b + d);
86
87 if (std::fabs(pnumber - mediant) < zero) {
88 if (b + d <= den_max) {
89 numerator = (isNegative) ? -(a + c) : (a + c);
90 denominator = b + d;
91 return;
92 } else if (d > b) {
93 numerator = (isNegative) ? -c : c;
94 denominator = d;
95 return;
96 } else {
97 numerator = (isNegative) ? -a : a;
98 denominator = b;
99 return;
100 }
101 } else if (pnumber > mediant) {
102 a = a + c;
103 b = b + d;
104 } else {
105 c = a + c;
106 d = b + d;
107 }
108 }
109
110 if (b > den_max) {
111 numerator = (isNegative) ? -c : c;
112 denominator = d;
113 return;
114 } else {
115 numerator = (isNegative) ? -a : a;
116 denominator = b;
117 return;
118 }
119 }
120
121 template < GUM_Numeric GUM_SCALAR >
123 int64_t& denominator,
124 const GUM_SCALAR& number,
125 const double& zero) {
126 const GUM_SCALAR pnumber = (number > 0) ? number : -number;
127
129 GUM_SCALAR rnumber = pnumber;
130
132 std::vector< uint64_t > p({0, 1});
133 std::vector< uint64_t > q({1, 0});
134
136 std::vector< uint64_t > a;
137
138 uint64_t p_tmp, q_tmp;
139
140 uint64_t n;
141 double delta, delta_tmp;
142
144 const double epsilon = config().epsilonStandard();
145
151 while (true) {
152 a.push_back(std::lrint(std::floor(rnumber)));
153 p.push_back(a.back() * p.back() + p[p.size() - 2]);
154 q.push_back(a.back() * q.back() + q[q.size() - 2]);
155
156 delta = std::fabs(pnumber - (GUM_SCALAR)p.back() / q.back());
157
158 if (delta < zero) {
159 numerator = (int64_t)p.back();
160 if (number < 0) numerator = -numerator;
161 denominator = q.back();
162 break;
163 }
164
165 if (std::abs(rnumber - a.back()) < epsilon) break;
166
167 rnumber = GUM_SCALAR(1.) / (rnumber - a.back());
168 }
169
170 if (a.size() < 2) return;
171
175 Idx i = Idx(p.size() - 2);
179 // Test n = a[i-1]/2 ( when a[i-1] is even )
180 n = a[i - 1] / 2;
181 p_tmp = n * p[i] + p[i - 1];
182 q_tmp = n * q[i] + q[i - 1];
183
184 delta = std::fabs(pnumber - ((double)p[i]) / q[i]);
185 delta_tmp = std::fabs(pnumber - ((double)p_tmp) / q_tmp);
186
187 if (delta < zero) {
188 numerator = (int64_t)p[i];
189 if (number < 0) numerator = -numerator;
190 denominator = q[i];
191 return;
192 }
193
194 if (delta_tmp < zero) {
195 numerator = (int64_t)p_tmp;
196 if (number < 0) numerator = -numerator;
197 denominator = q_tmp;
198 return;
199 }
200
201 // next semi-convergents until next convergent from smaller denominator to
202 // bigger
203 // denominator
204 for (n = (a[i - 1] + 2) / 2; n < a[i - 1]; ++n) {
205 p_tmp = n * p[i] + p[i - 1];
206 q_tmp = n * q[i] + q[i - 1];
207
208 delta_tmp = std::fabs(pnumber - ((double)p_tmp) / q_tmp);
209
210 if (delta_tmp < zero) {
211 numerator = (int64_t)p_tmp;
212 if (number < 0) numerator = -numerator;
213 denominator = q_tmp;
214 return;
215 }
216 }
217
219 }
220
221 template < GUM_Numeric GUM_SCALAR >
223 int64_t& denominator,
224 const GUM_SCALAR& number,
225 const int64_t& den_max) {
226 const GUM_SCALAR pnumber = (number > 0) ? number : -number;
227
228 const uint64_t denMax = (uint64_t)den_max;
229
231 GUM_SCALAR rnumber = pnumber;
232
234 std::vector< uint64_t > p({0, 1});
235 std::vector< uint64_t > q({1, 0});
236
238 std::vector< uint64_t > a;
239
240 uint64_t p_tmp, q_tmp;
241
242 uint64_t n;
243 double delta, delta_tmp;
244
246 const double epsilon = config().epsilonStandard();
247
249 while (true) {
250 a.push_back(std::lrint(std::floor(rnumber)));
251
252 p_tmp = a.back() * p.back() + p[p.size() - 2];
253 q_tmp = a.back() * q.back() + q[q.size() - 2];
254
255 if (q_tmp > denMax || p_tmp > denMax) break;
256
257 p.push_back(p_tmp);
258 q.push_back(q_tmp);
259
260 if (std::fabs(rnumber - a.back()) < epsilon) break;
261
262 rnumber = GUM_SCALAR(1.) / (rnumber - a.back());
263 }
264
265 if (a.size() < 2 || q.back() == denMax || p.back() == denMax) {
266 numerator = p.back();
267 if (number < 0) numerator = -numerator;
268 denominator = q.back();
269 return;
270 }
271
275 Idx i = Idx(p.size() - 1);
276
280 for (n = a[i - 1] - 1; n >= (a[i - 1] + 2) / 2; --n) {
281 p_tmp = n * p[i] + p[i - 1];
282 q_tmp = n * q[i] + q[i - 1];
283
284 if (q_tmp > denMax || p_tmp > denMax) continue;
285
286 numerator = (int64_t)p_tmp;
287 if (number < 0) numerator = -numerator;
288 denominator = q_tmp;
289 return;
290 } // end of for
291
292 // Test n = a[i-1]/2
293 n = a[i - 1] / 2;
294 p_tmp = n * p[i] + p[i - 1];
295 q_tmp = n * q[i] + q[i - 1];
296
297 delta_tmp = std::fabs(pnumber - ((double)p_tmp) / q_tmp);
298 delta = std::fabs(pnumber - ((double)p[i]) / q[i]);
299
300 if (delta_tmp < delta && q_tmp <= denMax && p_tmp <= denMax) {
301 numerator = (int64_t)p_tmp;
302 if (number < 0) numerator = -numerator;
303 denominator = q_tmp;
304 } else {
305 numerator = (int64_t)p[i];
306 if (number < 0) numerator = -numerator;
307
308 denominator = q[i];
309 }
310
312 }
313
314} // namespace gum
double epsilonStandard() const noexcept
static void continuedFracBest(int64_t &numerator, int64_t &denominator, const GUM_SCALAR &number, const int64_t &den_max=1000000)
Find the best rational approximation.
static void farey(int64_t &numerator, int64_t &denominator, const GUM_SCALAR &number, const int64_t &den_max=1000000L, const GUM_SCALAR &zero=static_cast< GUM_SCALAR >(config().epsilonStandard()))
Find the rational close enough to a given ( decimal ) number in [-1,1] and whose denominator is not h...
static void continuedFracFirst(int64_t &numerator, int64_t &denominator, const GUM_SCALAR &number, const double &zero=config().epsilonStandard())
Find the first best rational approximation.
Typed, documented, sectioned configuration singleton read from an .ini content.
Size Idx
Type for indexes.
Definition types.h:79
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
Configuration & config()
A short name for Configuration::instance() : gum::config().epsilonStandard(). It is not inline so tha...
Class template used to approximate decimal numbers by rationals.