math/doc/internals/simple_continued_fraction.qbk at c4c4592d07d297ba804451a9b6082518e3153260 · boostorg/math · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
[/
  Copyright Nick Thompson, 2020
  Copyright Matt Borland, 2023
  Distributed under the Boost Software License, Version 1.0.
  (See accompanying file LICENSE_1_0.txt or copy at
  http://www.boost.org/LICENSE_1_0.txt).
]

[section:simple_continued_fraction Simple Continued Fractions]

    #include <boost/math/tools/simple_continued_fraction.hpp>
    namespace boost::math::tools {

    template<typename Real, typename Z = int64_t>
    class simple_continued_fraction {
    public:
        simple_continued_fraction(Real x);

        Real khinchin_geometric_mean() const;

        Real khinchin_harmonic_mean() const;

        const std::vector<Z>& partial_denominators() const;

        inline std::vector<Z>&& get_data() noexcept;

        template<typename T, typename Z2>
        friend std::ostream& operator<<(std::ostream& out, simple_continued_fraction<T, Z2>& scf);
    };

    template<typename Real, typename Z = int64_t>
    inline std::vector<Z> simple_continued_fraction_coefficients(Real x);

    }


The `simple_continued_fraction` class provided by Boost affords the ability to convert a floating point number into a simple continued fraction.
In addition, we can answer a few questions about the number in question using this representation.

Here's a minimal working example:

    using boost::math::constants::pi;
    using boost::math::tools::simple_continued_fraction;
    auto cfrac = simple_continued_fraction(pi<long double>());
    std::cout << "π ≈ " << cfrac << "\n";
    // Prints:
    // π ≈ [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2]

The class computes partial denominators while simultaneously computing convergents with the modified Lentz's algorithm.
Once a convergent is within a few ulps of the input value, the computation stops.

Note that every floating point number is a rational number, and this exact rational can be exactly converted to a finite continued fraction.
This is perfectly sensible behavior, but we do not do it here.
This is because when examining known values like π, it creates a large number of incorrect partial denominators, even if every bit of the binary representation is correct.

It may be the case the a few incorrect partial convergents is harmless, but we compute continued fractions because we would like to do something with them.
One sensible thing to do it to ask whether the number is in some sense "random"; a question that can be partially answered by computing the Khinchin geometric mean

If you only require the coefficients of the simple continued fraction for example in the calculation of [@https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations best rational approximations] there is a free function for that.

An example of this calculation follows:

    using boost::math::tools::simple_continued_fraction_coefficients;

    auto coefs1 = simple_continued_fraction_coefficients(static_cast<Real>(3.14155L)); // [3; 7, 15, 2, 7, 1, 4, 2]
    auto coefs2 = simple_continued_fraction_coefficients(static_cast<Real>(3.14165L)); // [3; 7, 16, 1, 3, 4, 2, 4]

    const std::size_t max_size = (std::min)(coefs1.size(), coefs2.size());
    std::vector<std::int64_t> coefs;
    coefs.reserve(max_size);

    for (std::size_t i = 0; i < max_size; ++i)
    {
        const auto c1 = coefs1[i];
        const auto c2 = coefs2[i];
        if (c1 == c2)
        {
            coefs.emplace_back(c1);
            continue;
        }

        coefs.emplace_back((std::min)(c1, c2) + 1);
        break;
    }

    // Result is [3; 7, 16]

[$../equations/khinchin_geometric.svg]

and Khinchin harmonic mean

[$../equations/khinchin_harmonic.svg]

If these approach Khinchin's constant /K/[sub 0] and /K/[sub -1] as the number of partial denominators goes to infinity, then our number is "uninteresting" with respect to the characterization.
These violations are washed out if too many incorrect partial denominators are included in the expansion.

Note: The convergence of these means to the Khinchin limit is exceedingly slow; we've used 30,000 decimal digits of π and only found two digits of agreement with /K/[sub 0].
However, clear violations of are obvious, such as the continued fraction expansion of √2, whose Khinchin geometric mean is precisely 2.

[endsect]