Google Git
Sign in
nest-open-source / nest-learning-thermostat / 5.0 / boost / 317601cb979f96545d0e892ce7cfdf59f676ee0a / . / boost_1_45_0 / libs / math / doc / sf_and_dist / html / math_toolkit / toolkit / internals1 / series_evaluation.html
blob: 59e312c16be7b16fec6511d7c7f6f40e4acb699d [file] [log] [blame]
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Series Evaluation</title>
<link rel="stylesheet" href="../../../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.74.0">
<link rel="home" href="../../../index.html" title="Math Toolkit">
<link rel="up" href="../internals1.html" title="Reused Utilities">
<link rel="prev" href="constants.html" title="Numeric Constants">
<link rel="next" href="cf.html" title="Continued Fraction Evaluation">
</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="constants.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals1.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="cf.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section" lang="en">
<div class="titlepage"><div><div><h4 class="title">
<a name="math_toolkit.toolkit.internals1.series_evaluation"></a><a class="link" href="series_evaluation.html" title="Series Evaluation">
Series Evaluation</a>
</h4></div></div></div>
<a name="math_toolkit.toolkit.internals1.series_evaluation.synopsis"></a><h5>
<a name="id1191938"></a>
<a class="link" href="series_evaluation.html#math_toolkit.toolkit.internals1.series_evaluation.synopsis">Synopsis</a>
</h5>
<p>
</p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">series</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</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">namespace</span> <span class="identifier">tools</span><span class="special">{</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">V</span><span class="special">&gt;</span>
<span class="keyword">inline</span> <span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">U</span><span class="special">&amp;</span> <span class="identifier">tolerance</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">V</span><span class="special">&amp;</span> <span class="identifier">init_value</span><span class="special">);</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">V</span><span class="special">&gt;</span>
<span class="keyword">inline</span> <span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">U</span><span class="special">&amp;</span> <span class="identifier">tolerance</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">);</span>
<span class="comment">//
</span><span class="comment">// The following interfaces are now deprecated:
</span><span class="comment">//
</span><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">&gt;</span>
<span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">);</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">&gt;</span>
<span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">);</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">&gt;</span>
<span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">,</span> <span class="identifier">U</span> <span class="identifier">init_value</span><span class="special">);</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">U</span><span class="special">&gt;</span>
<span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">,</span> <span class="identifier">U</span> <span class="identifier">init_value</span><span class="special">);</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">&gt;</span>
<span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">kahan_sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">);</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Functor</span><span class="special">&gt;</span>
<span class="keyword">typename</span> <span class="identifier">Functor</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">kahan_sum_series</span><span class="special">(</span><span class="identifier">Functor</span><span class="special">&amp;</span> <span class="identifier">func</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">bits</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_terms</span><span class="special">);</span>
<span class="special">}}}</span> <span class="comment">// namespaces
</span></pre>
<a name="math_toolkit.toolkit.internals1.series_evaluation.description"></a><h5>
<a name="id1192949"></a>
<a class="link" href="series_evaluation.html#math_toolkit.toolkit.internals1.series_evaluation.description">Description</a>
</h5>
<p>
These algorithms are intended for the <a href="http://en.wikipedia.org/wiki/Series_%28mathematics%29" target="_top">summation
of infinite series</a>.
</p>
<p>
Each of the algorithms takes a nullary-function object as the first argument:
the function object will be repeatedly invoked to pull successive terms
from the series being summed.
</p>
<p>
The second argument is the precision required, summation will stop when
the next term is less than <span class="emphasis"><em>tolerance</em></span> times the result.
The deprecated versions of sum_series take an integer number of bits here
- internally they just convert this to a tolerance and forward the call.
</p>
<p>
The third argument <span class="emphasis"><em>max_terms</em></span> sets an upper limit on
the number of terms of the series to evaluate. In addition, on exit the
function will set <span class="emphasis"><em>max_terms</em></span> to the actual number of
terms of the series that were evaluated: this is particularly useful for
profiling the convergence properties of a new series.
</p>
<p>
The final optional argument <span class="emphasis"><em>init_value</em></span> is the initial
value of the sum to which the terms of the series should be added. This
is useful in two situations:
</p>
<div class="itemizedlist"><ul type="disc">
<li>
Where the first value of the series has a different formula to successive
terms. In this case the first value in the series can be passed as
the last argument and the logic of the function object can then be
simplified to return subsequent terms.
</li>
<li>
Where the series is being added (or subtracted) from some other value:
termination of the series will likely occur much more rapidly if that
other value is passed as the last argument. For example, there are
several functions that can be expressed as <span class="emphasis"><em>1 - S(z)</em></span>
where S(z) is an infinite series. In this case, pass -1 as the last
argument and then negate the result of the summation to get the result
of <span class="emphasis"><em>1 - S(z)</em></span>.
</li>
</ul></div>
<p>
The two <span class="emphasis"><em>kahan_sum_series</em></span> variants of these algorithms
maintain a carry term that corrects for roundoff error during summation.
They are inspired by the <a href="http://en.wikipedia.org/wiki/Kahan_Summation_Algorithm" target="_top"><span class="emphasis"><em>Kahan
Summation Formula</em></span></a> that appears in <a href="http://docs.sun.com/source/806-3568/ncg_goldberg.html" target="_top">What
Every Computer Scientist Should Know About Floating-Point Arithmetic</a>.
However, it should be pointed out that there are very few series that require
summation in this way.
</p>
<a name="math_toolkit.toolkit.internals1.series_evaluation.example"></a><h5>
<a name="id1193048"></a>
<a class="link" href="series_evaluation.html#math_toolkit.toolkit.internals1.series_evaluation.example">Example</a>
</h5>
<p>
Let's suppose we want to implement <span class="emphasis"><em>log(1+x)</em></span> via its
infinite series,
</p>
<p>
<span class="inlinemediaobject"><img src="../../../../equations/log1pseries.png"></span>
</p>
<p>
We begin by writing a small function object to return successive terms
of the series:
</p>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="keyword">struct</span> <span class="identifier">log1p_series</span>
<span class="special">{</span>
<span class="comment">// we must define a result_type typedef:
</span> <span class="keyword">typedef</span> <span class="identifier">T</span> <span class="identifier">result_type</span><span class="special">;</span>
<span class="identifier">log1p_series</span><span class="special">(</span><span class="identifier">T</span> <span class="identifier">x</span><span class="special">)</span>
<span class="special">:</span> <span class="identifier">k</span><span class="special">(</span><span class="number">0</span><span class="special">),</span> <span class="identifier">m_mult</span><span class="special">(-</span><span class="identifier">x</span><span class="special">),</span> <span class="identifier">m_prod</span><span class="special">(-</span><span class="number">1</span><span class="special">){}</span>
<span class="identifier">T</span> <span class="keyword">operator</span><span class="special">()()</span>
<span class="special">{</span>
<span class="comment">// This is the function operator invoked by the summation
</span> <span class="comment">// algorithm, the first call to this operator should return
</span> <span class="comment">// the first term of the series, the second call the second
</span> <span class="comment">// term and so on.
</span> <span class="identifier">m_prod</span> <span class="special">*=</span> <span class="identifier">m_mult</span><span class="special">;</span>
<span class="keyword">return</span> <span class="identifier">m_prod</span> <span class="special">/</span> <span class="special">++</span><span class="identifier">k</span><span class="special">;</span>
<span class="special">}</span>
<span class="keyword">private</span><span class="special">:</span>
<span class="keyword">int</span> <span class="identifier">k</span><span class="special">;</span>
<span class="keyword">const</span> <span class="identifier">T</span> <span class="identifier">m_mult</span><span class="special">;</span>
<span class="identifier">T</span> <span class="identifier">m_prod</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
Implementing log(1+x) is now fairly trivial:
</p>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">log1p</span><span class="special">(</span><span class="identifier">T</span> <span class="identifier">x</span><span class="special">)</span>
<span class="special">{</span>
<span class="comment">// We really should add some error checking on x here!
</span> <span class="identifier">assert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">fabs</span><span class="special">(</span><span class="identifier">x</span><span class="special">)</span> <span class="special">&lt;</span> <span class="number">1</span><span class="special">);</span>
<span class="comment">// Construct the series functor:
</span> <span class="identifier">log1p_series</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="identifier">s</span><span class="special">(</span><span class="identifier">x</span><span class="special">);</span>
<span class="comment">// Set a limit on how many iterations we permit:
</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span> <span class="identifier">max_iter</span> <span class="special">=</span> <span class="number">1000</span><span class="special">;</span>
<span class="comment">// Add it up, with enough precision for full machine precision:
</span> <span class="keyword">return</span> <span class="identifier">tools</span><span class="special">::</span><span class="identifier">sum_series</span><span class="special">(</span><span class="identifier">s</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;::</span><span class="identifier">epsilon</span><span class="special">(),</span> <span class="identifier">max_iter</span><span class="special">);</span>
<span class="special">}</span>
</pre>
</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 &#169; 2006 , 2007, 2008, 2009, 2010 John Maddock, Paul A. Bristow,
Hubert Holin, Xiaogang Zhang, Bruno Lalande, Johan R&#229;de, Gautam Sewani and
Thijs van den Berg<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="constants.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals1.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="cf.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>