| [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> |
| 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 can not be deduced from the |
| arguments passed to the function. Therefore if you write something like: |
| |
| `boost::math::factorial(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::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! |
| ] |
| |
| 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> |
| 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. |
| |
| [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_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 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! |
| ] |
| |
| [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 functions.wolfram.com. |
| |
| [h4 Implementation] |
| |
| The double factorial is implemented in terms of the factorial and gamma |
| functions using the relations: |
| |
| (2n)!! = 2[super n ] * n! |
| |
| (2n+1)!! = (2n+1)! / (2[super n ] n!) |
| |
| and |
| |
| (2n-1)!! = [Gamma]((2n+1)/2) * 2[super n ] / sqrt(pi) |
| |
| [endsect] |
| |
| [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/: |
| |
| rising_factorial(x, i) = [Gamma](x + i) / [Gamma](x); |
| |
| or |
| |
| 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_pomotion_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 functions.wolfram.com. |
| |
| [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] |
| |
| `` |
| #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/: |
| |
| 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_pomotion_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 |
| functions.wolfram.com. |
| |
| [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_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 functions.wolfram.com. |
| |
| [h4 Implementation] |
| |
| Binomial coefficients are calculated using table lookup of factorials |
| where possible using: |
| |
| [sub n]C[sub k] = n! / (k!(n-k)!) |
| |
| Otherwise it is implemented in terms of the beta function using the relations: |
| |
| [sub n]C[sub k] = 1 / (k * __beta(k, n-k+1)) |
| |
| and |
| |
| [sub n]C[sub k] = 1 / ((n-k) * __beta(k+1, n-k)) |
| |
| [endsect] |
| |
| |
| [endsect][/section:factorials Factorials] |
| |
| [/ |
| 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). |
| ] |
| |