1 [section:cf Continued Fraction Evaluation]
6 #include <boost/math/tools/fraction.hpp>
9 namespace boost{ namespace math{ namespace tools{
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)
15 template <class Gen, class U>
16 typename detail::fraction_traits<Gen>::result_type
17 continued_fraction_b(Gen& g, const U& tolerance)
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)
23 template <class Gen, class U>
24 typename detail::fraction_traits<Gen>::result_type
25 continued_fraction_a(Gen& g, const U& tolerance)
28 // These interfaces are present for legacy reasons, and are now deprecated:
31 typename detail::fraction_traits<Gen>::result_type
32 continued_fraction_b(Gen& g, int bits);
35 typename detail::fraction_traits<Gen>::result_type
36 continued_fraction_b(Gen& g, int bits, boost::uintmax_t& max_terms);
39 typename detail::fraction_traits<Gen>::result_type
40 continued_fraction_a(Gen& g, int bits);
43 typename detail::fraction_traits<Gen>::result_type
44 continued_fraction_a(Gen& g, int bits, boost::uintmax_t& max_terms);
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:
56 and those with a "_b" suffix evaluate the fraction:
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.
66 The generator type should be a function object which supports the following
70 [[Expression] [Description]]
71 [[Gen::result_type] [The type that is the result of invoking operator().
72 This can be either an arithmetic type, or a std::pair<> of arithmetic types.]]
73 [[g()] [Returns an object of type Gen::result_type.
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
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.
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.
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.
103 The [@http://en.wikipedia.org/wiki/Golden_ratio golden ratio phi = 1.618033989...]
104 can be computed from the simplest continued fraction of all:
108 We begin by defining a generator function:
111 struct golden_ratio_fraction
113 typedef T result_type;
115 result_type operator()
121 The golden ratio can then be computed to double precision using:
123 continued_fraction_a(
124 golden_ratio_fraction<double>(),
125 std::numeric_limits<double>::epsilon());
127 It's more usual though to have to define both the /a/'s and the /b/'s
128 when evaluating special functions by continued fractions, for example
129 the tan function is defined by:
133 So its generator object would look like:
145 typedef std::pair<T,T> result_type;
147 std::pair<T,T> operator()()
150 return std::make_pair(a, b);
154 Notice that if the continuant is subtracted from the /b/ terms,
155 as is the case here, then all the /a/ terms returned by the generator
156 will be negative. The tangent function can now be evaluated using:
161 tan_fraction<T> fract(a);
162 return a / continued_fraction_b(fract, std::numeric_limits<T>::epsilon());
165 Notice that this time we're using the "_b" suffixed version to evaluate
166 the fraction: we're removing the leading /a/ term during fraction evaluation
167 as it's different from all the others.
169 [endsect][/section:cf Continued Fraction Evaluation]
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).