[section:factorials Factorials and Binomial Coefficients] [section:sf_factorial Factorial] [h4 Synopsis] `` #include `` namespace boost{ namespace math{ template T factorial(unsigned i); template T factorial(unsigned i, const ``__Policy``&); template constexpr T unchecked_factorial(unsigned i); template 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(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::value); // factorial(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(factorial(n)); // See factorial documentation for more detail. `` ] template T factorial(unsigned i); template T factorial(unsigned i, const ``__Policy``&); Returns [^i!]. [optional_policy] For [^i <= max_factorial::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 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::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 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::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 `` namespace boost{ namespace math{ template T double_factorial(unsigned i); template 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(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::value); // factorial(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(factorial(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 `` namespace boost{ namespace math{ template ``__sf_result`` rising_factorial(T x, int i); template ``__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 `` namespace boost{ namespace math{ template ``__sf_result`` falling_factorial(T x, unsigned i); template ``__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 `` namespace boost{ namespace math{ template T binomial_coefficient(unsigned n, unsigned k); template 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(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). ]