]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [section:bernoulli_numbers Bernoulli Numbers] |
2 | ||
3 | [@https://en.wikipedia.org/wiki/Bernoulli_number Bernoulli numbers] | |
4 | are a sequence of rational numbers useful for the Taylor series expansion, | |
5 | Euler-Maclaurin formula, and the Riemann zeta function. | |
6 | ||
7 | Bernoulli numbers are used in evaluation of some Boost.Math functions, | |
8 | including the __tgamma, __lgamma and polygamma functions. | |
9 | ||
10 | [h4 Single Bernoulli number] | |
11 | ||
12 | [h4 Synopsis] | |
13 | ||
14 | `` | |
15 | #include <boost/math/special_functions/bernoulli.hpp> | |
16 | `` | |
17 | ||
18 | namespace boost { namespace math { | |
19 | ||
20 | template <class T> | |
21 | T bernoulli_b2n(const int n); // Single Bernoulli number (default policy). | |
22 | ||
23 | template <class T, class Policy> | |
24 | T bernoulli_b2n(const int n, const Policy &pol); // User policy for errors etc. | |
25 | ||
26 | }} // namespaces | |
27 | ||
28 | [h4 Description] | |
29 | ||
30 | Both return the (2 * n)[super th] Bernoulli number B[sub 2n]. | |
31 | ||
32 | Note that since all odd numbered Bernoulli numbers are zero (apart from B[sub 1] which is [plusminus][frac12]) | |
33 | the interface will only return the even numbered Bernoulli numbers. | |
34 | ||
35 | This function uses fast table lookup for low-indexed Bernoulli numbers, while larger values are calculated | |
36 | as needed and then cached. The caching mechanism requires a certain amount of thread safety code, so | |
37 | `unchecked_bernoulli_b2n` may provide a better interface for performance critical code. | |
38 | ||
39 | The final __Policy argument is optional and can be used to control the behaviour of the function: | |
40 | how it handles errors, what level of precision to use, etc. | |
41 | ||
42 | Refer to __policy_section for more details. | |
43 | ||
44 | [h4 Examples] | |
45 | ||
46 | [import ../../example/bernoulli_example.cpp] | |
47 | [bernoulli_example_1] | |
48 | ||
49 | [bernoulli_output_1] | |
50 | ||
51 | [h4 Single (unchecked) Bernoulli number] | |
52 | ||
53 | [h4 Synopsis] | |
54 | `` | |
55 | #include <boost/math/special_functions/bernoulli.hpp> | |
56 | ||
57 | `` | |
58 | ||
59 | template <> | |
60 | struct max_bernoulli_b2n<T>; | |
61 | ||
62 | template<class T> | |
63 | inline T unchecked_bernoulli_b2n(unsigned n); | |
64 | ||
65 | `unchecked_bernoulli_b2n` provides access to Bernoulli numbers [*without any checks for overflow or invalid parameters]. | |
66 | It is implemented as a direct (and very fast) table lookup, and while not recommended for general use it can be useful | |
67 | inside inner loops where the ultimate performance is required, and error checking is moved outside the loop. | |
68 | ||
69 | The largest value you can pass to `unchecked_bernoulli_b2n<>` is `max_bernoulli_b2n<>::value`: passing values greater than | |
70 | that will result in a buffer overrun error, so it's clearly important to place the error handling in your own code | |
71 | when using this direct interface. | |
72 | ||
73 | The value of `boost::math::max_bernoulli_b2n<T>::value` varies by the type T, for types `float`/`double`/`long double` | |
74 | it's the largest value which doesn't overflow the target type: for example, `boost::math::max_bernoulli_b2n<double>::value` is 129. | |
75 | However, for multiprecision types, it's the largest value for which the result can be represented as the ratio of two 64-bit | |
76 | integers, for example `boost::math::max_bernoulli_b2n<boost::multiprecision::cpp_dec_float_50>::value` is just 17. Of course | |
77 | larger indexes can be passed to `bernoulli_b2n<T>(n)`, but then you lose fast table lookup (i.e. values may need to be calculated). | |
78 | ||
79 | [bernoulli_example_4] | |
80 | [bernoulli_output_4] | |
81 | ||
82 | [h4 Multiple Bernoulli Numbers] | |
83 | ||
84 | [h4 Synopsis] | |
85 | ||
86 | `` | |
87 | #include <boost/math/special_functions/bernoulli.hpp> | |
88 | `` | |
89 | ||
90 | namespace boost { namespace math { | |
91 | ||
92 | // Multiple Bernoulli numbers (default policy). | |
93 | template <class T, class OutputIterator> | |
94 | OutputIterator bernoulli_b2n( | |
95 | int start_index, | |
96 | unsigned number_of_bernoullis_b2n, | |
97 | OutputIterator out_it); | |
98 | ||
99 | // Multiple Bernoulli numbers (user policy). | |
100 | template <class T, class OutputIterator, class Policy> | |
101 | OutputIterator bernoulli_b2n( | |
102 | int start_index, | |
103 | unsigned number_of_bernoullis_b2n, | |
104 | OutputIterator out_it, | |
105 | const Policy& pol); | |
106 | }} // namespaces | |
107 | ||
108 | [h4 Description] | |
109 | ||
110 | Two versions of the Bernoulli number function are provided to compute multiple Bernoulli numbers | |
111 | with one call (one with default policy and the other allowing a user-defined policy). | |
112 | ||
113 | These return a series of Bernoulli numbers: | |
114 | ||
115 | [:B[sub 2*start_index],B[sub 2*(start_index+1)],...,B[sub 2*(start_index+number_of_bernoullis_b2n-1)]] | |
116 | ||
117 | [h4 Examples] | |
118 | [bernoulli_example_2] | |
119 | [bernoulli_output_2] | |
120 | [bernoulli_example_3] | |
121 | [bernoulli_output_3] | |
122 | ||
123 | The source of this example is at [@../../example/bernoulli_example.cpp bernoulli_example.cpp] | |
124 | ||
125 | [h4 Accuracy] | |
126 | ||
127 | All the functions usually return values within one ULP (unit in the last place) for the floating-point type. | |
128 | ||
129 | [h4 Implementation] | |
130 | ||
131 | The implementation details are in [@../../include/boost/math/special_functions/detail/bernoulli_details.hpp bernoulli_details.hpp] | |
132 | and [@../../include/boost/math/special_functions/detail/unchecked_bernoulli.hpp unchecked_bernoulli.hpp]. | |
133 | ||
134 | For `i <= max_bernoulli_index<T>::value` this is implemented by simple table lookup from a statically initialized table; | |
135 | for larger values of `i`, this is implemented by the Tangent Numbers algorithm as described in the paper: | |
136 | Fast Computation of Bernoulli, Tangent and Secant Numbers, Richard P. Brent and David Harvey, | |
137 | [@http://arxiv.org/pdf/1108.0286v3.pdf] (2011). | |
138 | ||
139 | [@http://mathworld.wolfram.com/TangentNumber.html Tangent (or Zag) numbers] | |
140 | (an even alternating permutation number) are defined | |
141 | and their generating function is also given therein. | |
142 | ||
143 | The relation of Tangent numbers with Bernoulli numbers ['B[sub i]] | |
144 | is given by Brent and Harvey's equation 14: | |
145 | ||
146 | __spaces[equation tangent_numbers] | |
147 | ||
148 | Their relation with Bernoulli numbers ['B[sub i]] are defined by | |
149 | ||
150 | if i > 0 and i is even then | |
151 | __spaces[equation bernoulli_numbers] [br] | |
152 | elseif i == 0 then ['B[sub i]] = 1 [br] | |
153 | elseif i == 1 then ['B[sub i]] = -1/2 [br] | |
154 | elseif i < 0 or i is odd then ['B[sub i]] = 0 | |
155 | ||
156 | Note that computed values are stored in a fixed-size table, access is thread safe via atomic operations (i.e. lock | |
157 | free programming), this imparts a much lower overhead on access to cached values than might otherwise be expected - | |
158 | typically for multiprecision types the cost of thread synchronisation is negligible, while for built in types | |
159 | this code is not normally executed anyway. For very large arguments which cannot be reasonably computed or | |
160 | stored in our cache, an asymptotic expansion [@http://www.luschny.de/math/primes/bernincl.html due to Luschny] is used: | |
161 | ||
162 | [equation bernoulli_numbers2] | |
163 | ||
164 | [endsect] [/section:bernoulli_numbers Bernoulli Numbers] | |
165 | ||
166 | ||
167 | [section:tangent_numbers Tangent Numbers] | |
168 | ||
169 | [@http://en.wikipedia.org/wiki/Tangent_numbers Tangent numbers], | |
170 | also called a zag function. See also | |
171 | [@http://mathworld.wolfram.com/TangentNumber.html Tangent number]. | |
172 | ||
173 | From the number, An, of alternating permutations of the set {1, ..., n}, | |
174 | the numbers A2n+1 with odd indices are called tangent numbers or zag numbers. | |
175 | The first few values are 1, 2, 16, 272, 7936, 353792, 22368256, 1903757312 ... | |
176 | (sequence [@http://oeis.org/A000182 A000182 in OEIS]). | |
177 | They are called tangent numbers because they appear as | |
178 | numerators in the Maclaurin series of tan x. | |
179 | ||
180 | Tangent numbers are used in the computation of Bernoulli numbers, | |
181 | but are also made available here. | |
182 | ||
183 | [h4 Synopsis] | |
184 | `` | |
185 | #include <boost/math/special_functions/detail/bernoulli.hpp> | |
186 | `` | |
187 | ||
188 | template <class T> | |
189 | T tangent_t2n(const int i); // Single tangent number (default policy). | |
190 | ||
191 | template <class T, class Policy> | |
192 | T tangent_t2n(const int i, const Policy &pol); // Single tangent number (user policy). | |
193 | ||
194 | // Multiple tangent numbers (default policy). | |
195 | template <class T, class OutputIterator> | |
196 | OutputIterator tangent_t2n(const int start_index, | |
197 | const unsigned number_of_tangent_t2n, | |
198 | OutputIterator out_it); | |
199 | ||
200 | // Multiple tangent numbers (user policy). | |
201 | template <class T, class OutputIterator, class Policy> | |
202 | OutputIterator tangent_t2n(const int start_index, | |
203 | const unsigned number_of_tangent_t2n, | |
204 | OutputIterator out_it, | |
205 | const Policy& pol); | |
206 | ||
207 | [h4 Examples] | |
208 | ||
209 | [tangent_example_1] | |
210 | ||
211 | The output is: | |
212 | [tangent_output_1] | |
213 | ||
214 | The source of this example is at [../../example/bernoulli_example.cpp bernoulli_example.cpp] | |
215 | ||
216 | [endsect] [/section:tangent_numbers Tangent Numbers] | |
217 | ||
218 | [/ | |
219 | Copyright 2013, 2014 Nikhar Agrawal, Christopher Kormanyos, John Maddock, Paul A. Bristow. | |
220 | Distributed under the Boost Software License, Version 1.0. | |
221 | (See accompanying file LICENSE_1_0.txt or copy at | |
222 | http://www.boost.org/LICENSE_1_0.txt). | |
223 | ] |