boost/math
2
0
Fork 0
mirror of https://github.com/boostorg/math.git synced 2026-01-20 16:52:09 +00:00
Code Issues Projects Releases Wiki Activity
Files
develop
math/doc/html/math_toolkit/internals/simple_continued_fraction.html
jzmaddock 4c2cdc2cf6 Regenerate docs.
2024-08-06 13:18:32 +01:00

121 lines
10 KiB
HTML
Raw Permalink Blame History

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Simple Continued Fractions</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../internals.html" title="Internal tools">
<link rel="prev" href="cf.html" title="Continued Fraction Evaluation">
<link rel="next" href="centered_continued_fraction.html" title="Centered Continued Fractions">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="cf.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="centered_continued_fraction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="math_toolkit.internals.simple_continued_fraction"></a><a class="link" href="simple_continued_fraction.html" title="Simple Continued Fractions">Simple
Continued Fractions</a>
</h3></div></div></div>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">simple_continued_fraction</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">tools</span> <span class="special">{</span>
<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Real</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Z</span> <span class="special">=</span> <span class="identifier">int64_t</span><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">simple_continued_fraction</span> <span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="identifier">simple_continued_fraction</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">x</span><span class="special">);</span>
<span class="identifier">Real</span> <span class="identifier">khinchin_geometric_mean</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span>
<span class="identifier">Real</span> <span class="identifier">khinchin_harmonic_mean</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span>
<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Z_</span><span class="special">&gt;</span>
<span class="keyword">friend</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">&lt;&lt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">out</span><span class="special">,</span> <span class="identifier">simple_continued_fraction</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Z</span><span class="special">&gt;&amp;</span> <span class="identifier">scf</span><span class="special">);</span>
<span class="special">};</span>
<span class="special">}</span>
</pre>
<p>
The <code class="computeroutput"><span class="identifier">simple_continued_fraction</span></code>
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.
</p>
<p>
Here's a minimal working example:
</p>
<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">constants</span><span class="special">::</span><span class="identifier">pi</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">tools</span><span class="special">::</span><span class="identifier">simple_continued_fraction</span><span class="special">;</span>
<span class="keyword">auto</span> <span class="identifier">cfrac</span> <span class="special">=</span> <span class="identifier">simple_continued_fraction</span><span class="special">(</span><span class="identifier">pi</span><span class="special">&lt;</span><span class="keyword">long</span> <span class="keyword">double</span><span class="special">&gt;());</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"π ≈ "</span> <span class="special">&lt;&lt;</span> <span class="identifier">cfrac</span> <span class="special">&lt;&lt;</span> <span class="string">"\n"</span><span class="special">;</span>
<span class="comment">// Prints:</span>
<span class="comment">// π ≈ [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2]</span>
</pre>
<p>
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.
</p>
<p>
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.
</p>
<p>
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
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/khinchin_geometric.svg" width="173" height="22"></object></span>
</p>
<p>
and Khinchin harmonic mean
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/khinchin_harmonic.svg" width="153" height="40"></object></span>
</p>
<p>
If these approach Khinchin's constant <span class="emphasis"><em>K</em></span><sub>0</sub> and <span class="emphasis"><em>K</em></span><sub>-1</sub> 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.
</p>
<p>
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 <span class="emphasis"><em>K</em></span><sub>0</sub>. However, clear violations of are
obvious, such as the continued fraction expansion of √2, whose Khinchin
geometric mean is precisely 2.
</p>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
Walker and Xiaogang Zhang<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="cf.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="centered_continued_fraction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink