factorials.qbk

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

[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]

   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.

[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)
                          
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.
   
[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).
]