1 [section:factorials Factorials and Binomial Coefficients]
3 [section:sf_factorial Factorial]
8 #include <boost/math/special_functions/factorials.hpp>
11 namespace boost{ namespace math{
14 T factorial(unsigned i);
16 template <class T, class ``__Policy``>
17 T factorial(unsigned i, const ``__Policy``&);
20 T unchecked_factorial(unsigned i);
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:
33 `boost::math::factorial(2);`
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:
38 `boost::math::factorial<double>(2);`
40 So that the return type is known.
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`!
45 The source code `static_assert` and comment just after the will be:
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.
59 T factorial(unsigned i);
61 template <class T, class ``__Policy``>
62 T factorial(unsigned i, const ``__Policy``&);
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.
71 If [^i] is so large that the result can not be represented in type T, then
72 calls __overflow_error.
75 T unchecked_factorial(unsigned i);
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.
88 static const unsigned value = X;
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.
98 For arguments smaller than `max_factorial<T>::value`
100 correctly rounded. For larger arguments the accuracy will be the same
105 Basic sanity checks and spot values to verify the data tables:
106 the main tests for the __tgamma function handle those cases already.
110 The factorial function is table driven for small arguments, and is
111 implemented in terms of __tgamma for larger arguments.
115 [section:sf_double_factorial Double Factorial]
118 #include <boost/math/special_functions/factorials.hpp>
121 namespace boost{ namespace math{
124 T double_factorial(unsigned i);
126 template <class T, class ``__Policy``>
127 T double_factorial(unsigned i, const ``__Policy``&);
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.
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:
143 `boost::math::double_factorial(2);`
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:
148 `boost::math::double_factorial<double>(2);`
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!
153 The source code `static_assert` and comment just after the will be:
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.
166 [note The argument to `double_factorial` is type `unsigned` even though technically -1!! is defined.]
170 The implementation uses a trivial adaptation of
171 the factorial function, so error rates should be no more than a couple
176 The spot tests for the double factorial use data
177 generated by functions.wolfram.com.
181 The double factorial is implemented in terms of the factorial and gamma
182 functions using the relations:
184 (2n)!! = 2[super n ] * n!
186 (2n+1)!! = (2n+1)! / (2[super n ] n!)
190 (2n-1)!! = [Gamma]((2n+1)/2) * 2[super n ] / sqrt(pi)
194 [section:sf_rising_factorial Rising Factorial]
197 #include <boost/math/special_functions/factorials.hpp>
200 namespace boost{ namespace math{
203 ``__sf_result`` rising_factorial(T x, int i);
205 template <class T, class ``__Policy``>
206 ``__sf_result`` rising_factorial(T x, int i, const ``__Policy``&);
210 Returns the rising factorial of /x/ and /i/:
212 rising_factorial(x, i) = [Gamma](x + i) / [Gamma](x);
216 rising_factorial(x, i) = x(x+1)(x+2)(x+3)...(x+i-1)
218 Note that both /x/ and /i/ can be negative as well as positive.
222 May return the result of __overflow_error if the result is too large
223 to represent in type T.
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
231 The accuracy will be the same as
232 the __tgamma_delta_ratio function.
236 The spot tests for the rising factorials use data generated
237 by functions.wolfram.com.
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.
247 [section:sf_falling_factorial Falling Factorial]
250 #include <boost/math/special_functions/factorials.hpp>
253 namespace boost{ namespace math{
256 ``__sf_result`` falling_factorial(T x, unsigned i);
258 template <class T, class ``__Policy``>
259 ``__sf_result`` falling_factorial(T x, unsigned i, const ``__Policy``&);
263 Returns the falling factorial of /x/ and /i/:
265 falling_factorial(x, i) = x(x-1)(x-2)(x-3)...(x-i+1)
267 Note that this function is only defined for positive /i/, hence the
268 `unsigned` second argument. Argument /x/ can be either positive or
273 May return the result of __overflow_error if the result is too large
274 to represent in type T.
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
282 The accuracy will be the same as
283 the __tgamma_delta_ratio function.
287 The spot tests for the falling factorials use data generated by
288 functions.wolfram.com.
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.
298 [section:sf_binomial Binomial Coefficients]
301 #include <boost/math/special_functions/binomial.hpp>
304 namespace boost{ namespace math{
307 T binomial_coefficient(unsigned n, unsigned k);
309 template <class T, class ``__Policy``>
310 T binomial_coefficient(unsigned n, unsigned k, const ``__Policy``&);
314 Returns the binomial coefficient: [sub n]C[sub k].
320 May return the result of __overflow_error if the result is too large
321 to represent in type T.
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:
327 `boost::math::binomial_coefficient(10, 2);`
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:
332 `boost::math::binomial_coefficient<double>(10, 2);`
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!
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.
346 The spot tests for the binomial coefficients use data
347 generated by functions.wolfram.com.
351 Binomial coefficients are calculated using table lookup of factorials
352 where possible using:
354 [sub n]C[sub k] = n! / (k!(n-k)!)
356 Otherwise it is implemented in terms of the beta function using the relations:
358 [sub n]C[sub k] = 1 / (k * __beta(k, n-k+1))
362 [sub n]C[sub k] = 1 / ((n-k) * __beta(k+1, n-k))
367 [endsect][/section:factorials Factorials]
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).