libs/math/doc/internals/fraction.qbk

   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. ]
  51 These functions all evaluate the continued fraction described by the /generator/
  52 type argument.  The functions with an "_a" suffix evaluate the fraction:
  53
  54 [equation fraction2]
  55
  56 and those with a "_b" suffix evaluate the fraction:
  57
  58 [equation fraction1]
  59
  60 This latter form is somewhat more natural in that it corresponds with the usual
  61 definition of a continued fraction, but note that the first /a/ value returned by
  62 the generator is discarded.  Further, often the first /a/ and /b/ values in a
  63 continued fraction have different defining equations to the remaining terms, which
  64 may make the "_a" suffixed form more appropriate.
  65
  66 The generator type should be a function object which supports the following
  67 operations:
  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
  75 Each 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
  81 In all the continued fraction evaluation functions the /tolerance/ parameter is the
  82 precision desired in the result, evaluation of the fraction will
  83 continue until the last term evaluated leaves the relative error in the result
  84 less than /tolerance/.  The deprecated interfaces take a number of digits precision
  85 here, internally they just convert this to a tolerance and forward call.
  86
  87 If the optional /max_terms/ parameter is specified then no more than /max_terms/
  88 calls to the generator will be made, and on output,
  89 /max_terms/ will be set to actual number of
  90 calls made.  This facility is particularly useful when profiling a continued
  91 fraction for convergence.
  92
  93 [h4 Implementation]
  94
  95 Internally these algorithms all use the modified Lentz algorithm: refer to
  96 Numeric Recipes in C++, W. H. Press et all, chapter 5,
  97 (especially 5.2 Evaluation of continued fractions, p 175 - 179)
  98 for more information, also
  99 Lentz, W.J. 1976, Applied Optics, vol. 15, pp. 668-671.
 100
 101 [h4 Examples]
 102
 103 [import ../../example/continued_fractions.cpp]
 104
 105 All of these examples are in [@../../example/continued_fractions.cpp continued_fractions.cpp].
 106
 107 The [@http://en.wikipedia.org/wiki/Golden_ratio golden ratio phi = 1.618033989...]
 108 can be computed from the simplest continued fraction of all:
 109
 110 [equation fraction3]
 111
 112 We begin by defining a generator function:
 113
 114 [golden_ratio_1]
 115
 116 The golden ratio can then be computed to double precision using:
 117
 118 [cf_gr]
 119
 120 It's more usual though to have to define both the /a/'s and the /b/'s
 121 when evaluating special functions by continued fractions, for example
 122 the tan function is defined by:
 123
 124 [equation fraction4]
 125
 126 So its generator object would look like:
 127
 128 [cf_tan_fraction]
 129
 130 Notice that if the continuant is subtracted from the /b/ terms,
 131 as is the case here, then all the /a/ terms returned by the generator
 132 will be negative.  The tangent function can now be evaluated using:
 133
 134 [cf_tan]
 135
 136 Notice that this time we're using the "_b" suffixed version to evaluate
 137 the fraction: we're removing the leading /a/ term during fraction evaluation
 138 as it's different from all the others.
 139
 140 Now we'll look at a couple of complex number examples, starting with the exponential
 141 integral which can be calculated via:
 142
 143 [equation expint_n_3]
 144
 145 So our functor looks like this:
 146
 147 [cf_expint_fraction]
 148
 149 We can finish the example by wrapping everything up in a function:
 150
 151 [cf_expint]
 152
 153 Notice how the termination condition is still expressed as a complex number, albeit one with zero imaginary part.
 154
 155 Our final example will use [^continued_fraction_a], in fact there is only one special function in our code
 156 which uses that variant, and it's the upper incomplete gamma function (Q), which can be calculated via:
 157
 158 [equation igamma9]
 159
 160 In 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
 165 So 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