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