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