libs/math/doc/html/math_toolkit/internals1/cf.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Continued Fraction Evaluation</title>
   5 <link rel="stylesheet" href="../../math.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
   7 <link rel="home" href="../../index.html" title="Math Toolkit 2.1.0">
   8 <link rel="up" href="../internals1.html" title="Utilities &amp; internals">
   9 <link rel="prev" href="series_evaluation.html" title="Series Evaluation">
  10 <link rel="next" href="rational.html" title="Polynomial and Rational Function Evaluation">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="series_evaluation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals1.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="rational.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="math_toolkit.internals1.cf"></a><a class="link" href="cf.html" title="Continued Fraction Evaluation">Continued Fraction Evaluation</a>
  28 </h3></div></div></div>
  29 <h5>
  30 <a name="math_toolkit.internals1.cf.h0"></a>
  31         <span class="phrase"><a name="math_toolkit.internals1.cf.synopsis"></a></span><a class="link" href="cf.html#math_toolkit.internals1.cf.synopsis">Synopsis</a>
  32       </h5>
  33 <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">fraction</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  34 </pre>
  35 <pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">tools</span><span class="special">{</span>
  36
  37 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">&gt;</span>
  38 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  39    <span class="identifier">continued_fraction_b</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">U</span><span class="special">&amp;</span> <span class="identifier">tolerance</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">)</span>
  40
  41 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">&gt;</span>
  42 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  43    <span class="identifier">continued_fraction_b</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">U</span><span class="special">&amp;</span> <span class="identifier">tolerance</span><span class="special">)</span>
  44
  45 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">&gt;</span>
  46 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  47    <span class="identifier">continued_fraction_a</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">U</span><span class="special">&amp;</span> <span class="identifier">tolerance</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">)</span>
  48
  49 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">&gt;</span>
  50 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  51    <span class="identifier">continued_fraction_a</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">U</span><span class="special">&amp;</span> <span class="identifier">tolerance</span><span class="special">)</span>
  52
  53 <span class="comment">//</span>
  54 <span class="comment">// These interfaces are present for legacy reasons, and are now deprecated:</span>
  55 <span class="comment">//</span>
  56 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">&gt;</span>
  57 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  58    <span class="identifier">continued_fraction_b</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">);</span>
  59
  60 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">&gt;</span>
  61 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  62    <span class="identifier">continued_fraction_b</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">);</span>
  63
  64 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">&gt;</span>
  65 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  66    <span class="identifier">continued_fraction_a</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">);</span>
  67
  68 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Gen</span><span class="special">&gt;</span>
  69 <span class="keyword">typename</span> <span class="identifier">detail</span><span class="special">::</span><span class="identifier">fraction_traits</span><span class="special">&lt;</span><span class="identifier">Gen</span><span class="special">&gt;::</span><span class="identifier">result_type</span>
  70    <span class="identifier">continued_fraction_a</span><span class="special">(</span><span class="identifier">Gen</span><span class="special">&amp;</span> <span class="identifier">g</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">);</span>
  71
  72 <span class="special">}}}</span> <span class="comment">// namespaces</span>
  73 </pre>
  74 <h5>
  75 <a name="math_toolkit.internals1.cf.h1"></a>
  76         <span class="phrase"><a name="math_toolkit.internals1.cf.description"></a></span><a class="link" href="cf.html#math_toolkit.internals1.cf.description">Description</a>
  77       </h5>
  78 <p>
  79         <a href="http://en.wikipedia.org/wiki/Continued_fraction" target="_top">Continued fractions
  80         are a common method of approximation. </a> These functions all evaluate
  81         the continued fraction described by the <span class="emphasis"><em>generator</em></span> type
  82         argument. The functions with an "_a" suffix evaluate the fraction:
  83       </p>
  84 <p>
  85         <span class="inlinemediaobject"><img src="../../../equations/fraction2.png"></span>
  86       </p>
  87 <p>
  88         and those with a "_b" suffix evaluate the fraction:
  89       </p>
  90 <p>
  91         <span class="inlinemediaobject"><img src="../../../equations/fraction1.png"></span>
  92       </p>
  93 <p>
  94         This latter form is somewhat more natural in that it corresponds with the
  95         usual definition of a continued fraction, but note that the first <span class="emphasis"><em>a</em></span>
  96         value returned by the generator is discarded. Further, often the first <span class="emphasis"><em>a</em></span>
  97         and <span class="emphasis"><em>b</em></span> values in a continued fraction have different
  98         defining equations to the remaining terms, which may make the "_a"
  99         suffixed form more appropriate.
 100       </p>
 101 <p>
 102         The generator type should be a function object which supports the following
 103         operations:
 104       </p>
 105 <div class="informaltable"><table class="table">
 106 <colgroup>
 107 <col>
 108 <col>
 109 </colgroup>
 110 <thead><tr>
 111 <th>
 112                 <p>
 113                   Expression
 114                 </p>
 115               </th>
 116 <th>
 117                 <p>
 118                   Description
 119                 </p>
 120               </th>
 121 </tr></thead>
 122 <tbody>
 123 <tr>
 124 <td>
 125                 <p>
 126                   Gen::result_type
 127                 </p>
 128               </td>
 129 <td>
 130                 <p>
 131                   The type that is the result of invoking operator(). This can be
 132                   either an arithmetic type, or a std::pair&lt;&gt; of arithmetic
 133                   types.
 134                 </p>
 135               </td>
 136 </tr>
 137 <tr>
 138 <td>
 139                 <p>
 140                   g()
 141                 </p>
 142               </td>
 143 <td>
 144                 <p>
 145                   Returns an object of type Gen::result_type.
 146                 </p>
 147                 <p>
 148                   Each time this operator is called then the next pair of <span class="emphasis"><em>a</em></span>
 149                   and <span class="emphasis"><em>b</em></span> values is returned. Or, if result_type
 150                   is an arithmetic type, then the next <span class="emphasis"><em>b</em></span> value
 151                   is returned and all the <span class="emphasis"><em>a</em></span> values are assumed
 152                   to 1.
 153                 </p>
 154               </td>
 155 </tr>
 156 </tbody>
 157 </table></div>
 158 <p>
 159         In all the continued fraction evaluation functions the <span class="emphasis"><em>tolerance</em></span>
 160         parameter is the precision desired in the result, evaluation of the fraction
 161         will continue until the last term evaluated leaves the relative error in
 162         the result less than <span class="emphasis"><em>tolerance</em></span>. The deprecated interfaces
 163         take a number of digits precision here, internally they just convert this
 164         to a tolerance and forward call.
 165       </p>
 166 <p>
 167         If the optional <span class="emphasis"><em>max_terms</em></span> parameter is specified then
 168         no more than <span class="emphasis"><em>max_terms</em></span> calls to the generator will be
 169         made, and on output, <span class="emphasis"><em>max_terms</em></span> will be set to actual
 170         number of calls made. This facility is particularly useful when profiling
 171         a continued fraction for convergence.
 172       </p>
 173 <h5>
 174 <a name="math_toolkit.internals1.cf.h2"></a>
 175         <span class="phrase"><a name="math_toolkit.internals1.cf.implementation"></a></span><a class="link" href="cf.html#math_toolkit.internals1.cf.implementation">Implementation</a>
 176       </h5>
 177 <p>
 178         Internally these algorithms all use the modified Lentz algorithm: refer to
 179         Numeric Recipes in C++, W. H. Press et all, chapter 5, (especially 5.2 Evaluation
 180         of continued fractions, p 175 - 179) for more information, also Lentz, W.J.
 181         1976, Applied Optics, vol. 15, pp. 668-671.
 182       </p>
 183 <h5>
 184 <a name="math_toolkit.internals1.cf.h3"></a>
 185         <span class="phrase"><a name="math_toolkit.internals1.cf.examples"></a></span><a class="link" href="cf.html#math_toolkit.internals1.cf.examples">Examples</a>
 186       </h5>
 187 <p>
 188         The <a href="http://en.wikipedia.org/wiki/Golden_ratio" target="_top">golden ratio phi
 189         = 1.618033989...</a> can be computed from the simplest continued fraction
 190         of all:
 191       </p>
 192 <p>
 193         <span class="inlinemediaobject"><img src="../../../equations/fraction3.png"></span>
 194       </p>
 195 <p>
 196         We begin by defining a generator function:
 197       </p>
 198 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
 199 <span class="keyword">struct</span> <span class="identifier">golden_ratio_fraction</span>
 200 <span class="special">{</span>
 201    <span class="keyword">typedef</span> <span class="identifier">T</span> <span class="identifier">result_type</span><span class="special">;</span>
 202
 203    <span class="identifier">result_type</span> <span class="keyword">operator</span><span class="special">()</span>
 204    <span class="special">{</span>
 205       <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span>
 206    <span class="special">}</span>
 207 <span class="special">};</span>
 208 </pre>
 209 <p>
 210         The golden ratio can then be computed to double precision using:
 211       </p>
 212 <pre class="programlisting"><span class="identifier">continued_fraction_a</span><span class="special">(</span>
 213    <span class="identifier">golden_ratio_fraction</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;(),</span>
 214    <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;::</span><span class="identifier">epsilon</span><span class="special">());</span>
 215 </pre>
 216 <p>
 217         It's more usual though to have to define both the <span class="emphasis"><em>a</em></span>'s
 218         and the <span class="emphasis"><em>b</em></span>'s when evaluating special functions by continued
 219         fractions, for example the tan function is defined by:
 220       </p>
 221 <p>
 222         <span class="inlinemediaobject"><img src="../../../equations/fraction4.png"></span>
 223       </p>
 224 <p>
 225         So its generator object would look like:
 226       </p>
 227 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
 228 <span class="keyword">struct</span> <span class="identifier">tan_fraction</span>
 229 <span class="special">{</span>
 230 <span class="keyword">private</span><span class="special">:</span>
 231    <span class="identifier">T</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">b</span><span class="special">;</span>
 232 <span class="keyword">public</span><span class="special">:</span>
 233    <span class="identifier">tan_fraction</span><span class="special">(</span><span class="identifier">T</span> <span class="identifier">v</span><span class="special">)</span>
 234       <span class="special">:</span> <span class="identifier">a</span><span class="special">(-</span><span class="identifier">v</span><span class="special">*</span><span class="identifier">v</span><span class="special">),</span> <span class="identifier">b</span><span class="special">(-</span><span class="number">1</span><span class="special">)</span>
 235    <span class="special">{}</span>
 236
 237    <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="identifier">result_type</span><span class="special">;</span>
 238
 239    <span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="keyword">operator</span><span class="special">()()</span>
 240    <span class="special">{</span>
 241       <span class="identifier">b</span> <span class="special">+=</span> <span class="number">2</span><span class="special">;</span>
 242       <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">b</span><span class="special">);</span>
 243    <span class="special">}</span>
 244 <span class="special">};</span>
 245 </pre>
 246 <p>
 247         Notice that if the continuant is subtracted from the <span class="emphasis"><em>b</em></span>
 248         terms, as is the case here, then all the <span class="emphasis"><em>a</em></span> terms returned
 249         by the generator will be negative. The tangent function can now be evaluated
 250         using:
 251       </p>
 252 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
 253 <span class="identifier">T</span> <span class="identifier">tan</span><span class="special">(</span><span class="identifier">T</span> <span class="identifier">a</span><span class="special">)</span>
 254 <span class="special">{</span>
 255    <span class="identifier">tan_fraction</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="identifier">fract</span><span class="special">(</span><span class="identifier">a</span><span class="special">);</span>
 256    <span class="keyword">return</span> <span class="identifier">a</span> <span class="special">/</span> <span class="identifier">continued_fraction_b</span><span class="special">(</span><span class="identifier">fract</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;::</span><span class="identifier">epsilon</span><span class="special">());</span>
 257 <span class="special">}</span>
 258 </pre>
 259 <p>
 260         Notice that this time we're using the "_b" suffixed version to
 261         evaluate the fraction: we're removing the leading <span class="emphasis"><em>a</em></span>
 262         term during fraction evaluation as it's different from all the others.
 263       </p>
 264 </div>
 265 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 266 <td align="left"></td>
 267 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2010, 2012-2014 Nikhar Agrawal,
 268       Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
 269       Holin, Bruno Lalande, John Maddock, Johan R&#229;de, Gautam Sewani, Benjamin Sobotta,
 270       Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p>
 271         Distributed under the Boost Software License, Version 1.0. (See accompanying
 272         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>)
 273       </p>
 274 </div></td>
 275 </tr></table>
 276 <hr>
 277 <div class="spirit-nav">
 278 <a accesskey="p" href="series_evaluation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals1.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="rational.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 279 </div>
 280 </body>
 281 </html>