]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [section:factorials Factorials and Binomial Coefficients] |
2 | ||
3 | [section:sf_factorial Factorial] | |
4 | ||
5 | [h4 Synopsis] | |
6 | ||
7 | `` | |
8 | #include <boost/math/special_functions/factorials.hpp> | |
9 | `` | |
10 | ||
11 | namespace boost{ namespace math{ | |
12 | ||
13 | template <class T> | |
14 | T factorial(unsigned i); | |
15 | ||
16 | template <class T, class ``__Policy``> | |
17 | T factorial(unsigned i, const ``__Policy``&); | |
18 | ||
19 | template <class T> | |
20 | T unchecked_factorial(unsigned i); | |
21 | ||
22 | template <class T> | |
23 | struct max_factorial; | |
24 | ||
25 | }} // namespaces | |
26 | ||
27 | [h4 Description] | |
28 | ||
29 | [important | |
30 | The functions described below are templates where the template argument T CANNOT be deduced from the | |
31 | arguments passed to the function. Therefore if you write something like: | |
32 | ||
33 | `boost::math::factorial(2);` | |
34 | ||
35 | You will get a (perhaps perplexing) compiler error, ususally indicating that there is no such function to be found. | |
36 | Instead you need to specify the return type explicity and write: | |
37 | ||
38 | `boost::math::factorial<double>(2);` | |
39 | ||
40 | So that the return type is known. | |
41 | ||
42 | Furthermore, the template argument must be a real-valued type such as `float` or `double` | |
43 | and not an integer type - that would overflow far too easily for quite small values of parameter `i`! | |
44 | ||
45 | The source code `static_assert` and comment just after the will be: | |
46 | ||
47 | `` | |
48 | BOOST_STATIC_ASSERT(!boost::is_integral<T>::value); | |
49 | // factorial<unsigned int>(n) is not implemented | |
50 | // because it would overflow integral type T for too small n | |
51 | // to be useful. Use instead a floating-point type, | |
52 | // and convert to an unsigned type if essential, for example: | |
53 | // unsigned int nfac = static_cast<unsigned int>(factorial<double>(n)); | |
54 | // See factorial documentation for more detail. | |
55 | `` | |
56 | ] | |
57 | ||
58 | template <class T> | |
59 | T factorial(unsigned i); | |
60 | ||
61 | template <class T, class ``__Policy``> | |
62 | T factorial(unsigned i, const ``__Policy``&); | |
63 | ||
64 | Returns [^i!]. | |
65 | ||
66 | [optional_policy] | |
67 | ||
68 | For [^i <= max_factorial<T>::value] this is implemented by table lookup, | |
69 | for larger values of [^i], this function is implemented in terms of __tgamma. | |
70 | ||
71 | If [^i] is so large that the result can not be represented in type T, then | |
72 | calls __overflow_error. | |
73 | ||
74 | template <class T> | |
75 | T unchecked_factorial(unsigned i); | |
76 | ||
77 | Returns [^i!]. | |
78 | ||
79 | Internally this function performs table lookup of the result. Further it performs | |
80 | no range checking on the value of i: it is up to the caller to ensure | |
81 | that [^i <= max_factorial<T>::value]. This function is intended to be used | |
82 | inside inner loops that require fast table lookup of factorials, but requires | |
83 | care to ensure that argument [^i] never grows too large. | |
84 | ||
85 | template <class T> | |
86 | struct max_factorial | |
87 | { | |
88 | static const unsigned value = X; | |
89 | }; | |
90 | ||
91 | This traits class defines the largest value that can be passed to | |
92 | [^unchecked_factorial]. The member `value` can be used where integral | |
93 | constant expressions are required: for example to define the size of | |
94 | further tables that depend on the factorials. | |
95 | ||
96 | [h4 Accuracy] | |
97 | ||
98 | For arguments smaller than `max_factorial<T>::value` | |
99 | the result should be | |
100 | correctly rounded. For larger arguments the accuracy will be the same | |
101 | as for __tgamma. | |
102 | ||
103 | [h4 Testing] | |
104 | ||
105 | Basic sanity checks and spot values to verify the data tables: | |
106 | the main tests for the __tgamma function handle those cases already. | |
107 | ||
108 | [h4 Implementation] | |
109 | ||
110 | The factorial function is table driven for small arguments, and is | |
111 | implemented in terms of __tgamma for larger arguments. | |
112 | ||
113 | [endsect] | |
114 | ||
115 | [section:sf_double_factorial Double Factorial] | |
116 | ||
117 | `` | |
118 | #include <boost/math/special_functions/factorials.hpp> | |
119 | `` | |
120 | ||
121 | namespace boost{ namespace math{ | |
122 | ||
123 | template <class T> | |
124 | T double_factorial(unsigned i); | |
125 | ||
126 | template <class T, class ``__Policy``> | |
127 | T double_factorial(unsigned i, const ``__Policy``&); | |
128 | ||
129 | }} // namespaces | |
130 | ||
131 | Returns [^i!!]. | |
132 | ||
133 | [optional_policy] | |
134 | ||
135 | May return the result of __overflow_error if the result is too large | |
136 | to represent in type T. The implementation is designed to be optimised | |
137 | for small /i/ where table lookup of i! is possible. | |
138 | ||
139 | [important | |
140 | The functions described above are templates where the template argument T can not be deduced from the | |
141 | arguments passed to the function. Therefore if you write something like: | |
142 | ||
143 | `boost::math::double_factorial(2);` | |
144 | ||
145 | You will get a (possibly perplexing) compiler error, ususally indicating that there is no such function to be found. Instead you need to specifiy | |
146 | the return type explicity and write: | |
147 | ||
148 | `boost::math::double_factorial<double>(2);` | |
149 | ||
150 | So that the return type is known. Further, the template argument must be a real-valued type such as `float` or `double` | |
151 | and not an integer type - that would overflow far too easily! | |
152 | ||
153 | The source code `static_assert` and comment just after the will be: | |
154 | ||
155 | `` | |
156 | BOOST_STATIC_ASSERT(!boost::is_integral<T>::value); | |
157 | // factorial<unsigned int>(n) is not implemented | |
158 | // because it would overflow integral type T for too small n | |
159 | // to be useful. Use instead a floating-point type, | |
160 | // and convert to an unsigned type if essential, for example: | |
161 | // unsigned int nfac = static_cast<unsigned int>(factorial<double>(n)); | |
162 | // See factorial documentation for more detail. | |
163 | `` | |
164 | ] | |
165 | ||
166 | [note The argument to `double_factorial` is type `unsigned` even though technically -1!! is defined.] | |
167 | ||
168 | [h4 Accuracy] | |
169 | ||
170 | The implementation uses a trivial adaptation of | |
171 | the factorial function, so error rates should be no more than a couple | |
172 | of epsilon higher. | |
173 | ||
174 | [h4 Testing] | |
175 | ||
176 | The spot tests for the double factorial use data | |
177 | generated by functions.wolfram.com. | |
178 | ||
179 | [h4 Implementation] | |
180 | ||
181 | The double factorial is implemented in terms of the factorial and gamma | |
182 | functions using the relations: | |
183 | ||
184 | (2n)!! = 2[super n ] * n! | |
185 | ||
186 | (2n+1)!! = (2n+1)! / (2[super n ] n!) | |
187 | ||
188 | and | |
189 | ||
190 | (2n-1)!! = [Gamma]((2n+1)/2) * 2[super n ] / sqrt(pi) | |
191 | ||
192 | [endsect] | |
193 | ||
194 | [section:sf_rising_factorial Rising Factorial] | |
195 | ||
196 | `` | |
197 | #include <boost/math/special_functions/factorials.hpp> | |
198 | `` | |
199 | ||
200 | namespace boost{ namespace math{ | |
201 | ||
202 | template <class T> | |
203 | ``__sf_result`` rising_factorial(T x, int i); | |
204 | ||
205 | template <class T, class ``__Policy``> | |
206 | ``__sf_result`` rising_factorial(T x, int i, const ``__Policy``&); | |
207 | ||
208 | }} // namespaces | |
209 | ||
210 | Returns the rising factorial of /x/ and /i/: | |
211 | ||
212 | rising_factorial(x, i) = [Gamma](x + i) / [Gamma](x); | |
213 | ||
214 | or | |
215 | ||
216 | rising_factorial(x, i) = x(x+1)(x+2)(x+3)...(x+i-1) | |
217 | ||
218 | Note that both /x/ and /i/ can be negative as well as positive. | |
219 | ||
220 | [optional_policy] | |
221 | ||
222 | May return the result of __overflow_error if the result is too large | |
223 | to represent in type T. | |
224 | ||
225 | The return type of these functions is computed using the __arg_promotion_rules: | |
226 | the type of the result is `double` if T is an integer type, otherwise the type | |
227 | of the result is T. | |
228 | ||
229 | [h4 Accuracy] | |
230 | ||
231 | The accuracy will be the same as | |
232 | the __tgamma_delta_ratio function. | |
233 | ||
234 | [h4 Testing] | |
235 | ||
236 | The spot tests for the rising factorials use data generated | |
237 | by functions.wolfram.com. | |
238 | ||
239 | [h4 Implementation] | |
240 | ||
241 | Rising and falling factorials are implemented as ratios of gamma functions | |
242 | using __tgamma_delta_ratio. Optimisations for | |
243 | small integer arguments are handled internally by that function. | |
244 | ||
245 | [endsect] | |
246 | ||
247 | [section:sf_falling_factorial Falling Factorial] | |
248 | ||
249 | `` | |
250 | #include <boost/math/special_functions/factorials.hpp> | |
251 | `` | |
252 | ||
253 | namespace boost{ namespace math{ | |
254 | ||
255 | template <class T> | |
256 | ``__sf_result`` falling_factorial(T x, unsigned i); | |
257 | ||
258 | template <class T, class ``__Policy``> | |
259 | ``__sf_result`` falling_factorial(T x, unsigned i, const ``__Policy``&); | |
260 | ||
261 | }} // namespaces | |
262 | ||
263 | Returns the falling factorial of /x/ and /i/: | |
264 | ||
265 | falling_factorial(x, i) = x(x-1)(x-2)(x-3)...(x-i+1) | |
266 | ||
267 | Note that this function is only defined for positive /i/, hence the | |
268 | `unsigned` second argument. Argument /x/ can be either positive or | |
269 | negative however. | |
270 | ||
271 | [optional_policy] | |
272 | ||
273 | May return the result of __overflow_error if the result is too large | |
274 | to represent in type T. | |
275 | ||
276 | The return type of these functions is computed using the __arg_promotion_rules: | |
277 | the type of the result is `double` if T is an integer type, otherwise the type | |
278 | of the result is T. | |
279 | ||
280 | [h4 Accuracy] | |
281 | ||
282 | The accuracy will be the same as | |
283 | the __tgamma_delta_ratio function. | |
284 | ||
285 | [h4 Testing] | |
286 | ||
287 | The spot tests for the falling factorials use data generated by | |
288 | functions.wolfram.com. | |
289 | ||
290 | [h4 Implementation] | |
291 | ||
292 | Rising and falling factorials are implemented as ratios of gamma functions | |
293 | using __tgamma_delta_ratio. Optimisations for | |
294 | small integer arguments are handled internally by that function. | |
295 | ||
296 | [endsect] | |
297 | ||
298 | [section:sf_binomial Binomial Coefficients] | |
299 | ||
300 | `` | |
301 | #include <boost/math/special_functions/binomial.hpp> | |
302 | `` | |
303 | ||
304 | namespace boost{ namespace math{ | |
305 | ||
306 | template <class T> | |
307 | T binomial_coefficient(unsigned n, unsigned k); | |
308 | ||
309 | template <class T, class ``__Policy``> | |
310 | T binomial_coefficient(unsigned n, unsigned k, const ``__Policy``&); | |
311 | ||
312 | }} // namespaces | |
313 | ||
314 | Returns the binomial coefficient: [sub n]C[sub k]. | |
315 | ||
316 | Requires k <= n. | |
317 | ||
318 | [optional_policy] | |
319 | ||
320 | May return the result of __overflow_error if the result is too large | |
321 | to represent in type T. | |
322 | ||
323 | [important | |
324 | The functions described above are templates where the template argument T can not be deduced from the | |
325 | arguments passed to the function. Therefore if you write something like: | |
326 | ||
327 | `boost::math::binomial_coefficient(10, 2);` | |
328 | ||
329 | You will get a compiler error, ususally indicating that there is no such function to be found. Instead you need to specifiy | |
330 | the return type explicity and write: | |
331 | ||
332 | `boost::math::binomial_coefficient<double>(10, 2);` | |
333 | ||
334 | So that the return type is known. Further, the template argument must be a real-valued type such as `float` or `double` | |
335 | and not an integer type - that would overflow far too easily! | |
336 | ] | |
337 | ||
338 | [h4 Accuracy] | |
339 | ||
340 | The accuracy will be the same as for the | |
341 | factorials for small arguments (i.e. no more than one or two epsilon), | |
342 | and the __beta function for larger arguments. | |
343 | ||
344 | [h4 Testing] | |
345 | ||
346 | The spot tests for the binomial coefficients use data | |
347 | generated by functions.wolfram.com. | |
348 | ||
349 | [h4 Implementation] | |
350 | ||
351 | Binomial coefficients are calculated using table lookup of factorials | |
352 | where possible using: | |
353 | ||
354 | [sub n]C[sub k] = n! / (k!(n-k)!) | |
355 | ||
356 | Otherwise it is implemented in terms of the beta function using the relations: | |
357 | ||
358 | [sub n]C[sub k] = 1 / (k * __beta(k, n-k+1)) | |
359 | ||
360 | and | |
361 | ||
362 | [sub n]C[sub k] = 1 / ((n-k) * __beta(k+1, n-k)) | |
363 | ||
364 | [endsect] | |
365 | ||
366 | ||
367 | [endsect][/section:factorials Factorials] | |
368 | ||
369 | [/ | |
370 | Copyright 2006, 2010 John Maddock and Paul A. Bristow. | |
371 | Distributed under the Boost Software License, Version 1.0. | |
372 | (See accompanying file LICENSE_1_0.txt or copy at | |
373 | http://www.boost.org/LICENSE_1_0.txt). | |
374 | ] |