Debian Codegraph @

third-party/boost-math/include/boost/math/tools/luroth_expansion.hpp

raw
1 // (C) Copyright Nick Thompson 2020.
2 // Use, modification and distribution are subject to the
3 // Boost Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 #ifndef BOOST_MATH_TOOLS_LUROTH_EXPANSION_HPP
7 #define BOOST_MATH_TOOLS_LUROTH_EXPANSION_HPP
8
9 #include <vector>
10 #include <ostream>
11 #include <iomanip>
12 #include <cmath>
13 #include <limits>
14 #include <cstdint>
15 #include <stdexcept>
16
17 #include <boost/math/tools/is_standalone.hpp>
18 #ifndef BOOST_MATH_STANDALONE
19 #include <boost/config.hpp>
20 #ifdef BOOST_MATH_NO_CXX17_IF_CONSTEXPR
21 #error "The header <boost/math/norms.hpp> can only be used in C++17 and later."
22 #endif
23 #endif
24
25 namespace boost::math::tools {
26
27 template<typename Real, typename Z = int64_t>
28 class luroth_expansion {
29 public:
30 luroth_expansion(Real x) : x_{x}
31 {
32 using std::floor;
33 using std::abs;
34 using std::sqrt;
35 using std::isfinite;
36 if (!isfinite(x))
37 {
38 throw std::domain_error("Cannot convert non-finites into a Luroth representation.");
39 }
40 d_.reserve(50);
41 Real dn1 = floor(x);
42 d_.push_back(static_cast<Z>(dn1));
43 if (dn1 == x)
44 {
45 d_.shrink_to_fit();
46 return;
47 }
48 // This attempts to follow the notation of:
49 // "Khinchine's constant for Luroth Representation", by Sophia Kalpazidou.
50 x = x - dn1;
51 Real computed = dn1;
52 Real prod = 1;
53 // Let the error bound grow by 1 ULP/iteration.
54 // I haven't done the error analysis to show that this is an expected rate of error growth,
55 // but if you don't do this, you can easily get into an infinite loop.
56 Real i = 1;
57 Real scale = std::numeric_limits<Real>::epsilon()*abs(x_)/2;
58 while (abs(x_ - computed) > (i++)*scale)
59 {
60 Real recip = 1/x;
61 Real dn = floor(recip);
62 // x = n + 1/k => lur(x) = ((n; k - 1))
63 // Note that this is a bit different than Kalpazidou (examine the half-open interval of definition carefully).
64 // One way to examine this definition is better for rationals (it never happens for irrationals)
65 // is to consider i + 1/3. If you follow Kalpazidou, then you get ((i, 3, 0)); a zero digit!
66 // That's bad since it destroys uniqueness and also breaks the computation of the geometric mean.
67 if (recip == dn) {
68 d_.push_back(static_cast<Z>(dn - 1));
69 break;
70 }
71 d_.push_back(static_cast<Z>(dn));
72 Real tmp = 1/(dn+1);
73 computed += prod*tmp;
74 prod *= tmp/dn;
75 x = dn*(dn+1)*(x - tmp);
76 }
77
78 for (size_t i = 1; i < d_.size(); ++i)
79 {
80 // Sanity check:
81 if (d_[i] <= 0)
82 {
83 throw std::domain_error("Found a digit <= 0; this is an error.");
84 }
85 }
86 d_.shrink_to_fit();
87 }
88
89
90 const std::vector<Z>& digits() const {
91 return d_;
92 }
93
94 // Under the assumption of 'randomness', this mean converges to 2.2001610580.
95 // See Finch, Mathematical Constants, section 1.8.1.
96 Real digit_geometric_mean() const {
97 if (d_.size() == 1) {
98 return std::numeric_limits<Real>::quiet_NaN();
99 }
100 using std::log;
101 using std::exp;
102 Real g = 0;
103 for (size_t i = 1; i < d_.size(); ++i) {
104 g += log(static_cast<Real>(d_[i]));
105 }
106 return exp(g/(d_.size() - 1));
107 }
108
109 template<typename T, typename Z2>
110 friend std::ostream& operator<<(std::ostream& out, luroth_expansion<T, Z2>& scf);
111
112 private:
113 const Real x_;
114 std::vector<Z> d_;
115 };
116
117
118 template<typename Real, typename Z2>
119 std::ostream& operator<<(std::ostream& out, luroth_expansion<Real, Z2>& luroth)
120 {
121 constexpr const int p = std::numeric_limits<Real>::max_digits10;
122 if constexpr (p == 2147483647)
123 {
124 out << std::setprecision(luroth.x_.backend().precision());
125 }
126 else
127 {
128 out << std::setprecision(p);
129 }
130
131 out << "((" << luroth.d_.front();
132 if (luroth.d_.size() > 1)
133 {
134 out << "; ";
135 for (size_t i = 1; i < luroth.d_.size() -1; ++i)
136 {
137 out << luroth.d_[i] << ", ";
138 }
139 out << luroth.d_.back();
140 }
141 out << "))";
142 return out;
143 }
144
145
146 }
147 #endif