aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
gum::Rational< GUM_SCALAR > Class Template Reference

Class template used to approximate decimal numbers by rationals. More...

#include <agrum/base/core/math/rational.h>

Static Public Member Functions

Real approximation by rational
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 higher than a given integer number.
static void continuedFracFirst (int64_t &numerator, int64_t &denominator, const GUM_SCALAR &number, const double &zero=config().epsilonStandard())
 Find the first best rational approximation.
static void continuedFracBest (int64_t &numerator, int64_t &denominator, const GUM_SCALAR &number, const int64_t &den_max=1000000)
 Find the best rational approximation.

Detailed Description

template<GUM_Numeric GUM_SCALAR>
class gum::Rational< GUM_SCALAR >

Class template used to approximate decimal numbers by rationals.

Template Parameters
GUM_SCALARThe floating type ( float, double, long double ... ) of the number.

Definition at line 81 of file rational.h.

Member Function Documentation

◆ continuedFracBest()

template<GUM_Numeric GUM_SCALAR>
void gum::Rational< GUM_SCALAR >::continuedFracBest ( int64_t & numerator,
int64_t & denominator,
const GUM_SCALAR & number,
const int64_t & den_max = 1000000 )
static

Find the best rational approximation.

Not the first, to a given ( decimal) number ( ANY number ) and whose denominator is not higher than a given integer number.

In this case, we look for semi-convergents at the right of the last admissible convergent, if any. They are better approximations, but have higher denominators.

Parameters
numeratorThe numerator of the rational.
denominatorThe denominator of the rational.
numberThe constant number we want to approximate using rationals.
den_maxThe constant highest authorized denominator. 1000000 by default.

Definition at line 222 of file rational_tpl.h.

225 {
226 const GUM_SCALAR pnumber = (number > 0) ? number : -number;
227
229
232
236
239
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
287 if (number < 0) numerator = -numerator;
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) {
302 if (number < 0) numerator = -numerator;
304 } else {
305 numerator = (int64_t)p[i];
306 if (number < 0) numerator = -numerator;
307
308 denominator = q[i];
309 }
310
312 }
Class template used to approximate decimal numbers by rationals.
Definition rational.h:81

References gum::config(), and gum::Configuration::epsilonStandard().

Here is the call graph for this function:

◆ continuedFracFirst()

template<GUM_Numeric GUM_SCALAR>
void gum::Rational< GUM_SCALAR >::continuedFracFirst ( int64_t & numerator,
int64_t & denominator,
const GUM_SCALAR & number,
const double & zero = config().epsilonStandard() )
static

Find the first best rational approximation.

end of farey func

The one with the smallest denominator such that no other rational with smaller denominator is a better approx, within precision zero to a given ( decimal ) number ( ANY number).

It gives the same answer than farey assuming zero is the same and den_max is infinite. Use this functions because you are sure to get an approx within zero of number.

We look at the semi-convergents left of the last admissible convergent, if any. They may be within the same precision and have a smaller denominator.

Parameters
numeratorThe numerator of the rational.
denominatorThe denominator of the rational.
numberThe constant number we want to approximate using rationals.
zeroThe positive value below which a number is considered zero. The key core.epsilonStandard of the configuration (1e-6) by default.

Definition at line 122 of file rational_tpl.h.

125 {
126 const GUM_SCALAR pnumber = (number > 0) ? number : -number;
127
130
134
137
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) {
196 if (number < 0) numerator = -numerator;
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) {
212 if (number < 0) numerator = -numerator;
214 return;
215 }
216 }
217
219 }

References gum::config(), and gum::Configuration::epsilonStandard().

Referenced by gum::credal::LRSWrapper< GUM_SCALAR >::_fill_().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ farey()

template<GUM_Numeric GUM_SCALAR>
void gum::Rational< GUM_SCALAR >::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()) )
static

Find the rational close enough to a given ( decimal ) number in [-1,1] and whose denominator is not higher than a given integer number.

Because of the double constraint on precision and size of the denominator, there is no guarantee on the precision of the approximation if den_max is low and zero is high. Prefer the use of continued fractions.

Parameters
numeratorThe numerator of the rational.
denominatorThe denominator of the rational.
numberThe constant number we want to approximate using rationals.
den_maxThe constant highest authorized denominator. 1000000 by default.
zeroThe positive value below which a number is considered zero. The key core.epsilonStandard of the configuration (1e-6) by default.

Definition at line 59 of file rational_tpl.h.

63 {
64 bool isNegative = (number < 0) ? true : false;
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
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 }

Referenced by gum::credal::CredalNet< GUM_SCALAR >::_H2Vlrs_().

Here is the caller graph for this function:

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