Code-Eli  0.3.6
binomial_coefficient.hpp
Go to the documentation of this file.
1 /*********************************************************************************
2 * Copyright (c) 2013 David D. Marshall <ddmarsha@calpoly.edu>
3 *
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
8 *
9 * Contributors:
10 * David D. Marshall - initial code and implementation
11 ********************************************************************************/
12 
13 #ifndef eli_mutil_dm_binomial_coef_hpp
14 #define eli_mutil_dm_binomial_coef_hpp
15 
16 #include "eli/code_eli.hpp"
17 
18 namespace eli
19 {
20  namespace mutil
21  {
22  namespace dm
23  {
24  template<typename data__, typename natural__>
25  void n_choose_k(data__ &v, natural__ n, natural__ k)
26  {
27  natural__ i;
28 
29  if (n<k)
30  {
31  assert(false);
32  v = -1;
33  return;
34  }
35  if (n==k)
36  {
37  v = 1;
38  return;
39  }
40 
41  // use symmetry property to get smaller term
42  if (k>n-k)
43  k=n-k;
44 
45  v=1;
46  for (i=1; i<=k; ++i)
47  {
48  // try and keep from overflowing integral data types
49  if (static_cast<data__>(i)>v)
50  {
51  v*=n-k+i;
52  v/=i;
53  }
54  else
55  {
56  v/=i;
57  v*=n-k+i;
58  }
59  }
60  }
61 
62  template<typename data__, typename natural__>
63  void binomial_coefficient(data__ &v, const data__ &n, natural__ k)
64  {
65  natural__ i;
66 
67  if (n==k)
68  {
69  v = 1;
70  return;
71  }
72 
73  v=1;
74  for (i=1; i<=k; ++i)
75  {
76  v*=n-k+i;
77  v/=i;
78  }
79  }
80 
81  template<typename data__, typename natural__>
82  void binomial_coefficient(data__ &v, natural__ n, natural__ k)
83  {
84  binomial_coefficient(v, static_cast<data__>(n), k);
85  }
86  }
87  }
88 }
89 
90 #endif
Definition: math.hpp:20
void n_choose_k(data__ &v, natural__ n, natural__ k)
Definition: binomial_coefficient.hpp:25
void binomial_coefficient(data__ &v, const data__ &n, natural__ k)
Definition: binomial_coefficient.hpp:63