1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Binomial Coefficients</title>
<link rel="stylesheet" href="../../../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
<link rel="home" href="../../../index.html" title="Math Toolkit">
<link rel="up" href="../factorials.html" title="Factorials and Binomial Coefficients">
<link rel="prev" href="sf_falling_factorial.html" title="Falling Factorial">
<link rel="next" href="../sf_beta.html" title="Beta Functions">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="sf_falling_factorial.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../factorials.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_beta.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section math_toolkit_special_factorials_sf_binomial">
<div class="titlepage"><div><div><h4 class="title">
<a name="math_toolkit.special.factorials.sf_binomial"></a><a class="link" href="sf_binomial.html" title="Binomial Coefficients">Binomial
Coefficients</a>
</h4></div></div></div>
<p>
</p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">special_functions</span><span class="special">/</span><span class="identifier">binomial</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
</pre>
<p>
</p>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span>
<span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">></span>
<span class="identifier">T</span> <span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">k</span><span class="special">);</span>
<span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <a class="link" href="../../policy.html" title="Policies">Policy</a><span class="special">></span>
<span class="identifier">T</span> <span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">k</span><span class="special">,</span> <span class="keyword">const</span> <a class="link" href="../../policy.html" title="Policies">Policy</a><span class="special">&);</span>
<span class="special">}}</span> <span class="comment">// namespaces</span>
</pre>
<p>
Returns the binomial coefficient: <sub>n</sub>C<sub>k</sub>.
</p>
<p>
Requires k <= n.
</p>
<p>
The final <a class="link" href="../../policy.html" title="Policies">Policy</a> argument is
optional and can be used to control the behaviour of the function: how
it handles errors, what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Policies">policy documentation for more details</a>.
</p>
<p>
May return the result of <a class="link" href="../../main_overview/error_handling.html#overflow_error">overflow_error</a>
if the result is too large to represent in type T.
</p>
<div class="important"><table border="0" summary="Important">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Important]" src="../../../../../../../../doc/src/images/important.png"></td>
<th align="left">Important</th>
</tr>
<tr><td align="left" valign="top">
<p>
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:
</p>
<p>
<code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="number">10</span><span class="special">,</span> <span class="number">2</span><span class="special">);</span></code>
</p>
<p>
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:
</p>
<p>
<code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">binomial_coefficient</span><span class="special"><</span><span class="keyword">double</span><span class="special">>(</span><span class="number">10</span><span class="special">,</span> <span class="number">2</span><span class="special">);</span></code>
</p>
<p>
So that the return type is known. Further, the template argument must
be a real-valued type such as <code class="computeroutput"><span class="keyword">float</span></code>
or <code class="computeroutput"><span class="keyword">double</span></code> and not an integer
type - that would overflow far too easily!
</p>
</td></tr>
</table></div>
<h5>
<a name="math_toolkit.special.factorials.sf_binomial.h0"></a>
<span><a name="math_toolkit.special.factorials.sf_binomial.accuracy"></a></span><a class="link" href="sf_binomial.html#math_toolkit.special.factorials.sf_binomial.accuracy">Accuracy</a>
</h5>
<p>
The accuracy will be the same as for the factorials for small arguments
(i.e. no more than one or two epsilon), and the <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>
function for larger arguments.
</p>
<h5>
<a name="math_toolkit.special.factorials.sf_binomial.h1"></a>
<span><a name="math_toolkit.special.factorials.sf_binomial.testing"></a></span><a class="link" href="sf_binomial.html#math_toolkit.special.factorials.sf_binomial.testing">Testing</a>
</h5>
<p>
The spot tests for the binomial coefficients use data generated by functions.wolfram.com.
</p>
<h5>
<a name="math_toolkit.special.factorials.sf_binomial.h2"></a>
<span><a name="math_toolkit.special.factorials.sf_binomial.implementation"></a></span><a class="link" href="sf_binomial.html#math_toolkit.special.factorials.sf_binomial.implementation">Implementation</a>
</h5>
<p>
Binomial coefficients are calculated using table lookup of factorials where
possible using:
</p>
<p>
<sub>n</sub>C<sub>k</sub> = n! / (k!(n-k)!)
</p>
<p>
Otherwise it is implemented in terms of the beta function using the relations:
</p>
<p>
<sub>n</sub>C<sub>k</sub> = 1 / (k * <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>(k,
n-k+1))
</p>
<p>
and
</p>
<p>
<sub>n</sub>C<sub>k</sub> = 1 / ((n-k) * <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>(k+1,
n-k))
</p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2006-2010 John Maddock, Paul A. Bristow, Hubert Holin, Xiaogang Zhang, Bruno
Lalande, Johan Råde, Gautam Sewani, Thijs van den Berg and Benjamin Sobotta<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="sf_falling_factorial.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../factorials.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_beta.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
