generic-library/boost
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
boost/libs/math/doc/html/math_toolkit/internals/agm.html
Edouard DUPIN d0115b733d [DEV] add v1.76.0
2021-10-05 21:37:46 +02:00

137 lines
13 KiB
HTML
Raw Permalink Blame History

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Arithmetic-Geometric Mean</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Math Toolkit 3.0.0">
<link rel="up" href="../internals.html" title="Internal tools">
<link rel="prev" href="series_evaluation.html" title="Series Evaluation">
<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="series_evaluation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.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">
<div class="titlepage"><div><div><h3 class="title">
<a name="math_toolkit.internals.agm"></a><a class="link" href="agm.html" title="Arithmetic-Geometric Mean">Arithmetic-Geometric Mean</a>
</h3></div></div></div>
<h5>
<a name="math_toolkit.internals.agm.h0"></a>
<span class="phrase"><a name="math_toolkit.internals.agm.synopsis"></a></span><a class="link" href="agm.html#math_toolkit.internals.agm.synopsis">Synopsis</a>
</h5>
<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">agm</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="keyword">namespace</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="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Real</span><span class="special">&gt;</span>
<span class="identifier">Real</span> <span class="identifier">agm</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">a0</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">g0</span><span class="special">);</span>
<span class="special">}</span> <span class="comment">// namespaces</span>
</pre>
<p>
The function <code class="computeroutput"><span class="identifier">agm</span></code> produces
the limiting value of the sequence
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/agm_sequence.svg" width="526" height="36"></object></span>
</p>
<p>
A basic usage is
</p>
<pre class="programlisting"><span class="keyword">double</span> <span class="identifier">G</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">tools</span><span class="special">::</span><span class="identifier">agm</span><span class="special">(</span><span class="identifier">sqrt</span><span class="special">(</span><span class="number">2.0</span><span class="special">),</span> <span class="number">1.0</span><span class="special">);</span>
</pre>
<p>
The AGM inequality
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/agm_sequence.svg" width="526" height="36"></object></span>
</p>
<p>
shows that
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/agm_bound.svg" width="249" height="18"></object></span>
</p>
<p>
We use this condition internally to measure convergence; however, there is
no need to worry about putting arguments in the correct order since we extend
<code class="computeroutput"><span class="identifier">agm</span></code> to a symmetric function
by definition. Both arguments must be non-negative, as the sequence becomes
complex for negative arguments. (We have not implemented the complex-valued
AGM sequence.) The function <code class="computeroutput"><span class="identifier">agm</span></code>
is "essentially" one-dimensional, as the scale invariance <code class="computeroutput"><span class="identifier">agm</span><span class="special">(</span><span class="identifier">k</span><span class="special">*</span><span class="identifier">x</span><span class="special">,</span>
<span class="identifier">k</span><span class="special">*</span><span class="identifier">y</span><span class="special">)</span> <span class="special">==</span>
<span class="identifier">k</span><span class="special">*</span><span class="identifier">agm</span><span class="special">(</span><span class="identifier">x</span><span class="special">,</span><span class="identifier">y</span><span class="special">)</span></code>
always allows us to take one argument to be unity. The following ULP plot
has been generated with the function <code class="computeroutput"><span class="identifier">agm</span><span class="special">(</span><span class="identifier">x</span><span class="special">,</span>
<span class="identifier">Real</span><span class="special">(</span><span class="number">1</span><span class="special">))</span></code>:
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../../graphs/agm_ulps_plot.svg"></object></span>
</p>
<p>
The graph above shows an ulps plot of the Boost implementation of <code class="computeroutput"><span class="identifier">agm</span><span class="special">(</span><span class="identifier">x</span><span class="special">,</span> <span class="identifier">Real</span><span class="special">(</span><span class="number">1</span><span class="special">))</span></code>.
An ~2 ULP bound is to be expected.
</p>
<p>
A google benchmark for various types is available in <code class="computeroutput"><span class="identifier">boost</span><span class="special">/</span><span class="identifier">libs</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">reporting</span><span class="special">/</span><span class="identifier">performance</span><span class="special">/</span><span class="identifier">test_agm</span><span class="special">.</span><span class="identifier">cpp</span></code>; some
results on a consumer laptop are provided for convenience:
</p>
<pre class="programlisting"><span class="identifier">Run</span> <span class="identifier">on</span> <span class="special">(</span><span class="number">16</span> <span class="identifier">X</span> <span class="number">2300</span> <span class="identifier">MHz</span> <span class="identifier">CPU</span> <span class="identifier">s</span><span class="special">)</span>
<span class="identifier">CPU</span> <span class="identifier">Caches</span><span class="special">:</span>
<span class="identifier">L1</span> <span class="identifier">Data</span> <span class="number">32</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x8</span><span class="special">)</span>
<span class="identifier">L1</span> <span class="identifier">Instruction</span> <span class="number">32</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x8</span><span class="special">)</span>
<span class="identifier">L2</span> <span class="identifier">Unified</span> <span class="number">262</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x8</span><span class="special">)</span>
<span class="identifier">L3</span> <span class="identifier">Unified</span> <span class="number">16777</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x1</span><span class="special">)</span>
<span class="identifier">Load</span> <span class="identifier">Average</span><span class="special">:</span> <span class="number">2.02</span><span class="special">,</span> <span class="number">2.14</span><span class="special">,</span> <span class="number">2.00</span>
<span class="special">-------------------------------------------------------------------------------</span>
<span class="identifier">Benchmark</span> <span class="identifier">Time</span> <span class="identifier">CPU</span> <span class="identifier">Iterations</span>
<span class="special">-------------------------------------------------------------------------------</span>
<span class="identifier">AGM</span><span class="special">&lt;</span><span class="keyword">float</span><span class="special">&gt;</span> <span class="number">8.52</span> <span class="identifier">ns</span> <span class="number">8.51</span> <span class="identifier">ns</span> <span class="number">59654685</span>
<span class="identifier">AGM</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;</span> <span class="number">13.5</span> <span class="identifier">ns</span> <span class="number">13.5</span> <span class="identifier">ns</span> <span class="number">51709746</span>
<span class="identifier">AGM</span><span class="special">&lt;</span><span class="keyword">long</span> <span class="keyword">double</span><span class="special">&gt;</span> <span class="number">30.6</span> <span class="identifier">ns</span> <span class="number">30.6</span> <span class="identifier">ns</span> <span class="number">18745247</span>
<span class="identifier">AGM</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">multiprecision</span><span class="special">::</span><span class="identifier">float128</span><span class="special">&gt;</span> <span class="number">2332</span> <span class="identifier">ns</span> <span class="number">2332</span> <span class="identifier">ns</span> <span class="number">299303</span>
</pre>
<p>
If any inputs are NaNs, the result is a NaN. If any inputs are +∞, the
result is +∞, unless the other argument fails NaN or negative validation.
</p>
<h5>
<a name="math_toolkit.internals.agm.h1"></a>
<span class="phrase"><a name="math_toolkit.internals.agm.references"></a></span><a class="link" href="agm.html#math_toolkit.internals.agm.references">References</a>
</h5>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
Steven R. Finch. <span class="emphasis"><em>Mathematical Constants</em></span> Cambridge,
2003.
</li></ul></div>
</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-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
Walker and Xiaogang Zhang<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="series_evaluation.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.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>
Reference in New Issue View Git Blame Copy Permalink