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;
67 if (std::abs(pnumber - GUM_SCALAR(1.)) < zero) {
68 numerator = (isNegative) ? -1 : 1;
71 }
else if (pnumber < zero) {
77 int64_t a(0), b(1), c(1), d(1);
80 while (b <= den_max && d <= den_max) {
82 if (c > std::numeric_limits< int64_t >::max() - a
83 || d > std::numeric_limits< int64_t >::max() - b)
85 mediant = (GUM_SCALAR)(a + c) / (GUM_SCALAR)(b + d);
87 if (std::fabs(pnumber - mediant) < zero) {
88 if (b + d <= den_max) {
89 numerator = (isNegative) ? -(a + c) : (a + c);
93 numerator = (isNegative) ? -c : c;
97 numerator = (isNegative) ? -a : a;
101 }
else if (pnumber > mediant) {
111 numerator = (isNegative) ? -c : c;
115 numerator = (isNegative) ? -a : a;
123 int64_t& denominator,
124 const GUM_SCALAR& number,
125 const double& zero) {
126 const GUM_SCALAR pnumber = (number > 0) ? number : -number;
129 GUM_SCALAR rnumber = pnumber;
132 std::vector< uint64_t > p({0, 1});
133 std::vector< uint64_t > q({1, 0});
136 std::vector< uint64_t > a;
138 uint64_t p_tmp, q_tmp;
141 double delta, delta_tmp;
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]);
156 delta = std::fabs(pnumber - (GUM_SCALAR)p.back() / q.back());
159 numerator = (int64_t)p.back();
160 if (number < 0) numerator = -numerator;
161 denominator = q.back();
165 if (std::abs(rnumber - a.back()) < epsilon)
break;
167 rnumber = GUM_SCALAR(1.) / (rnumber - a.back());
170 if (a.size() < 2)
return;
175 Idx i =
Idx(p.size() - 2);
181 p_tmp = n * p[i] + p[i - 1];
182 q_tmp = n * q[i] + q[i - 1];
184 delta = std::fabs(pnumber - ((
double)p[i]) / q[i]);
185 delta_tmp = std::fabs(pnumber - ((
double)p_tmp) / q_tmp);
188 numerator = (int64_t)p[i];
189 if (number < 0) numerator = -numerator;
194 if (delta_tmp < zero) {
195 numerator = (int64_t)p_tmp;
196 if (number < 0) numerator = -numerator;
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];
208 delta_tmp = std::fabs(pnumber - ((
double)p_tmp) / q_tmp);
210 if (delta_tmp < zero) {
211 numerator = (int64_t)p_tmp;
212 if (number < 0) numerator = -numerator;
223 int64_t& denominator,
224 const GUM_SCALAR& number,
225 const int64_t& den_max) {
226 const GUM_SCALAR pnumber = (number > 0) ? number : -number;
228 const uint64_t denMax = (uint64_t)den_max;
231 GUM_SCALAR rnumber = pnumber;
234 std::vector< uint64_t > p({0, 1});
235 std::vector< uint64_t > q({1, 0});
238 std::vector< uint64_t > a;
240 uint64_t p_tmp, q_tmp;
243 double delta, delta_tmp;
250 a.push_back(std::lrint(std::floor(rnumber)));
252 p_tmp = a.back() * p.back() + p[p.size() - 2];
253 q_tmp = a.back() * q.back() + q[q.size() - 2];
255 if (q_tmp > denMax || p_tmp > denMax)
break;
260 if (std::fabs(rnumber - a.back()) < epsilon)
break;
262 rnumber = GUM_SCALAR(1.) / (rnumber - a.back());
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();
275 Idx i =
Idx(p.size() - 1);
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];
284 if (q_tmp > denMax || p_tmp > denMax)
continue;
286 numerator = (int64_t)p_tmp;
287 if (number < 0) numerator = -numerator;
294 p_tmp = n * p[i] + p[i - 1];
295 q_tmp = n * q[i] + q[i - 1];
297 delta_tmp = std::fabs(pnumber - ((
double)p_tmp) / q_tmp);
298 delta = std::fabs(pnumber - ((
double)p[i]) / q[i]);
300 if (delta_tmp < delta && q_tmp <= denMax && p_tmp <= denMax) {
301 numerator = (int64_t)p_tmp;
302 if (number < 0) numerator = -numerator;
305 numerator = (int64_t)p[i];
306 if (number < 0) numerator = -numerator;
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.