1[section:cf Continued Fraction Evaluation] 2 3[h4 Synopsis] 4 5`` 6#include <boost/math/tools/fraction.hpp> 7`` 8 9 namespace boost{ namespace math{ namespace tools{ 10 11 template <class Gen, class U> 12 typename detail::fraction_traits<Gen>::result_type 13 continued_fraction_b(Gen& g, const U& tolerance, boost::uintmax_t& max_terms) 14 15 template <class Gen, class U> 16 typename detail::fraction_traits<Gen>::result_type 17 continued_fraction_b(Gen& g, const U& tolerance) 18 19 template <class Gen, class U> 20 typename detail::fraction_traits<Gen>::result_type 21 continued_fraction_a(Gen& g, const U& tolerance, boost::uintmax_t& max_terms) 22 23 template <class Gen, class U> 24 typename detail::fraction_traits<Gen>::result_type 25 continued_fraction_a(Gen& g, const U& tolerance) 26 27 // 28 // These interfaces are present for legacy reasons, and are now deprecated: 29 // 30 template <class Gen> 31 typename detail::fraction_traits<Gen>::result_type 32 continued_fraction_b(Gen& g, int bits); 33 34 template <class Gen> 35 typename detail::fraction_traits<Gen>::result_type 36 continued_fraction_b(Gen& g, int bits, boost::uintmax_t& max_terms); 37 38 template <class Gen> 39 typename detail::fraction_traits<Gen>::result_type 40 continued_fraction_a(Gen& g, int bits); 41 42 template <class Gen> 43 typename detail::fraction_traits<Gen>::result_type 44 continued_fraction_a(Gen& g, int bits, boost::uintmax_t& max_terms); 45 46 }}} // namespaces 47 48[h4 Description] 49 50[@http://en.wikipedia.org/wiki/Continued_fraction Continued fractions are a common method of approximation. ] 51These functions all evaluate the continued fraction described by the /generator/ 52type argument. The functions with an "_a" suffix evaluate the fraction: 53 54[equation fraction2] 55 56and those with a "_b" suffix evaluate the fraction: 57 58[equation fraction1] 59 60This latter form is somewhat more natural in that it corresponds with the usual 61definition of a continued fraction, but note that the first /a/ value returned by 62the generator is discarded. Further, often the first /a/ and /b/ values in a 63continued fraction have different defining equations to the remaining terms, which 64may make the "_a" suffixed form more appropriate. 65 66The generator type should be a function object which supports the following 67operations: 68 69[table 70[[Expression] [Description]] 71[[Gen::result_type] [The type that is the result of invoking operator(). 72 This can be either an arithmetic or complex type, or a std::pair<> of arithmetic or complex types.]] 73[[g()] [Returns an object of type Gen::result_type. 74 75Each time this operator is called then the next pair of /a/ and /b/ 76 values is returned. Or, if result_type is an arithmetic type, 77 then the next /b/ value is returned and all the /a/ values 78 are assumed to 1.]] 79] 80 81In all the continued fraction evaluation functions the /tolerance/ parameter is the 82precision desired in the result, evaluation of the fraction will 83continue until the last term evaluated leaves the relative error in the result 84less than /tolerance/. The deprecated interfaces take a number of digits precision 85here, internally they just convert this to a tolerance and forward call. 86 87If the optional /max_terms/ parameter is specified then no more than /max_terms/ 88calls to the generator will be made, and on output, 89/max_terms/ will be set to actual number of 90calls made. This facility is particularly useful when profiling a continued 91fraction for convergence. 92 93[h4 Implementation] 94 95Internally these algorithms all use the modified Lentz algorithm: refer to 96Numeric Recipes in C++, W. H. Press et all, chapter 5, 97(especially 5.2 Evaluation of continued fractions, p 175 - 179) 98for more information, also 99Lentz, W.J. 1976, Applied Optics, vol. 15, pp. 668-671. 100 101[h4 Examples] 102 103[import ../../example/continued_fractions.cpp] 104 105All of these examples are in [@../../example/continued_fractions.cpp continued_fractions.cpp]. 106 107The [@http://en.wikipedia.org/wiki/Golden_ratio golden ratio phi = 1.618033989...] 108can be computed from the simplest continued fraction of all: 109 110[equation fraction3] 111 112We begin by defining a generator function: 113 114[golden_ratio_1] 115 116The golden ratio can then be computed to double precision using: 117 118[cf_gr] 119 120It's more usual though to have to define both the /a/'s and the /b/'s 121when evaluating special functions by continued fractions, for example 122the tan function is defined by: 123 124[equation fraction4] 125 126So its generator object would look like: 127 128[cf_tan_fraction] 129 130Notice that if the continuant is subtracted from the /b/ terms, 131as is the case here, then all the /a/ terms returned by the generator 132will be negative. The tangent function can now be evaluated using: 133 134[cf_tan] 135 136Notice that this time we're using the "_b" suffixed version to evaluate 137the fraction: we're removing the leading /a/ term during fraction evaluation 138as it's different from all the others. 139 140Now we'll look at a couple of complex number examples, starting with the exponential 141integral which can be calculated via: 142 143[equation expint_n_3] 144 145So our functor looks like this: 146 147[cf_expint_fraction] 148 149We can finish the example by wrapping everything up in a function: 150 151[cf_expint] 152 153Notice how the termination condition is still expressed as a complex number, albeit one with zero imaginary part. 154 155Our final example will use [^continued_fraction_a], in fact there is only one special function in our code 156which uses that variant, and it's the upper incomplete gamma function (Q), which can be calculated via: 157 158[equation igamma9] 159 160In this case the first couple of terms are different from the rest, so our fraction will start with the first 161"regular" a term: 162 163[cf_upper_gamma_fraction] 164 165So now we can implement Q, this time using [^continued_fraction_a]: 166 167[cf_gamma_Q] 168 169[endsect] [/section:cf Continued Fraction Evaluation] 170 171[/ 172 Copyright 2006 John Maddock and Paul A. Bristow. 173 Distributed under the Boost Software License, Version 1.0. 174 (See accompanying file LICENSE_1_0.txt or copy at 175 http://www.boost.org/LICENSE_1_0.txt). 176] 177 178