ceph/src/boost/libs/numeric/interval/doc/examples.htm

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
   2 "http://www.w3.org/TR/html4/loose.dtd">
   3
   4 <html>
   5 <head>
   6   <meta http-equiv="Content-Language" content="en-us">
   7   <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
   8   <link rel="stylesheet" type="text/css" href="../../../../boost.css">
   9
  10   <title>Tests and Examples</title>
  11 </head>
  12
  13 <body lang="en">
  14   <h1>Tests and Examples</h1>
  15
  16   <h2>A first example</h2>
  17
  18   <p>This example shows how to design a function which takes a polynomial and
  19   a value and returns the sign of this polynomial at this point. This
  20   function is a filter: if the answer is not guaranteed, the functions says
  21   so. The reason of using a filter rather than a simple evaluation function
  22   is: computations with floating-point numbers will incur approximations and
  23   it can be enough to change the sign of the polynomial. So, in order to
  24   validate the result, the function will use interval arithmetic.</p>
  25
  26   <p>The first step is the inclusion of the appropriate headers. Because the
  27   function will handle floating-point bounds, the easiest solution is:</p>
  28   <pre>
  29 #include &lt;boost/numeric/interval.hpp&gt;
  30 </pre>
  31
  32   <p>Now, let's begin the function. The polynomial is given by the array of
  33   its coefficients and its size (strictly greater to its degree). In order to
  34   simplify the code, two namespaces of the library are included.</p>
  35   <pre>
  36 int sign_polynomial(double x, double P[], int sz) {
  37   using namespace boost::numeric;
  38   using namespace interval_lib;
  39 </pre>
  40
  41   <p>Then we can define the interval type. Since no special behavior is
  42   required, the default policies are enough:</p>
  43   <pre>
  44   typedef interval&lt;double&gt; I;
  45 </pre>
  46
  47   <p>For the evaluation, let's just use the Horner scheme with interval
  48   arithmetic. The library overloads all the arithmetic operators and provides
  49   mixed operations, so the only difference between the code with and without
  50   interval arithmetic lies in the type of the iterated value
  51   <code>y</code>:</p>
  52   <pre>
  53   I y = P[sz - 1];
  54   for(int i = sz - 2; i &gt;= 0; i--)
  55     y = y * x + P[i];
  56 </pre>
  57
  58   <p>The last step is the computation of the sign of <code>y</code>. It is
  59   done by choosing an appropriate comparison scheme and then doing the
  60   comparison with the usual operators:</p>
  61   <pre>
  62   using namespace compare::certain;
  63   if (y &gt; 0.) return 1;
  64   if (y &lt; 0.) return -1;
  65   return 0;
  66 }
  67 </pre>
  68
  69   <p>The answer <code>0</code> does not mean the polynomial is zero at this
  70   point. It only means the answer is not known since <code>y</code> contains
  71   zero and thus does not have a precise sign.</p>
  72
  73   <p>Now we have the expected function. However, due to the poor
  74   implementations of floating-point rounding in most of the processors, it
  75   can be useful to say to optimize the code; or rather, to let the library
  76   optimize it. The main condition for this optimization is that the interval
  77   code should not be mixed with floating-point code. In this example, it is
  78   the case, since all the operations done in the functions involve the
  79   library. So the code can be rewritten:</p>
  80   <pre>
  81 int sign_polynomial(double x, double P[], int sz) {
  82   using namespace boost::numeric;
  83   using namespace interval_lib;
  84   typedef interval&lt;double&gt; I_aux;
  85
  86   I_aux::traits_type::rounding rnd;
  87   typedef unprotect&lt;I_aux&gt;::type I;
  88
  89   I y = P[sz - 1];
  90   for(int i = sz - 2; i &gt;= 0; i--)
  91     y = y * x + P[i];
  92
  93   using namespace compare::certain;
  94   if (y &gt; 0.) return 1;
  95   if (y &lt; 0.) return -1;
  96   return 0;
  97 }
  98 </pre>
  99
 100   <p>The difference between this code and the previous is the use of another
 101   interval type. This new type <code>I</code> indicates to the library that
 102   all the computations can be done without caring for the rounding mode. And
 103   because of that, it is up to the function to care about it: a rounding
 104   object need to be alive whenever the optimized type is used.</p>
 105
 106   <h2>Other tests and examples</h2>
 107
 108   <p>In <code>libs/numeric/interval/test/</code> and
 109   <code>libs/numeric/interval/examples/</code> are some test and example
 110   programs.. The examples illustrate a few uses of intervals. For a general
 111   description and considerations on using this library, and some potential
 112   domains of application, please read this <a href=
 113   "guide.htm">mini-guide</a>.</p>
 114
 115   <h3>Tests</h3>
 116
 117   <p>The test programs are as follows. Please note that they require the use
 118   of the Boost.test library and can be automatically tested by using
 119   <code>bjam</code> (except for interval_test.cpp).</p>
 120
 121   <p><b>add.cpp</b> tests if the additive and subtractive operators and the
 122   respective _std and _opp rounding functions are correctly implemented. It
 123   is done by using symbolic expressions as a base type.</p>
 124
 125   <p><b>cmp.cpp</b>, <b>cmp_lex.cpp</b>, <b>cmp_set.cpp</b>, and
 126   <b>cmp_tribool.cpp</b> test if the operators <code>&lt;</code>
 127   <code>&gt;</code> <code>&lt;=</code> <code>&gt;=</code> <code>==</code>
 128   <code>!=</code> behave correctly for the default, lexicographic, set, and
 129   tristate comparisons. <b>cmp_exp.cpp</b> tests the explicit comparison
 130   functions <code>cer..</code> and <code>pos..</code> behave correctly.
 131   <b>cmp_exn.cpp</b> tests if the various policies correctly detect
 132   exceptional cases. All these tests use some simple intervals ([1,2] and
 133   [3,4], [1,3] and [2,4], [1,2] and [2,3], etc).</p>
 134
 135   <p><b>det.cpp</b> tests if the <code>_std</code> and <code>_opp</code>
 136   versions in protected and unprotected mode produce the same result when
 137   Gauss scheme is used on an unstable matrix (in order to exercise rounding).
 138   The tests are done for <code>interval&lt;float&gt;</code> and
 139   <code>interval&lt;double&gt;</code>.</p>
 140
 141   <p><b>fmod.cpp</b> defines a minimalistic version of
 142   <code>interval&lt;int&gt;</code> and uses it in order to test
 143   <code>fmod</code> on some specific interval values.</p>
 144
 145   <p><b>mul.cpp</b> exercises the multiplication, the finite division, the
 146   square and the square root with some integer intervals leading to exact
 147   results.</p>
 148
 149   <p><b>pi.cpp</b> tests if the interval value of &pi; (for <code>int</code>,
 150   <code>float</code> and <code>double</code> base types) contains the number
 151   &pi; (defined with 21 decimal digits) and if it is a subset of
 152   [&pi;&plusmn;1ulp] (in order to ensure some precision).</p>
 153
 154   <p><b>pow.cpp</b> tests if the <code>pow</code> function behaves correctly
 155   on some simple test cases.</p>
 156
 157   <p><b>test_float.cpp</b> exercises the arithmetic operations of the library
 158   for floating point base types.</p>
 159
 160   <p><b>interval_test.cpp</b> tests if the interval library respects the
 161   inclusion property of interval arithmetic by computing some functions and
 162   operations for both <code>double</code> and
 163   <code>interval&lt;double&gt;</code>.</p>
 164
 165   <h2>Examples</h2>
 166
 167   <p><b>filter.cpp</b> contains filters for computational geometry able to
 168   find the sign of a determinant. This example is inspired by the article
 169   <em>Interval arithmetic yields efficient dynamic filters for computational
 170   geometry</em> by Br&ouml;nnimann, Burnikel and Pion, 2001.</p>
 171
 172   <p><b>findroot_demo.cpp</b> finds zeros of some functions by using
 173   dichotomy and even produces gnuplot data for one of them. The processor has
 174   to correctly handle elementary functions for this example to properly
 175   work.</p>
 176
 177   <p><b>horner.cpp</b> is a really basic example of unprotecting the interval
 178   operations for a whole function (which computes the value of a polynomial
 179   by using Horner scheme).</p>
 180
 181   <p><b>io.cpp</b> shows some stream input and output operators for intervals
 182   .The wide variety of possibilities explains why the library do not
 183   implement i/o operators and they are left to the user.</p>
 184
 185   <p><b>newton-raphson.cpp</b> is an implementation of a specialized version
 186   of Newton-Raphson algorithm for finding the zeros of a function knowing its
 187   derivative. It exercises unprotecting, full division, some set operations
 188   and empty intervals.</p>
 189
 190   <p><b>transc.cpp</b> implements the transcendental part of the rounding
 191   policy for <code>double</code> by using an external library (the MPFR
 192   subset of GMP in this case).</p>
 193   <hr>
 194
 195   <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
 196   "../../../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
 197   height="31" width="88"></a></p>
 198
 199   <p>Revised
 200   <!--webbot bot="Timestamp" s-type="EDITED" s-format="%Y-%m-%d" startspan -->2006-12-24<!--webbot bot="Timestamp" endspan i-checksum="12172" --></p>
 201
 202   <p><i>Copyright &copy; 2002 Guillaume Melquiond, Sylvain Pion, Herv&eacute;
 203   Br&ouml;nnimann, Polytechnic University<br>
 204   Copyright &copy; 2003 Guillaume Melquiond</i></p>
 205
 206   <p><i>Distributed under the Boost Software License, Version 1.0. (See
 207   accompanying file <a href="../../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a>
 208   or copy at <a href=
 209   "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
 210 </body>
 211 </html>