libs/math/doc/sf/factorials.qbk

   1 [section:factorials Factorials and Binomial Coefficients]
   2
   3 [section:sf_factorial Factorial]
   4
   5 [h4 Synopsis]
   6
   7 ``
   8 #include <boost/math/special_functions/factorials.hpp>
   9 ``
  10
  11    namespace boost{ namespace math{
  12
  13    template <class T>
  14    T factorial(unsigned i);
  15
  16    template <class T, class ``__Policy``>
  17    T factorial(unsigned i, const ``__Policy``&);
  18
  19    template <class T>
  20    constexpr T unchecked_factorial(unsigned i);
  21
  22    template <class T>
  23    struct max_factorial;
  24
  25    }} // namespaces
  26
  27 [h4 Description]
  28
  29 [important
  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:
  32
  33    `boost::math::factorial(2);`
  34
  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:
  37
  38    `boost::math::factorial<double>(2);`
  39
  40 So that the return type is known.
  41
  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`!
  44
  45 The source code `static_assert` and comment just after the  will be:
  46
  47 ``
  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.
  55 ``
  56 ]
  57
  58    template <class T>
  59    T factorial(unsigned i);
  60
  61    template <class T, class ``__Policy``>
  62    T factorial(unsigned i, const ``__Policy``&);
  63
  64 Returns [^i!].
  65
  66 [optional_policy]
  67
  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.
  70
  71 If [^i] is so large that the result can not be represented in type T, then
  72 calls __overflow_error.
  73
  74    template <class T>
  75    constexpr T unchecked_factorial(unsigned i);
  76
  77 Returns [^i!].
  78
  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.
  84
  85    template <class T>
  86    struct max_factorial
  87    {
  88       static const unsigned value = X;
  89    };
  90
  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.
  95
  96 This function is `constexpr` only if the compiler supports C++14 constexpr functions.
  97
  98 [h4 Accuracy]
  99
 100 For arguments smaller than `max_factorial<T>::value`
 101 the result should be
 102 correctly rounded.  For larger arguments the accuracy will be the same
 103 as for __tgamma.
 104
 105 [h4 Testing]
 106
 107 Basic sanity checks and spot values to verify the data tables:
 108 the main tests for the __tgamma function handle those cases already.
 109
 110 [h4 Implementation]
 111
 112 The factorial function is table driven for small arguments, and is
 113 implemented in terms of __tgamma for larger arguments.
 114
 115 [endsect] [/section:sf_factorial Factorial]
 116
 117 [section:sf_double_factorial Double Factorial]
 118
 119 ``
 120 #include <boost/math/special_functions/factorials.hpp>
 121 ``
 122
 123    namespace boost{ namespace math{
 124
 125    template <class T>
 126    T double_factorial(unsigned i);
 127
 128    template <class T, class ``__Policy``>
 129    T double_factorial(unsigned i, const ``__Policy``&);
 130
 131    }} // namespaces
 132
 133 Returns [^i!!].
 134
 135 [optional_policy]
 136
 137 May return the result of __overflow_error if the result is too large
 138 to represent in type T.  The implementation is designed to be optimised
 139 for small /i/ where table lookup of i! is possible.
 140
 141 [important
 142 The functions described above are templates where the template argument T can not be deduced from the
 143 arguments passed to the function.  Therefore if you write something like:
 144
 145    `boost::math::double_factorial(2);`
 146
 147 You will get a (possibly perplexing) compiler error, ususally indicating that there is no such function to be found.  Instead you need to specifiy
 148 the return type explicity and write:
 149
 150    `boost::math::double_factorial<double>(2);`
 151
 152 So that the return type is known.  Further, the template argument must be a real-valued type such as `float` or `double`
 153 and not an integer type - that would overflow far too easily!
 154
 155 The source code `static_assert` and comment just after the  will be:
 156
 157 ``
 158    BOOST_STATIC_ASSERT(!boost::is_integral<T>::value);
 159    // factorial<unsigned int>(n) is not implemented
 160    // because it would overflow integral type T for too small n
 161    // to be useful. Use instead a floating-point type,
 162    // and convert to an unsigned type if essential, for example:
 163    // unsigned int nfac = static_cast<unsigned int>(factorial<double>(n));
 164    // See factorial documentation for more detail.
 165 ``
 166 ]
 167
 168 [note The argument to `double_factorial` is type `unsigned` even though technically -1!! is defined.]
 169
 170 [h4 Accuracy]
 171
 172 The implementation uses a trivial adaptation of
 173 the factorial function, so error rates should be no more than a couple
 174 of epsilon higher.
 175
 176 [h4 Testing]
 177
 178 The spot tests for the double factorial use data generated by __WolframAlpha.
 179
 180 [h4 Implementation]
 181
 182 The double factorial is implemented in terms of the factorial and gamma
 183 functions using the relations:
 184
 185 [expression ['(2n)!! = 2[super n ] * n!]]
 186
 187 [expression ['(2n+1)!! = (2n+1)! / (2[super n ] n!)]]
 188
 189 and
 190
 191 [expression ['(2n-1)!! = [Gamma]((2n+1)/2) * 2[super n ] / sqrt(pi)]]
 192
 193 [endsect] [/section:sf_double_factorial Double Factorial]
 194
 195 [section:sf_rising_factorial Rising Factorial]
 196
 197 ``
 198 #include <boost/math/special_functions/factorials.hpp>
 199 ``
 200
 201    namespace boost{ namespace math{
 202
 203    template <class T>
 204    ``__sf_result`` rising_factorial(T x, int i);
 205
 206    template <class T, class ``__Policy``>
 207    ``__sf_result`` rising_factorial(T x, int i, const ``__Policy``&);
 208
 209    }} // namespaces
 210
 211 Returns the rising factorial of /x/ and /i/:
 212
 213 [expression ['rising_factorial(x, i) = [Gamma](x + i) / [Gamma](x)]]
 214
 215 or
 216
 217 [expression ['rising_factorial(x, i) = x(x+1)(x+2)(x+3)...(x+i-1)]]
 218
 219 Note that both /x/ and /i/ can be negative as well as positive.
 220
 221 [optional_policy]
 222
 223 May return the result of __overflow_error if the result is too large
 224 to represent in type T.
 225
 226 The return type of these functions is computed using the __arg_promotion_rules:
 227 the type of the result is `double` if T is an integer type, otherwise the type
 228 of the result is T.
 229
 230 [h4 Accuracy]
 231
 232 The accuracy will be the same as
 233 the __tgamma_delta_ratio function.
 234
 235 [h4 Testing]
 236
 237 The spot tests for the rising factorials use data generated by __Wolfram_functions.
 238
 239 [h4 Implementation]
 240
 241 Rising and factorials are implemented as ratios of gamma functions using __tgamma_delta_ratio.
 242 Optimisations for small integer arguments are handled internally by that function.
 243
 244 [endsect] [/section:sf_rising_factorial Rising Factorial]
 245
 246 [section:sf_falling_factorial Falling Factorial]
 247
 248 ``
 249 #include <boost/math/special_functions/factorials.hpp>
 250 ``
 251
 252    namespace boost{ namespace math{
 253
 254    template <class T>
 255    ``__sf_result`` falling_factorial(T x, unsigned i);
 256
 257    template <class T, class ``__Policy``>
 258    ``__sf_result`` falling_factorial(T x, unsigned i, const ``__Policy``&);
 259
 260    }} // namespaces
 261
 262 Returns the falling factorial of /x/ and /i/:
 263
 264 [expression ['falling_factorial(x, i) = x(x-1)(x-2)(x-3)...(x-i+1)]]
 265
 266 Note that this function is only defined for positive /i/, hence the
 267 `unsigned` second argument.  Argument /x/ can be either positive or
 268 negative however.
 269
 270 [optional_policy]
 271
 272 May return the result of __overflow_error if the result is too large
 273 to represent in type T.
 274
 275 The return type of these functions is computed using the __arg_promotion_rules:
 276 the type of the result is `double` if T is an integer type, otherwise the type
 277 of the result is T.
 278
 279 [h4 Accuracy]
 280
 281 The accuracy will be the same as
 282 the __tgamma_delta_ratio function.
 283
 284 [h4 Testing]
 285
 286 The spot tests for the falling factorials use data generated by __Wolfram_functions.
 287
 288 [h4 Implementation]
 289
 290 Rising and falling factorials are implemented as ratios of gamma functions
 291 using __tgamma_delta_ratio.  Optimisations for
 292 small integer arguments are handled internally by that function.
 293
 294 [endsect] [/section:sf_falling_factorial Falling Factorial]
 295
 296 [section:sf_binomial Binomial Coefficients]
 297
 298 ``
 299 #include <boost/math/special_functions/binomial.hpp>
 300 ``
 301
 302    namespace boost{ namespace math{
 303
 304    template <class T>
 305    T binomial_coefficient(unsigned n, unsigned k);
 306
 307    template <class T, class ``__Policy``>
 308    T binomial_coefficient(unsigned n, unsigned k, const ``__Policy``&);
 309
 310    }} // namespaces
 311
 312 Returns the binomial coefficient: [sub n]C[sub k].
 313
 314 Requires k <= n.
 315
 316 [optional_policy]
 317
 318 May return the result of __overflow_error if the result is too large
 319 to represent in type T.
 320
 321 [important
 322 The functions described above are templates where the template argument `T` can not be deduced from the
 323 arguments passed to the function.  Therefore if you write something like:
 324
 325    `boost::math::binomial_coefficient(10, 2);`
 326
 327 You will get a compiler error, ususally indicating that there is no such function to be found.  Instead you need to specifiy
 328 the return type explicity and write:
 329
 330    `boost::math::binomial_coefficient<double>(10, 2);`
 331
 332 So that the return type is known.  Further, the template argument must be a real-valued type such as `float` or `double`
 333 and not an integer type - that would overflow far too easily!
 334 ]
 335
 336 [h4 Accuracy]
 337
 338 The accuracy will be the same as for the
 339 factorials for small arguments (i.e. no more than one or two epsilon),
 340 and the __beta function for larger arguments.
 341
 342 [h4 Testing]
 343
 344 The spot tests for the binomial coefficients use data generated by __WolframAlpha.
 345
 346 [h4 Implementation]
 347
 348 Binomial coefficients are calculated using table lookup of factorials
 349 where possible using:
 350
 351 [expression ['[sub n]C[sub k] = n! / (k!(n-k)!)]]
 352
 353 Otherwise it is implemented in terms of the beta function using the relations:
 354
 355 [expression ['[sub n]C[sub k] = 1 / (k * __beta(k, n-k+1))]]
 356
 357 and
 358
 359 [expression ['[sub n]C[sub k] = 1 / ((n-k) * __beta(k+1, n-k))]]
 360
 361 [endsect] [/section:sf_binomial Binomial Coefficients]
 362
 363 [endsect] [/section:factorials Factorials]
 364
 365 [/
 366   Copyright 2006, 2010 John Maddock and Paul A. Bristow.
 367   Distributed under the Boost Software License, Version 1.0.
 368   (See accompanying file LICENSE_1_0.txt or copy at
 369   http://www.boost.org/LICENSE_1_0.txt).
 370 ]