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

229 lines
22 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>ULPs Plots</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="../utils.html" title="Chapter 2. Floating Point Utilities">
<link rel="prev" href="cond.html" title="Condition Numbers">
<link rel="next" href="../cstdfloat.html" title="Chapter 3. Specified-width floating-point typedefs">
</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="cond.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../utils.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="../cstdfloat.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="math_toolkit.ulps_plots"></a><a class="link" href="ulps_plots.html" title="ULPs Plots">ULPs Plots</a>
</h2></div></div></div>
<h5>
<a name="math_toolkit.ulps_plots.h0"></a>
<span class="phrase"><a name="math_toolkit.ulps_plots.synopsis"></a></span><a class="link" href="ulps_plots.html#math_toolkit.ulps_plots.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">ulps_plot</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">class</span> <span class="identifier">F</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">PreciseReal</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">CoarseReal</span><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">ulps_plot</span> <span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="identifier">ulps_plot</span><span class="special">(</span><span class="identifier">F</span> <span class="identifier">hi_acc_impl</span><span class="special">,</span> <span class="identifier">CoarseReal</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">CoarseReal</span> <span class="identifier">b</span><span class="special">,</span>
<span class="identifier">size_t</span> <span class="identifier">samples</span> <span class="special">=</span> <span class="number">10000</span><span class="special">,</span> <span class="keyword">bool</span> <span class="identifier">perturb_abscissas</span> <span class="special">=</span> <span class="keyword">false</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">random_seed</span> <span class="special">=</span> <span class="special">-</span><span class="number">1</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Set a clip value to restrict the range of ULP's shown, values outside [-clip,clip]</span>
<span class="comment">// will be shown at the clip boundary and in a different color (red by default):</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">clip</span><span class="special">(</span><span class="identifier">PreciseReal</span> <span class="identifier">clip</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// The width of the SVG:</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">width</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">width</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// The color of the condition number envelope:</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">envelope_color</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">color</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Title:</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">title</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">title</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Background color:</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">background_color</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">background_color</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Font color:</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">font_color</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">font_color</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Sets the color of points which are cropped, or set to an empty</span>
<span class="comment">// string to hide them completely (default is "red"):</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">crop_color</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">font_color</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Set's the color of points where one of the functions returned a NaN,</span>
<span class="comment">// or set to an empty string to hide completely (the default):</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">nan_color</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">font_color</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Show ULP envelope true/false:</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">ulp_envelope</span><span class="special">(</span><span class="keyword">bool</span> <span class="identifier">write_ulp</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// The number of horizontal/vertical lines to draw:</span>
<span class="comment">//</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">horizontal_lines</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">horizontal_lines</span><span class="special">);</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">vertical_lines</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">vertical_lines</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Add a function, and plot color:</span>
<span class="comment">//</span>
<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">G</span><span class="special">&gt;</span>
<span class="identifier">ulps_plot</span><span class="special">&amp;</span> <span class="identifier">add_fn</span><span class="special">(</span><span class="identifier">G</span> <span class="identifier">g</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">color</span> <span class="special">=</span> <span class="string">"steelblue"</span><span class="special">);</span>
<span class="comment">//</span>
<span class="comment">// Write to stream or file:</span>
<span class="comment">//</span>
<span class="keyword">friend</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">&lt;&lt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">fs</span><span class="special">,</span> <span class="identifier">ulps_plot</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">plot</span><span class="special">)</span>
<span class="keyword">void</span> <span class="identifier">write</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="keyword">const</span> <span class="special">&amp;</span> <span class="identifier">filename</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span>
<span class="special">};</span>
<span class="special">}</span> <span class="comment">// namespaces</span>
</pre>
<p>
An ULPs plot measures the accuracy of an implementation of a function implemented
in floating point arithmetic. ULP stands for <span class="emphasis"><em>unit in the last place</em></span>;
i.e., we create a unit system that normalizes the distance between one representable
and the next greater representable to 1.
</p>
<p>
So for example, the ULP distance between <code class="computeroutput"><span class="number">1.0</span></code>
and <code class="computeroutput"><span class="number">1.0</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="keyword">double</span><span class="special">&gt;::</span><span class="identifier">epsilon</span><span class="special">()</span></code>
is 1, the ulp distance between <code class="computeroutput"><span class="number">1.0</span></code>
and <code class="computeroutput"><span class="number">1.0</span> <span class="special">+</span>
<span class="number">2</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="keyword">double</span><span class="special">&gt;::</span><span class="identifier">epsilon</span><span class="special">()</span></code>
is 2. A key concept of this measurement is <span class="emphasis"><em>semi-scale invariance</em></span>:
The ULP distance between <code class="computeroutput"><span class="number">2.0</span></code> and
<code class="computeroutput"><span class="number">2.0</span> <span class="special">+</span>
<span class="number">2</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="keyword">double</span><span class="special">&gt;::</span><span class="identifier">epsilon</span><span class="special">()</span></code>
is 1, not 2.
</p>
<p>
An ULPs plot gives us an idea of how efficiently we are using the floating
point number system we have chosen. To compute a ULP plot, we need a higher
precision implementation; for example we can test a 32 bit floating point implementation
against an 80-bit long double implementation. The higher precision value is
computed in the template type <code class="computeroutput"><span class="identifier">PreciseReal</span></code>,
and the lower precision value is computed in type <code class="computeroutput"><span class="identifier">CoarseReal</span></code>.
For simplicity, we will refer to the result of the higher precision implementation
the exact value, which we will denote by <span class="emphasis"><em>y</em></span>, and the value
computed in lower precision we will denote by ŷ. The ULP distance between
<span class="emphasis"><em>y</em></span> and ŷ is then
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../graphs/ulp_distance.svg" width="49" height="43"></object></span>
</p>
<p>
where μ is the unit roundoff of the <code class="computeroutput"><span class="identifier">CoarseReal</span></code>
type.
</p>
<p>
If every sample in an ULPs plot is bounded by ±½, then we have good evidence
that we have used our floating point number as efficiently as we can possibly
expect: We are getting the correctly rounded result. However, the converse
is not true: If there exists samples that are well above the unit roundoff,
we do not have evidence that the function is poorly implemented. Considering
the <span class="emphasis"><em>y</em></span>=0 case makes this obvious, but another more subtle
issue is at play. Consider that when we evaluate a function <span class="emphasis"><em>f</em></span>,
it is rare that we want to evaluate <span class="emphasis"><em>f</em></span> at a representable
x̂, instead we have an infinite precision value <span class="emphasis"><em>x</em></span> which
must be rounded into x̂ using the floating point rounding model x̂ = x(1+ε),
where |ε|&lt;μ.
</p>
<p>
We can use a first order Taylor series to determine the best accuracy we can
hope for under the assumption that the only source of error is rounding the
abscissa to the nearest to nearest representable:
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../graphs/ulps_and_condition_number.svg" width="611" height="44"></object></span>
</p>
<p>
Hence the condition number of function evaluation provides a natural scale
for evaluating the quality of an implementation of a special function. Since,
in addition, we cannot expect better than half-ULP accuracy, we can create
a <span class="emphasis"><em>ulp envelope</em></span> by taking the maximum of 0.5 and half the
condition number of function evaluation at each point.
</p>
<p>
<span class="inlinemediaobject"><object type="image/svg+xml" data="../../graphs/airy_ai_float.svg"></object></span>
</p>
<p>
The graph shows the ULP accuracy of Boost's implementation of the Airy Ai function.
We see only a few evaluations outside the ULP envelope. Note how the condition
number of function evaluation becomes unbounded at the roots.
</p>
<p>
A minimal working example which reproduces the plot above is given <a href="../../../example/airy_ulps_plot.cpp" target="_top">here</a>.
</p>
<p>
Note that you can compare two different implementations of a single function
by calling <code class="computeroutput"><span class="identifier">add_fn</span></code> multiple
times. This will give you a graphical answer to which one is more accurate.
For example:
</p>
<pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">plot</span> <span class="special">=</span> <span class="identifier">ulps_plot</span><span class="special">&lt;</span><span class="keyword">decltype</span><span class="special">(</span><span class="identifier">f</span><span class="special">),</span> <span class="keyword">long</span> <span class="keyword">double</span><span class="special">,</span> <span class="keyword">float</span><span class="special">&gt;(</span><span class="identifier">f</span><span class="special">,</span> <span class="number">1.0f</span><span class="special">,</span> <span class="number">2.0f</span><span class="special">);</span>
<span class="identifier">plot</span><span class="special">.</span><span class="identifier">add_fn</span><span class="special">(</span><span class="identifier">impl1</span><span class="special">,</span> <span class="string">"steelblue"</span><span class="special">);</span>
<span class="identifier">plot</span><span class="special">.</span><span class="identifier">add_fn</span><span class="special">(</span><span class="identifier">impl2</span><span class="special">,</span> <span class="string">"orange"</span><span class="special">);</span>
</pre>
<p>
Note that the graph is written as an SVG. We use <code class="computeroutput"><span class="identifier">firefox</span>
<span class="identifier">foo</span><span class="special">.</span><span class="identifier">svg</span></code> or <code class="computeroutput"><span class="identifier">open</span>
<span class="special">-</span><span class="identifier">a</span> <span class="identifier">Firefox</span> <span class="identifier">foo</span><span class="special">.</span><span class="identifier">svg</span></code> to display
these files.
</p>
<p>
There is a subtle issue about the "correct" value. Note that if the
function evaluated in <code class="computeroutput"><span class="identifier">PreciseReal</span></code>
is not accurate, the plot is worthless. But just how accurate it needs to be
is more difficult to determine. We recommend starting with at least <code class="computeroutput"><span class="keyword">long</span> <span class="keyword">double</span></code>
to test <code class="computeroutput"><span class="keyword">float</span></code> precision, and
<code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">multiprecision</span><span class="special">::</span><span class="identifier">float128</span></code> to test <code class="computeroutput"><span class="keyword">double</span></code>
precision values.
</p>
<h4>
<a name="math_toolkit.ulps_plots.h1"></a>
<span class="phrase"><a name="math_toolkit.ulps_plots.references"></a></span><a class="link" href="ulps_plots.html#math_toolkit.ulps_plots.references">References</a>
</h4>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
Cleve Moler. <span class="emphasis"><em>Ulps Plots Reveal Math Function Accuracy</em></span>,
https://blogs.mathworks.com/cleve/2017/01/23/ulps-plots-reveal-math-function-accurary/
</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="cond.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../utils.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="../cstdfloat.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink