123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370 |
- [section:factorials Factorials and Binomial Coefficients]
- [section:sf_factorial Factorial]
- [h4 Synopsis]
- ``
- #include <boost/math/special_functions/factorials.hpp>
- ``
- namespace boost{ namespace math{
-
- template <class T>
- T factorial(unsigned i);
-
- template <class T, class ``__Policy``>
- T factorial(unsigned i, const ``__Policy``&);
-
- template <class T>
- constexpr T unchecked_factorial(unsigned i);
-
- template <class T>
- struct max_factorial;
- }} // namespaces
- [h4 Description]
- [important
- The functions described below are templates where the template argument T CANNOT be deduced from the
- arguments passed to the function. Therefore if you write something like:
- `boost::math::factorial(2);`
- You will get a (perhaps perplexing) compiler error, ususally indicating that there is no such function to be found.
- Instead you need to specify the return type explicity and write:
- `boost::math::factorial<double>(2);`
- So that the return type is known.
- Furthermore, the template argument must be a real-valued type such as `float` or `double`
- and not an integer type - that would overflow far too easily for quite small values of parameter `i`!
- The source code `static_assert` and comment just after the will be:
- ``
- BOOST_STATIC_ASSERT(!boost::is_integral<T>::value);
- // factorial<unsigned int>(n) is not implemented
- // because it would overflow integral type T for too small n
- // to be useful. Use instead a floating-point type,
- // and convert to an unsigned type if essential, for example:
- // unsigned int nfac = static_cast<unsigned int>(factorial<double>(n));
- // See factorial documentation for more detail.
- ``
- ]
- template <class T>
- T factorial(unsigned i);
- template <class T, class ``__Policy``>
- T factorial(unsigned i, const ``__Policy``&);
- Returns [^i!].
- [optional_policy]
- For [^i <= max_factorial<T>::value] this is implemented by table lookup,
- for larger values of [^i], this function is implemented in terms of __tgamma.
- If [^i] is so large that the result can not be represented in type T, then
- calls __overflow_error.
- template <class T>
- constexpr T unchecked_factorial(unsigned i);
- Returns [^i!].
- Internally this function performs table lookup of the result. Further it performs
- no range checking on the value of i: it is up to the caller to ensure
- that [^i <= max_factorial<T>::value]. This function is intended to be used
- inside inner loops that require fast table lookup of factorials, but requires
- care to ensure that argument [^i] never grows too large.
- template <class T>
- struct max_factorial
- {
- static const unsigned value = X;
- };
- This traits class defines the largest value that can be passed to
- [^unchecked_factorial]. The member `value` can be used where integral
- constant expressions are required: for example to define the size of
- further tables that depend on the factorials.
- This function is `constexpr` only if the compiler supports C++14 constexpr functions.
- [h4 Accuracy]
- For arguments smaller than `max_factorial<T>::value`
- the result should be
- correctly rounded. For larger arguments the accuracy will be the same
- as for __tgamma.
- [h4 Testing]
- Basic sanity checks and spot values to verify the data tables:
- the main tests for the __tgamma function handle those cases already.
- [h4 Implementation]
- The factorial function is table driven for small arguments, and is
- implemented in terms of __tgamma for larger arguments.
- [endsect] [/section:sf_factorial Factorial]
- [section:sf_double_factorial Double Factorial]
- ``
- #include <boost/math/special_functions/factorials.hpp>
- ``
- namespace boost{ namespace math{
-
- template <class T>
- T double_factorial(unsigned i);
-
- template <class T, class ``__Policy``>
- T double_factorial(unsigned i, const ``__Policy``&);
-
- }} // namespaces
- Returns [^i!!].
- [optional_policy]
- May return the result of __overflow_error if the result is too large
- to represent in type T. The implementation is designed to be optimised
- for small /i/ where table lookup of i! is possible.
- [important
- The functions described above are templates where the template argument T can not be deduced from the
- arguments passed to the function. Therefore if you write something like:
- `boost::math::double_factorial(2);`
- You will get a (possibly perplexing) compiler error, ususally indicating that there is no such function to be found. Instead you need to specifiy
- the return type explicity and write:
- `boost::math::double_factorial<double>(2);`
- So that the return type is known. Further, the template argument must be a real-valued type such as `float` or `double`
- and not an integer type - that would overflow far too easily!
- The source code `static_assert` and comment just after the will be:
- ``
- BOOST_STATIC_ASSERT(!boost::is_integral<T>::value);
- // factorial<unsigned int>(n) is not implemented
- // because it would overflow integral type T for too small n
- // to be useful. Use instead a floating-point type,
- // and convert to an unsigned type if essential, for example:
- // unsigned int nfac = static_cast<unsigned int>(factorial<double>(n));
- // See factorial documentation for more detail.
- ``
- ]
- [note The argument to `double_factorial` is type `unsigned` even though technically -1!! is defined.]
- [h4 Accuracy]
- The implementation uses a trivial adaptation of
- the factorial function, so error rates should be no more than a couple
- of epsilon higher.
- [h4 Testing]
- The spot tests for the double factorial use data generated by __WolframAlpha.
- [h4 Implementation]
- The double factorial is implemented in terms of the factorial and gamma
- functions using the relations:
- [expression ['(2n)!! = 2[super n ] * n!]]
- [expression ['(2n+1)!! = (2n+1)! / (2[super n ] n!)]]
- and
- [expression ['(2n-1)!! = [Gamma]((2n+1)/2) * 2[super n ] / sqrt(pi)]]
- [endsect] [/section:sf_double_factorial Double Factorial]
- [section:sf_rising_factorial Rising Factorial]
- ``
- #include <boost/math/special_functions/factorials.hpp>
- ``
- namespace boost{ namespace math{
-
- template <class T>
- ``__sf_result`` rising_factorial(T x, int i);
-
- template <class T, class ``__Policy``>
- ``__sf_result`` rising_factorial(T x, int i, const ``__Policy``&);
-
- }} // namespaces
- Returns the rising factorial of /x/ and /i/:
- [expression ['rising_factorial(x, i) = [Gamma](x + i) / [Gamma](x)]]
- or
- [expression ['rising_factorial(x, i) = x(x+1)(x+2)(x+3)...(x+i-1)]]
-
- Note that both /x/ and /i/ can be negative as well as positive.
- [optional_policy]
- May return the result of __overflow_error if the result is too large
- to represent in type T.
- The return type of these functions is computed using the __arg_promotion_rules:
- the type of the result is `double` if T is an integer type, otherwise the type
- of the result is T.
- [h4 Accuracy]
- The accuracy will be the same as
- the __tgamma_delta_ratio function.
- [h4 Testing]
- The spot tests for the rising factorials use data generated by __Wolfram_functions.
- [h4 Implementation]
- Rising and factorials are implemented as ratios of gamma functions using __tgamma_delta_ratio.
- Optimisations for small integer arguments are handled internally by that function.
- [endsect] [/section:sf_rising_factorial Rising Factorial]
- [section:sf_falling_factorial Falling Factorial]
- ``
- #include <boost/math/special_functions/factorials.hpp>
- ``
- namespace boost{ namespace math{
-
- template <class T>
- ``__sf_result`` falling_factorial(T x, unsigned i);
-
- template <class T, class ``__Policy``>
- ``__sf_result`` falling_factorial(T x, unsigned i, const ``__Policy``&);
-
- }} // namespaces
- Returns the falling factorial of /x/ and /i/:
- [expression ['falling_factorial(x, i) = x(x-1)(x-2)(x-3)...(x-i+1)]]
-
- Note that this function is only defined for positive /i/, hence the
- `unsigned` second argument. Argument /x/ can be either positive or
- negative however.
- [optional_policy]
- May return the result of __overflow_error if the result is too large
- to represent in type T.
- The return type of these functions is computed using the __arg_promotion_rules:
- the type of the result is `double` if T is an integer type, otherwise the type
- of the result is T.
- [h4 Accuracy]
- The accuracy will be the same as
- the __tgamma_delta_ratio function.
- [h4 Testing]
- The spot tests for the falling factorials use data generated by __Wolfram_functions.
- [h4 Implementation]
- Rising and falling factorials are implemented as ratios of gamma functions
- using __tgamma_delta_ratio. Optimisations for
- small integer arguments are handled internally by that function.
- [endsect] [/section:sf_falling_factorial Falling Factorial]
- [section:sf_binomial Binomial Coefficients]
- ``
- #include <boost/math/special_functions/binomial.hpp>
- ``
- namespace boost{ namespace math{
-
- template <class T>
- T binomial_coefficient(unsigned n, unsigned k);
- template <class T, class ``__Policy``>
- T binomial_coefficient(unsigned n, unsigned k, const ``__Policy``&);
- }} // namespaces
- Returns the binomial coefficient: [sub n]C[sub k].
- Requires k <= n.
- [optional_policy]
- May return the result of __overflow_error if the result is too large
- to represent in type T.
-
- [important
- The functions described above are templates where the template argument `T` can not be deduced from the
- arguments passed to the function. Therefore if you write something like:
- `boost::math::binomial_coefficient(10, 2);`
- You will get a compiler error, ususally indicating that there is no such function to be found. Instead you need to specifiy
- the return type explicity and write:
- `boost::math::binomial_coefficient<double>(10, 2);`
- So that the return type is known. Further, the template argument must be a real-valued type such as `float` or `double`
- and not an integer type - that would overflow far too easily!
- ]
- [h4 Accuracy]
- The accuracy will be the same as for the
- factorials for small arguments (i.e. no more than one or two epsilon),
- and the __beta function for larger arguments.
- [h4 Testing]
- The spot tests for the binomial coefficients use data generated by __WolframAlpha.
- [h4 Implementation]
- Binomial coefficients are calculated using table lookup of factorials
- where possible using:
- [expression ['[sub n]C[sub k] = n! / (k!(n-k)!)]]
- Otherwise it is implemented in terms of the beta function using the relations:
- [expression ['[sub n]C[sub k] = 1 / (k * __beta(k, n-k+1))]]
- and
- [expression ['[sub n]C[sub k] = 1 / ((n-k) * __beta(k+1, n-k))]]
- [endsect] [/section:sf_binomial Binomial Coefficients]
- [endsect] [/section:factorials Factorials]
- [/
- Copyright 2006, 2010 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).
- ]
|