ceph/src/boost/libs/numeric/interval/doc/interval.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>Boost Interval Arithmetic Library</title>
  11 </head>
  12
  13 <body lang="en">
  14   <h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
  15   "middle"> Interval Arithmetic Library</h1>
  16
  17   <center>
  18     <table width="80%" summary="">
  19       <tbody>
  20         <tr>
  21           <td><b>Contents of this page:</b><br>
  22           <a href="#intro">Introduction</a><br>
  23           <a href="#synopsis">Synopsis</a><br>
  24           <a href="#interval">Template class <code>interval</code></a><br>
  25           <a href="#opers">Operations and functions</a><br>
  26           <a href="#interval_lib">Interval support library</a><br>
  27           <!--<a href="#compil">Compilation notes</a><br>-->
  28            <a href="#dangers">Common pitfalls and dangers</a><br>
  29           <a href="#rationale">Rationale</a><br>
  30           <a href="#acks">History and Acknowledgments</a></td>
  31
  32           <td><b>Other pages associated with this page:</b><br>
  33           <a href="rounding.htm">Rounding policies</a><br>
  34           <a href="checking.htm">Checking policies</a><br>
  35           <a href="policies.htm">Policies manipulation</a><br>
  36           <a href="comparisons.htm">Comparisons</a><br>
  37           <a href="numbers.htm">Base number type requirements</a><br>
  38           <a href="guide.htm">Choosing your own interval type</a><br>
  39           <a href="examples.htm">Test and example programs</a><br>
  40           <a href="includes.htm">Headers inclusion</a><br>
  41           <a href="todo.htm">Some items on the todo list</a></td>
  42         </tr>
  43       </tbody>
  44     </table>
  45   </center>
  46
  47   <h2 id="intro">Introduction and Overview</h2>
  48
  49   <p>As implied by its name, this library is intended to help manipulating
  50   mathematical intervals. It consists of a single header &lt;<a href=
  51   "../../../../boost/numeric/interval.hpp">boost/numeric/interval.hpp</a>&gt;
  52   and principally a type which can be used as <code>interval&lt;T&gt;</code>.
  53   In fact, this interval template is declared as
  54   <code>interval&lt;T,Policies&gt;</code> where <code>Policies</code> is a
  55   policy class that controls the various behaviours of the interval class;
  56   <code>interval&lt;T&gt;</code> just happens to pick the default policies
  57   for the type <code>T</code>.</p>
  58
  59   <p><span style="color: #FF0000; font-weight: bold">Warning!</span>
  60   Guaranteed interval arithmetic for native floating-point format is not
  61   supported on every combination of processor, operating system, and
  62   compiler. This is a list of systems known to work correctly when using
  63   <code>interval&lt;float&gt;</code> and <code>interval&lt;double&gt;</code>
  64   with basic arithmetic operators.</p>
  65
  66   <ul>
  67     <li>x86-like hardware is supported by the library with GCC, Visual C++
  68     &ge; 7.1, Intel compiler (&ge; 8 on Windows), CodeWarrior (&ge; 9), as
  69     long as the traditional x87 floating-point unit is used for
  70     floating-point computations (no <code>-mfpmath=sse2</code> support).</li>
  71
  72     <li>Sparc hardware is supported with GCC and Sun compiler.</li>
  73
  74     <li>PowerPC hardware is supported with GCC and CodeWarrior, when
  75     floating-point computations are not done with the Altivec unit.</li>
  76
  77     <li>Alpha hardware is supported with GCC, except maybe for the square
  78     root. The options <code>-mfp-rounding-mode=d -mieee</code> have to be
  79     used.</li>
  80   </ul>
  81
  82   <p>The previous list is not exhaustive. And even if a system does not
  83   provide guaranteed computations for hardware floating-point types, the
  84   interval library is still usable with user-defined types and for doing box
  85   arithmetic.</p>
  86
  87   <h3>Interval Arithmetic</h3>
  88
  89   <p>An interval is a pair of numbers which represents all the numbers
  90   between these two. (Intervals are considered closed so the bounds are
  91   included.) The purpose of this library is to extend the usual arithmetic
  92   functions to intervals. These intervals will be written [<i>a</i>,<i>b</i>]
  93   to represent all the numbers between <i>a</i> and <i>b</i> (included).
  94   <i>a</i> and <i>b</i> can be infinite (but they can not be the same
  95   infinite) and <i>a</i> &le; <i>b</i>.</p>
  96
  97   <p>The fundamental property of interval arithmetic is the
  98   <em><strong>inclusion property</strong></em>:</p>
  99
 100   <dl>
 101     <dd>``if <i>f</i> is a function on a set of numbers, <i>f</i> can be
 102     extended to a new function defined on intervals. This new function
 103     <i>f</i> takes one interval argument and returns an interval result such
 104     as: &forall; <i>x</i> &isin; [<i>a</i>,<i>b</i>], <i>f</i>(<i>x</i>)
 105     &isin; <i>f</i>([<i>a</i>,<i>b</i>]).''</dd>
 106   </dl>
 107
 108   <p>Such a property is not limited to functions with only one argument.
 109   Whenever possible, the interval result should be the smallest one able to
 110   satisfy the property (it is not really useful if the new functions always
 111   answer [-&infin;,+&infin;]).</p>
 112
 113   <p>There are at least two reasons a user would like to use this library.
 114   The obvious one is when the user has to compute with intervals. One example
 115   is when input data have some builtin imprecision: instead of a number, an
 116   input variable can be passed as an interval. Another example application is
 117   to solve equations, by bisecting an interval until the interval width is
 118   small enough. A third example application is in computer graphics, where
 119   computations with boxes, segments or rays can be reduced to computations
 120   with points via intervals.</p>
 121
 122   <p>Another common reason to use interval arithmetic is when the computer
 123   doesn't produce exact results: by using intervals, it is possible to
 124   quantify the propagation of rounding errors. This approach is used often in
 125   numerical computation. For example, let's assume the computer stores
 126   numbers with ten decimal significant digits. To the question 1 + 1E-100 -
 127   1, the computer will answer 0 although the correct answer would be 1E-100.
 128   With the help of interval arithmetic, the computer will answer [0,1E-9].
 129   This is quite a huge interval for such a little result, but the precision
 130   is now known, without having to compute error propagation.</p>
 131
 132   <h3>Numbers, rounding, and exceptional behavior</h3>
 133
 134   <p>The <em><strong>base number type</strong></em> is the type that holds
 135   the bounds of the interval. In order to successfully use interval
 136   arithmetic, the base number type must present some <a href=
 137   "rounding.htm">characteristics</a>. Firstly, due to the definition of an
 138   interval, the base numbers have to be totally ordered so, for instance,
 139   <code>complex&lt;T&gt;</code> is not usable as base number type for
 140   intervals. The mathematical functions for the base number type should also
 141   be compatible with the total order (for instance if x&gt;y and z&gt;t, then
 142   it should also hold that x+z &gt; y+t), so modulo types are not usable
 143   either.</p>
 144
 145   <p>Secondly, the computations must be exact or provide some rounding
 146   methods (for instance, toward minus or plus infinity) if we want to
 147   guarantee the inclusion property. Note that we also may explicitely specify
 148   no rounding, for instance if the base number type is exact, i.e. the result
 149   of a mathematical operation is always computed and represented without loss
 150   of precision. If the number type is not exact, we may still explicitely
 151   specify no rounding, with the obvious consequence that the inclusion
 152   property is no longer guaranteed.</p>
 153
 154   <p>Finally, because heavy loss of precision is always possible, some
 155   numbers have to represent infinities or an exceptional behavior must be
 156   defined. The same situation also occurs for NaN (<i>Not a Number</i>).</p>
 157
 158   <p>Given all this, one may want to limit the template argument T of the
 159   class template <code>interval</code> to the floating point types
 160   <code>float</code>, <code>double</code>, and <code>long double</code>, as
 161   defined by the IEEE-754 Standard. Indeed, if the interval arithmetic is
 162   intended to replace the arithmetic provided by the floating point unit of a
 163   processor, these types are the best choice. Unlike
 164   <code>std::complex</code>, however, we don't want to limit <code>T</code>
 165   to these types. This is why we allow the rounding and exceptional behaviors
 166   to be given by the two policies (rounding and checking). We do nevertheless
 167   provide highly optimized rounding and checking class specializations for
 168   the above-mentioned floating point types.</p>
 169
 170   <h3>Operations and functions</h3>
 171
 172   <p>It is straightforward to define the elementary arithmetic operations on
 173   intervals, being guided by the inclusion property. For instance, if [a,b]
 174   and [c,d] are intervals, [a,b]+[c,d] can be computed by taking the smallest
 175   interval that contains all the numbers x+y for x in [a,b] and y in [c,d];
 176   in this case, rounding a+c down and b+d up will suffice. Other operators
 177   and functions are similarly defined (see their definitions below).</p>
 178
 179   <h3>Comparisons</h3>
 180
 181   <p>It is also possible to define some comparison operators. Given two
 182   intervals, the result is a tri-state boolean type
 183   {<i>false</i>,<i>true,indeterminate</i>}. The answers <i>false</i> and
 184   <i>true</i> are easy to manipulate since they can directly be mapped on the
 185   boolean <i>true</i> and <i>false</i>. But it is not the case for the answer
 186   <em>indeterminate</em> since comparison operators are supposed to be
 187   boolean functions. So, what to do in order to obtain boolean answers?</p>
 188
 189   <p>One solution consists of deciding to adopt an exceptional behavior, such
 190   as a failed assertion or raising an exception. In this case, the
 191   exceptional behavior will be triggered when the result is
 192   indeterminate.</p>
 193
 194   <p>Another solution is to map <em>indeterminate</em> always to
 195   <i>false,</i> or always to <i>true</i>. If <i>false</i> is chosen, the
 196   comparison will be called "<i>certain</i>;" indeed, the result of
 197   [<i>a</i>,<i>b</i>] &lt; [<i>c</i>,<i>d</i>] will be <i>true</i> if and
 198   only if: &forall; <i>x</i> &isin; [<i>a</i>,<i>b</i>] &forall; <i>y</i>
 199   &isin; [<i>c</i>,<i>d</i>], <i>x</i> &lt; <i>y</i>. If <i>true</i> is
 200   chosen, the comparison will be called "<i>possible</i>;" indeed, the result
 201   of [<i>a</i>,<i>b</i>] &lt; [<i>c</i>,<i>d</i>] will be <i>true</i> if and
 202   only if: &exist; <i>x</i> &isin; [<i>a</i>,<i>b</i>] &exist; <i>y</i>
 203   &isin; [<i>c</i>,<i>d</i>], <i>x</i> &lt; <i>y</i>.</p>
 204
 205   <p>Since any of these solution has a clearly defined semantics, it is not
 206   clear that we should enforce either of them. For this reason, the default
 207   behavior consists to mimic the real comparisons by throwing an exception in
 208   the indeterminate case. Other behaviors can be selected bu using specific
 209   comparison namespace. There is also a bunch of explicitely named comparison
 210   functions. See <a href="comparisons.htm">comparisons</a> pages for further
 211   details.</p>
 212
 213   <h3>Overview of the library, and usage</h3>
 214
 215   <p>This library provides two quite distinct levels of usage. One is to use
 216   the basic class template <code>interval&lt;T&gt;</code> without specifying
 217   the policy. This only requires one to know and understand the concepts
 218   developed above and the content of the namespace boost. In addition to the
 219   class <code>interval&lt;T&gt;</code>, this level of usage provides
 220   arithmetic operators (<code>+</code>, <code>-</code>, <code>*</code>,
 221   <code>/</code>), algebraic and piecewise-algebraic functions
 222   (<code>abs</code>, <code>square</code>, <code>sqrt</code>,
 223   <code>pow</code>), transcendental and trigonometric functions
 224   (<code>exp</code>, <code>log</code>, <code>sin</code>, <code>cos</code>,
 225   <code>tan</code>, <code>asin</code>, <code>acos</code>, <code>atan</code>,
 226   <code>sinh</code>, <code>cosh</code>, <code>tanh</code>,
 227   <code>asinh</code>, <code>acosh</code>, <code>atanh</code>), and the
 228   standard comparison operators (<code>&lt;</code>, <code>&lt;=</code>,
 229   <code>&gt;</code>, <code>&gt;=</code>, <code>==</code>, <code>!=</code>),
 230   as well as several interval-specific functions (<code>min</code>,
 231   <code>max</code>, which have a different meaning than <code>std::min</code>
 232   and <code>std::max</code>; <code>lower</code>, <code>upper</code>,
 233   <code>width</code>, <code>median</code>, <code>empty</code>,
 234   <code>singleton</code>, <code>equal</code>, <code>in</code>,
 235   <code>zero_in</code>, <code>subset</code>, <code>proper_subset</code>,
 236   <code>overlap</code>, <code>intersect</code>, <code>hull</code>,
 237   <code>bisect</code>).</p>
 238
 239   <p>For some functions which take several parameters of type
 240   <code>interval&lt;T&gt;</code>, all combinations of argument types
 241   <code>T</code> and <code>interval&lt;T&gt;</code> which contain at least
 242   one <code>interval&lt;T&gt;</code>, are considered in order to avoid a
 243   conversion from the arguments of type <code>T</code> to a singleton of type
 244   <code>interval&lt;T&gt;</code>. This is done for efficiency reasons (the
 245   fact that an argument is a singleton sometimes renders some tests
 246   unnecessary).</p>
 247
 248   <p>A somewhat more advanced usage of this library is to hand-pick the
 249   policies <code>Rounding</code> and <code>Checking</code> and pass them to
 250   <code>interval&lt;T, Policies&gt;</code> through the use of <code>Policies
 251   := boost::numeric::interval_lib::policies&lt;Rounding,Checking&gt;</code>.
 252   Appropriate policies can be fabricated by using the various classes
 253   provided in the namespace <code>boost::numeric::interval_lib</code> as
 254   detailed in section <a href="#interval_lib">Interval Support Library</a>.
 255   It is also possible to choose the comparison scheme by overloading
 256   operators through namespaces.</p>
 257
 258   <h2><a name="synopsis" id="synopsis"></a>Synopsis</h2>
 259   <pre>
 260 namespace boost {
 261 namespace numeric {
 262
 263 namespace interval_lib {
 264
 265 /* this declaration is necessary for the declaration of interval */
 266 template &lt;class T&gt; struct default_policies;
 267
 268 /* ... ; the full synopsis of namespace interval_lib can be found <a href=
 269 "#interval_lib">here</a> */
 270
 271 } // namespace interval_lib
 272
 273
 274 /* template interval_policies; class definition can be found <a href=
 275 "policies.htm">here</a> */
 276 template&lt;class Rounding, class Checking&gt;
 277 struct interval_policies;
 278
 279 /* template class interval; class definition can be found <a href=
 280 "#interval">here</a> */
 281 template&lt;class T, class Policies = typename interval_lib::default_policies&lt;T&gt;::type &gt; class interval;
 282
 283 /* arithmetic operators involving intervals */
 284 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator+(const interval&lt;T, Policies&gt;&amp; x);
 285 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator-(const interval&lt;T, Policies&gt;&amp; x);
 286
 287 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator+(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 288 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator+(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 289 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator+(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 290
 291 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator-(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 292 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator-(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 293 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator-(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 294
 295 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator*(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 296 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator*(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 297 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator*(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 298
 299 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator/(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 300 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator/(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 301 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; operator/(const T&amp; r, const interval&lt;T, Policies&gt;&amp; x);
 302
 303 /* algebraic functions: sqrt, abs, square, pow, nth_root */
 304 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; abs(const interval&lt;T, Policies&gt;&amp; x);
 305 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; sqrt(const interval&lt;T, Policies&gt;&amp; x);
 306 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; square(const interval&lt;T, Policies&gt;&amp; x);
 307 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; pow(const interval&lt;T, Policies&gt;&amp; x, int y);
 308 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; nth_root(const interval&lt;T, Policies&gt;&amp; x, int y);
 309
 310 /* transcendental functions: exp, log */
 311 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; exp(const interval&lt;T, Policies&gt;&amp; x);
 312 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; log(const interval&lt;T, Policies&gt;&amp; x);
 313
 314 /* fmod, for trigonometric function argument reduction (see below) */
 315 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; fmod(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 316 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; fmod(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 317 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; fmod(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 318
 319 /* trigonometric functions */
 320 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; sin(const interval&lt;T, Policies&gt;&amp; x);
 321 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; cos(const interval&lt;T, Policies&gt;&amp; x);
 322 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; tan(const interval&lt;T, Policies&gt;&amp; x);
 323 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; asin(const interval&lt;T, Policies&gt;&amp; x);
 324 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; acos(const interval&lt;T, Policies&gt;&amp; x);
 325 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; atan(const interval&lt;T, Policies&gt;&amp; x);
 326
 327 /* hyperbolic trigonometric functions */
 328 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; sinh(const interval&lt;T, Policies&gt;&amp; x);
 329 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; cosh(const interval&lt;T, Policies&gt;&amp; x);
 330 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; tanh(const interval&lt;T, Policies&gt;&amp; x);
 331 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; asinh(const interval&lt;T, Policies&gt;&amp; x);
 332 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; acosh(const interval&lt;T, Policies&gt;&amp; x);
 333 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; atanh(const interval&lt;T, Policies&gt;&amp; x);
 334
 335 /* min, max external functions (NOT std::min/max, see below) */
 336 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; max(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 337 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; max(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 338 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; max(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 339 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; min(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 340 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; min(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 341 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; min(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 342
 343 /* bounds-related interval functions */
 344 template &lt;class T, class Policies&gt;  T lower(const interval&lt;T, Policies&gt;&amp; x);
 345 template &lt;class T, class Policies&gt;  T upper(const interval&lt;T, Policies&gt;&amp; x);
 346 template &lt;class T, class Policies&gt;  T width(const interval&lt;T, Policies&gt;&amp; x);
 347 template &lt;class T, class Policies&gt;  T median(const interval&lt;T, Policies&gt;&amp; x);
 348 template &lt;class T, class Policies&gt;  T norm(const interval&lt;T, Policies&gt;&amp; x);
 349
 350 /* bounds-related interval functions */
 351 template &lt;class T, class Policies&gt;  bool empty(const interval&lt;T, Policies&gt;&amp; b);
 352 template &lt;class T, class Policies&gt;  bool singleton(const interval&lt;T, Policies&gt;&amp; x);
 353 template &lt;class T, class Policies&gt;  bool equal(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 354 template &lt;class T, class Policies&gt;  bool in(const T&amp; r, const interval&lt;T, Policies&gt;&amp; b);
 355 template &lt;class T, class Policies&gt;  bool zero_in(const interval&lt;T, Policies&gt;&amp; b);
 356 template &lt;class T, class Policies&gt;  bool subset(const interval&lt;T, Policies&gt;&amp; a, const interval&lt;T, Policies&gt;&amp; b);
 357 template &lt;class T, class Policies&gt;  bool proper_subset(const interval&lt;T, Policies&gt;&amp; a, const interval&lt;T, Policies&gt;&amp; b);
 358 template &lt;class T, class Policies&gt;  bool overlap(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 359
 360 /* set manipulation interval functions */
 361 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; intersect(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 362 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; hull(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 363 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; hull(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 364 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; hull(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 365 template &lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; hull(const T&amp; x, const T&amp; y);
 366 template &lt;class T, class Policies&gt;  std::pair&lt;interval&lt;T, Policies&gt;, interval&lt;T, Policies&gt; &gt; bisect(const interval&lt;T, Policies&gt;&amp; x);
 367
 368 /* interval comparison operators */
 369 template&lt;class T, class Policies&gt;  bool operator&lt;(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 370 template&lt;class T, class Policies&gt;  bool operator&lt;(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 371 template&lt;class T, class Policies&gt;  bool operator&lt;(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 372
 373 template&lt;class T, class Policies&gt;  bool operator&lt;=(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 374 template&lt;class T, class Policies&gt;  bool operator&lt;=(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 375 template&lt;class T, class Policies&gt;  bool operator&lt;=(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 376
 377 template&lt;class T, class Policies&gt;  bool operator&gt;(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 378 template&lt;class T, class Policies&gt;  bool operator&gt;(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 379 template&lt;class T, class Policies&gt;  bool operator&gt;(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 380
 381 template&lt;class T, class Policies&gt;  bool operator&gt;=(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 382 template&lt;class T, class Policies&gt;  bool operator&gt;=(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 383 template&lt;class T, class Policies&gt;  bool operator&gt;=(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 384 </pre>
 385   <pre>
 386 template&lt;class T, class Policies&gt;  bool operator==(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 387 template&lt;class T, class Policies&gt;  bool operator==(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 388 template&lt;class T, class Policies&gt;  bool operator==(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 389
 390 template&lt;class T, class Policies&gt;  bool operator!=(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 391 template&lt;class T, class Policies&gt;  bool operator!=(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 392 template&lt;class T, class Policies&gt;  bool operator!=(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 393
 394 namespace interval_lib {
 395
 396 template&lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; division_part1(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&amp; y, bool&amp; b);
 397 template&lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; division_part2(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&amp; y, bool b = true);
 398 template&lt;class T, class Policies&gt;  interval&lt;T, Policies&gt; multiplicative_inverse(const interval&lt;T, Policies&gt;&amp; x);
 399
 400 template&lt;class I&gt;  I add(const typename I::base_type&amp; x, const typename I::base_type&amp; y);
 401 template&lt;class I&gt;  I sub(const typename I::base_type&amp; x, const typename I::base_type&amp; y);
 402 template&lt;class I&gt;  I mul(const typename I::base_type&amp; x, const typename I::base_type&amp; y);
 403 template&lt;class I&gt;  I div(const typename I::base_type&amp; x, const typename I::base_type&amp; y);
 404
 405 } // namespace interval_lib
 406
 407 } // namespace numeric
 408 } // namespace boost
 409 </pre>
 410
 411   <h2><a name="interval" id="interval"></a>Template class
 412   <code>interval</code></h2>The public interface of the template class
 413   interval itself is kept at a simplest minimum:
 414   <pre>
 415 template &lt;class T, class Policies = typename interval_lib::default_policies&lt;T&gt;::type&gt;
 416 class interval
 417 {
 418   public:
 419   typedef T base_type;
 420   typedef Policies traits_type;
 421
 422   interval();
 423   interval(T const &amp;v);
 424   template&lt;class T1&gt; interval(T1 const &amp;v);
 425   interval(T const &amp;l, T const &amp;u);
 426   template&lt;class T1, class T2&gt; interval(T1 const &amp;l, T2 const &amp;u);
 427   interval(interval&lt;T, Policies&gt; const &amp;r);
 428   template&lt;class Policies1&gt; interval(interval&lt;T, Policies1&gt; const &amp;r);
 429   template&lt;class T1, class Policies1&gt; interval(interval&lt;T1, Policies1&gt; const &amp;r);
 430
 431   interval &amp;operator=(T const &amp;v);
 432   template&lt;class T1&gt; interval &amp;operator=(T1 const &amp;v);
 433   interval &amp;operator=(interval&lt;T, Policies&gt; const &amp;r);
 434   template&lt;class Policies1&gt; interval &amp;operator=(interval&lt;T, Policies1&gt; const &amp;r);
 435   template&lt;class T1, class Policies1&gt; interval &amp;operator=(interval&lt;T1, Policies1&gt; const &amp;r);
 436
 437   void assign(T const &amp;l, T const &amp;u);
 438
 439   T const &amp;lower() const;
 440   T const &amp;upper() const;
 441
 442   static interval empty();
 443   static interval whole();
 444   static interval hull(T const &amp;x, T const &amp;y);
 445
 446   interval&amp; operator+= (T const &amp;r);
 447   interval&amp; operator-= (T const &amp;r);
 448   interval&amp; operator*= (T const &amp;r);
 449   interval&amp; operator/= (T const &amp;r);
 450   interval&amp; operator+= (interval const &amp;r);
 451   interval&amp; operator-= (interval const &amp;r);
 452   interval&amp; operator*= (interval const &amp;r);
 453   interval&amp; operator/= (interval const &amp;r);
 454 };
 455 </pre>
 456
 457   <p>The constructors create an interval enclosing their arguments. If there
 458   are two arguments, the first one is assumed to be the left bound and the
 459   second one is the right bound. Consequently, the arguments need to be
 460   ordered. If the property !(l &lt;= u) is not respected, the checking policy
 461   will be used to create an empty interval. If no argument is given, the
 462   created interval is the singleton zero.</p>
 463
 464   <p>If the type of the arguments is the same as the base number type, the
 465   values are directly used for the bounds. If it is not the same type, the
 466   library will use the rounding policy in order to convert the arguments
 467   (<code>conv_down</code> and <code>conv_up</code>) and create an enclosing
 468   interval. When the argument is an interval with a different policy, the
 469   input interval is checked in order to correctly propagate its emptiness (if
 470   empty).</p>
 471
 472   <p>The assignment operators behave similarly, except they obviously take
 473   one argument only. There is also an <code>assign</code> function in order
 474   to directly change the bounds of an interval. It behaves like the
 475   two-arguments constructors if the bounds are not ordered. There is no
 476   assign function that directly takes an interval or only one number as a
 477   parameter; just use the assignment operators in such a case.</p>
 478
 479   <p>The type of the bounds and the policies of the interval type define the
 480   set of values the intervals contain. E.g. with the default policies,
 481   intervals are subsets of the set of real numbers. The static functions
 482   <code>empty</code> and <code>whole</code> produce the intervals/subsets
 483   that are respectively the empty subset and the whole set. They are static
 484   member functions rather than global functions because they cannot guess
 485   their return types. Likewise for <code>hull</code>. <code>empty</code> and
 486   <code>whole</code> involve the checking policy in order to get the bounds
 487   of the resulting intervals.</p>
 488
 489   <h2><a name="opers" id="opers"></a>Operations and Functions</h2>
 490
 491   <p>Some of the following functions expect <code>min</code> and
 492   <code>max</code> to be defined for the base type. Those are the only
 493   requirements for the <code>interval</code> class (but the policies can have
 494   other requirements).</p>
 495
 496   <h4>Operators <code>+</code> <code>-</code> <code>*</code> <code>/</code>
 497   <code>+=</code> <code>-=</code> <code>*=</code> <code>/=</code></h4>
 498
 499   <p>The basic operations are the unary minus and the binary <code>+</code>
 500   <code>-</code> <code>*</code> <code>/</code>. The unary minus takes an
 501   interval and returns an interval. The binary operations take two intervals,
 502   or one interval and a number, and return an interval. If an argument is a
 503   number instead of an interval, you can expect the result to be the same as
 504   if the number was first converted to an interval. This property will be
 505   true for all the following functions and operators.</p>
 506
 507   <p>There are also some assignment operators <code>+=</code> <code>-=</code>
 508   <code>*=</code> <code>/=</code>. There is not much to say: <code>x op=
 509   y</code> is equivalent to <code>x = x op y</code>. If an exception is
 510   thrown during the computations, the l-value is not modified (but it may be
 511   corrupt if an exception is thrown by the base type during an
 512   assignment).</p>
 513
 514   <p>The operators <code>/</code> and <code>/=</code> will try to produce an
 515   empty interval if the denominator is exactly zero. If the denominator
 516   contains zero (but not only zero), the result will be the smallest interval
 517   containing the set of division results; so one of its bound will be
 518   infinite, but it may not be the whole interval.</p>
 519
 520   <h4><code>lower</code> <code>upper</code> <code>median</code>
 521   <code>width</code> <code>norm</code></h4>
 522
 523   <p><code>lower</code>, <code>upper</code>, <code>median</code> respectively
 524   compute the lower bound, the upper bound, and the median number of an
 525   interval (<code>(lower+upper)/2</code> rounded to nearest).
 526   <code>width</code> computes the width of an interval
 527   (<code>upper-lower</code> rounded toward plus infinity). <code>norm</code>
 528   computes an upper bound of the interval in absolute value; it is a
 529   mathematical norm (hence the name) similar to the absolute value for real
 530   numbers.</p>
 531
 532   <h4><code>min</code> <code>max</code> <code>abs</code> <code>square</code>
 533   <code>pow</code> <code>nth_root</code> <code>division_part?</code>
 534   <code>multiplicative_inverse</code></h4>
 535
 536   <p>The functions <code>min</code>, <code>max</code> and <code>abs</code>
 537   are also defined. Please do not mistake them for the functions defined in
 538   the standard library (aka <code>a&lt;b?a:b</code>, <code>a&gt;b?a:b</code>,
 539   <code>a&lt;0?-a:a</code>). These functions are compatible with the
 540   elementary property of interval arithmetic. For example,
 541   max([<i>a</i>,<i>b</i>], [<i>c</i>,<i>d</i>]) = {max(<i>x</i>,<i>y</i>)
 542   such that <i>x</i> in [<i>a</i>,<i>b</i>] and <i>y</i> in
 543   [<i>c</i>,<i>d</i>]}. They are not defined in the <code>std</code>
 544   namespace but in the boost namespace in order to avoid conflict with the
 545   other definitions.</p>
 546
 547   <p>The <code>square</code> function is quite particular. As you can expect
 548   from its name, it computes the square of its argument. The reason this
 549   function is provided is: <code>square(x)</code> is not <code>x*x</code> but
 550   only a subset when <code>x</code> contains zero. For example, [-2,2]*[-2,2]
 551   = [-4,4] but [-2,2]&sup2; = [0,4]; the result is a smaller interval.
 552   Consequently, <code>square(x)</code> should be used instead of
 553   <code>x*x</code> because of its better accuracy and a small performance
 554   improvement.</p>
 555
 556   <p>As for <code>square</code>, <code>pow</code> provides an efficient and
 557   more accurate way to compute the integer power of an interval. Please note:
 558   when the power is 0 and the interval is not empty, the result is 1, even if
 559   the input interval contains 0. <code>nth_root</code> computes the integer root
 560   of an interval (<code>nth_root(pow(x,k),k)</code> encloses <code>x</code> or
 561   <code>abs(x)</code> depending on whether <code>k</code> is odd or even).
 562   The behavior of <code>nth_root</code> is not defined if the integer argument is
 563   not positive. <code>multiplicative_inverse</code> computes
 564   <code>1/x</code>.</p>
 565
 566   <p>The functions <code>division_part1</code> and
 567   <code>division_part2</code> are useful when the user expects the division
 568   to return disjoint intervals if necessary. For example, the narrowest
 569   closed set containing [2,3] / [-2,1] is not ]-&infin;,&infin;[ but the union
 570   of ]-&infin;,-1] and [2,&infin;[. When the result of the division is
 571   representable by only one interval, <code>division_part1</code> returns
 572   this interval and sets the boolean reference to <code>false</code>.
 573   However, if the result needs two intervals, <code>division_part1</code>
 574   returns the negative part and sets the boolean reference to
 575   <code>true</code>; a call to <code>division_part2</code> is now needed to
 576   get the positive part. This second function can take the boolean returned
 577   by the first function as last argument. If this bool is not given, its
 578   value is assumed to be true and the behavior of the function is then
 579   undetermined if the division does not produce a second interval.</p>
 580
 581   <h4><code>intersect</code> <code>hull</code> <code>overlap</code>
 582   <code>in</code> <code>zero_in</code> <code>subset</code>
 583   <code>proper_subset</code> <code>empty</code> <code>singleton</code>
 584   <code>equal</code></h4>
 585
 586   <p><code>intersect</code> computes the set intersection of two closed sets,
 587   <code>hull</code> computes the smallest interval which contains the two
 588   parameters; those parameters can be numbers or intervals. If one of the
 589   arguments is an invalid number or an empty interval, the function will only
 590   use the other argument to compute the resulting interval (if allowed by the
 591   checking policy).</p>
 592
 593   <p>There is no union function since the union of two intervals is not an
 594   interval if they do not overlap. If they overlap, the <code>hull</code>
 595   function computes the union.</p>
 596
 597   <p>The function <code>overlap</code> tests if two intervals have some
 598   common subset. <code>in</code> tests if a number is in an interval;
 599   <code>zero_in</code> is a variant which tests if zero is in the interval.
 600   <code>subset</code> tests if the first interval is a subset of the second;
 601   and <code>proper_subset</code> tests if it is a proper subset.
 602   <code>empty</code> and <code>singleton</code> test if an interval is empty
 603   or is a singleton. Finally, <code>equal</code> tests if two intervals are
 604   equal.</p>
 605
 606   <h4><code>sqrt</code> <code>log</code> <code>exp</code> <code>sin</code>
 607   <code>cos</code> <code>tan</code> <code>asin</code> <code>acos</code>
 608   <code>atan</code> <code>sinh</code> <code>cosh</code> <code>tanh</code>
 609   <code>asinh</code> <code>acosh</code> <code>atanh</code>
 610   <code>fmod</code></h4>
 611
 612   <p>The functions <code>sqrt</code>, <code>log</code>, <code>exp</code>,
 613   <code>sin</code>, <code>cos</code>, <code>tan</code>, <code>asin</code>,
 614   <code>acos</code>, <code>atan</code>, <code>sinh</code>, <code>cosh</code>,
 615   <code>tanh</code>, <code>asinh</code>, <code>acosh</code>,
 616   <code>atanh</code> are also defined. There is not much to say; these
 617   functions extend the traditional functions to the intervals and respect the
 618   basic property of interval arithmetic. They use the <a href=
 619   "checking.htm">checking</a> policy to produce empty intervals when the
 620   input interval is strictly outside of the domain of the function.</p>
 621
 622   <p>The function <code>fmod(interval x, interval y)</code> expects the lower
 623   bound of <code>y</code> to be strictly positive and returns an interval
 624   <code>z</code> such as <code>0 &lt;= z.lower() &lt; y.upper()</code> and
 625   such as <code>z</code> is a superset of <code>x-n*y</code> (with
 626   <code>n</code> being an integer). So, if the two arguments are positive
 627   singletons, this function <code>fmod(interval, interval)</code> will behave
 628   like the traditional function <code>fmod(double, double)</code>.</p>
 629
 630   <p>Please note that <code>fmod</code> does not respect the inclusion
 631   property of arithmetic interval. For example, the result of
 632   <code>fmod</code>([13,17],[7,8]) should be [0,8] (since it must contain
 633   [0,3] and [5,8]). But this answer is not really useful when the purpose is
 634   to restrict an interval in order to compute a periodic function. It is the
 635   reason why <code>fmod</code> will answer [5,10].</p>
 636
 637   <h4><code>add</code> <code>sub</code> <code>mul</code>
 638   <code>div</code></h4>
 639
 640   <p>These four functions take two numbers and return the enclosing interval
 641   for the operations. It avoids converting a number to an interval before an
 642   operation, it can result in a better code with poor optimizers.</p>
 643
 644   <h3>Constants</h3>
 645
 646   <p>Some constants are hidden in the
 647   <code>boost::numeric::interval_lib</code> namespace. They need to be
 648   explicitely templated by the interval type. The functions are
 649   <code>pi&lt;I&gt;()</code>, <code>pi_half&lt;I&gt;()</code> and
 650   <code>pi_twice&lt;I&gt;()</code>, and they return an object of interval
 651   type <code>I</code>. Their respective values are &pi;, &pi;/2 and
 652   2&pi;.</p>
 653
 654   <h3>Exception throwing</h3>
 655
 656   <p>The interval class and all the functions defined around this class never
 657   throw any exceptions by themselves. However, it does not mean that an
 658   operation will never throw an exception. For example, let's consider the
 659   copy constructor. As explained before, it is the default copy constructor
 660   generated by the compiler. So it will not throw an exception if the copy
 661   constructor of the base type does not throw an exception.</p>
 662
 663   <p>The same situation applies to all the functions: exceptions will only be
 664   thrown if the base type or one of the two policies throws an exception.</p>
 665
 666   <h2 id="interval_lib">Interval Support Library</h2>
 667
 668   <p>The interval support library consists of a collection of classes that
 669   can be used and combined to fabricate almost various commonly-needed
 670   interval policies. In contrast to the basic classes and functions which are
 671   used in conjunction with <code>interval&lt;T&gt;</code> (and the default
 672   policies as the implicit second template parameter in this type), which
 673   belong simply to the namespace <code>boost</code>, these components belong
 674   to the namespace <code>boost::numeric::interval_lib</code>.</p>
 675
 676   <p>We merely give the synopsis here and defer each section to a separate
 677   web page since it is only intended for the advanced user. This allows to
 678   expand on each topic with examples, without unduly stretching the limits of
 679   this document.</p>
 680
 681   <h4>Synopsis</h4>
 682   <pre>
 683 namespace boost {
 684 namespace numeric {
 685 namespace interval_lib {
 686
 687 <span style=
 688 "color: #FF0000">/* built-in rounding policy and its specializations */</span>
 689 template &lt;class T&gt;  struct rounded_math;
 690 template &lt;&gt;         struct rounded_math&lt;float&gt;;
 691 template &lt;&gt;         struct rounded_math&lt;double&gt;;
 692 template &lt;&gt;         struct rounded_math&lt;long double&gt;;
 693
 694 <span style=
 695 "color: #FF0000">/* built-in rounding construction blocks */</span>
 696 template &lt;class T&gt;  struct rounding_control;
 697
 698 template &lt;class T, class Rounding = rounding_control&lt;T&gt; &gt;  struct rounded_arith_exact;
 699 template &lt;class T, class Rounding = rounding_control&lt;T&gt; &gt;  struct rounded_arith_std;
 700 template &lt;class T, class Rounding = rounding_control&lt;T&gt; &gt;  struct rounded_arith_opp;
 701
 702 template &lt;class T, class Rounding&gt;  struct rounded_transc_dummy;
 703 template &lt;class T, class Rounding = rounded_arith_exact&lt;T&gt; &gt;  struct rounded_transc_exact;
 704 template &lt;class T, class Rounding = rounded_arith_std  &lt;T&gt; &gt;  struct rounded_transc_std;
 705 template &lt;class T, class Rounding = rounded_arith_opp  &lt;T&gt; &gt;  struct rounded_transc_opp;
 706
 707 template &lt;class Rounding&gt; struct save_state;
 708 template &lt;class Rounding&gt; struct save_state_nothing;
 709
 710 <span style="color: #FF0000">/* built-in checking policies */</span>
 711 template &lt;class T&gt; struct checking_base;
 712 template &lt;class T, class Checking = checking_base&lt;T&gt;, class Exception = exception_create_empty&gt;   struct checking_no_empty;
 713 template &lt;class T, class Checking = checking_base&lt;T&gt; &gt;                                            struct checking_no_nan;
 714 template &lt;class T, class Checking = checking_base&lt;T&gt;, class Exception = exception_invalid_number&gt; struct checking_catch_nan;
 715 template &lt;class T&gt; struct checking_strict;
 716
 717 <span style=
 718 "color: #FF0000">/* some metaprogramming to manipulate interval policies */</span>
 719 template &lt;class Rounding, class Checking&gt; struct policies;
 720 template &lt;class OldInterval, class NewRounding&gt; struct change_rounding;
 721 template &lt;class OldInterval, class NewChecking&gt; struct change_checking;
 722 template &lt;class OldInterval&gt; struct unprotect;
 723
 724 <span style=
 725 "color: #FF0000">/* constants, need to be explicitly templated */</span>
 726 template&lt;class I&gt; I pi();
 727 template&lt;class I&gt; I pi_half();
 728 template&lt;class I&gt; I pi_twice();
 729
 730 <span style="color: #FF0000">/* interval explicit comparison functions:
 731  * the mode can be cer=certainly or pos=possibly,
 732  * the function lt=less_than, gt=greater_than, le=less_than_or_equal_to, ge=greater_than_or_equal_to
 733  *   eq=equal_to, ne= not_equal_to */</span>
 734 template &lt;class T, class Policies&gt;  bool cerlt(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 735 template &lt;class T, class Policies&gt;  bool cerlt(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 736 template &lt;class T, class Policies&gt;  bool cerlt(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 737
 738 template &lt;class T, class Policies&gt;  bool cerle(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 739 template &lt;class T, class Policies&gt;  bool cerle(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 740 template &lt;class T, class Policies&gt;  bool cerle(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 741
 742 template &lt;class T, class Policies&gt;  bool cergt(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 743 template &lt;class T, class Policies&gt;  bool cergt(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 744 template &lt;class T, class Policies&gt;  bool cergt(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 745
 746 template &lt;class T, class Policies&gt;  bool cerge(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 747 template &lt;class T, class Policies&gt;  bool cerge(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 748 template &lt;class T, class Policies&gt;  bool cerge(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 749
 750 template &lt;class T, class Policies&gt;  bool cereq(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 751 template &lt;class T, class Policies&gt;  bool cereq(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 752 template &lt;class T, class Policies&gt;  bool cereq(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 753
 754 template &lt;class T, class Policies&gt;  bool cerne(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 755 template &lt;class T, class Policies&gt;  bool cerne(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 756 template &lt;class T, class Policies&gt;  bool cerne(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 757
 758 template &lt;class T, class Policies&gt;  bool poslt(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 759 template &lt;class T, class Policies&gt;  bool poslt(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 760 template &lt;class T, class Policies&gt;  bool poslt(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 761
 762 template &lt;class T, class Policies&gt;  bool posle(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 763 template &lt;class T, class Policies&gt;  bool posle(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 764 template &lt;class T, class Policies&gt;  bool posle(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 765
 766 template &lt;class T, class Policies&gt;  bool posgt(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 767 template &lt;class T, class Policies&gt;  bool posgt(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 768 template &lt;class T, class Policies&gt;  bool posgt(const T&amp; x, const interval&lt;T, Policies&gt; &amp; y);
 769
 770 template &lt;class T, class Policies&gt;  bool posge(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 771 template &lt;class T, class Policies&gt;  bool posge(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 772 template &lt;class T, class Policies&gt;  bool posge(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 773
 774 template &lt;class T, class Policies&gt;  bool poseq(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 775 template &lt;class T, class Policies&gt;  bool poseq(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 776 template &lt;class T, class Policies&gt;  bool poseq(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 777
 778 template &lt;class T, class Policies&gt;  bool posne(const interval&lt;T, Policies&gt;&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 779 template &lt;class T, class Policies&gt;  bool posne(const interval&lt;T, Policies&gt;&amp; x, const T&amp; y);
 780 template &lt;class T, class Policies&gt;  bool posne(const T&amp; x, const interval&lt;T, Policies&gt;&amp; y);
 781
 782 <span style="color: #FF0000">/* comparison namespaces */</span>
 783 namespace compare {
 784   namespace certain;
 785   namespace possible;
 786   namespace lexicographic;
 787   namespace set;
 788   namespace tribool;
 789 } // namespace compare
 790
 791 } // namespace interval_lib
 792 } // namespace numeric
 793 } // namespace boost
 794 </pre>
 795
 796   <p>Each component of the interval support library is detailed in its own
 797   page.</p>
 798
 799   <ul>
 800     <li><a href="comparisons.htm">Comparisons</a></li>
 801
 802     <li><a href="rounding.htm">Rounding</a></li>
 803
 804     <li><a href="checking.htm">Checking</a></li>
 805   </ul>
 806
 807   <h2 id="dangers">Common Pitfalls and Dangers</h2>
 808
 809   <h4>Comparisons</h4>
 810
 811   <p>One of the biggest problems is probably the correct use of the
 812   comparison functions and operators. First, functions and operators do not
 813   try to know if two intervals are the same mathematical object. So, if the
 814   comparison used is "certain", then <code>x != x</code> is always true
 815   unless <code>x</code> is a singleton interval; and the same problem arises
 816   with <code>cereq</code> and <code>cerne</code>.</p>
 817
 818   <p>Another misleading interpretation of the comparison is: you cannot
 819   always expect [a,b] &lt; [c,d] to be !([a,b] &gt;= [c,d]) since the
 820   comparison is not necessarily total. Equality and less comparison should be
 821   seen as two distincts relational operators. However the default comparison
 822   operators do respect this property since they throw an exception whenever
 823   [a,b] and [c,d] overlap.</p>
 824
 825   <h4>Interval values and references</h4>
 826
 827   <p>This problem is a corollary of the previous problem with <code>x !=
 828   x</code>. All the functions of the library only consider the value of an
 829   interval and not the reference of an interval. In particular, you should
 830   not expect (unless <code>x</code> is a singleton) the following values to
 831   be equal: <code>x/x</code> and 1, <code>x*x</code> and
 832   <code>square(x)</code>, <code>x-x</code> and 0, etc. So the main cause of
 833   wide intervals is that interval arithmetic does not identify different
 834   occurrences of the same variable. So, whenever possible, the user has to
 835   rewrite the formulas to eliminate multiple occurences of the same variable.
 836   For example, <code>square(x)-2*x</code> is far less precise than
 837   <code>square(x-1)-1</code>.</p>
 838
 839   <h4>Unprotected rounding</h4>
 840
 841   <p>As explained in <a href="rounding.htm#perf">this section</a>, a good way
 842   to speed up computations when the base type is a basic floating-point type
 843   is to unprotect the intervals at the hot spots of the algorithm. This
 844   method is safe and really an improvement for interval computations. But
 845   please remember that any basic floating-point operation executed inside the
 846   unprotection blocks will probably have an undefined behavior (but only for
 847   the current thread). And do not forget to create a rounding object as
 848   explained in the <a href="rounding.htm#perfexp">example</a>.</p>
 849
 850   <h2 id="rationale">Rationale</h2>
 851
 852   <p>The purpose of this library is to provide an efficient and generalized
 853   way to deal with interval arithmetic through the use of a templatized class
 854   <code>boost::numeric::interval</code>. The big contention for which we provide a
 855   rationale is the format of this class template.</p>
 856
 857   <p>It would have been easier to provide a class interval whose base type is
 858   double. Or to follow <code>std::complex</code> and allow only
 859   specializations for <code>float</code>, <code>double</code>, and <code>long
 860   double</code>. We decided not to do this to allow intervals on custom
 861   types, e.g. fixed-precision bigfloat library types (MPFR, etc), rational
 862   numbers, and so on.</p>
 863
 864   <p><strong>Policy design.</strong> Although it was tempting to make it a
 865   class template with only one template argument, the diversity of uses for
 866   an interval arithmetic practically forced us to use policies. The behavior
 867   of this class can be fixed by two policies. These policies are packaged
 868   into a single policy class, rather than making <code>interval</code> with
 869   three template parameters. This is both for ease of use (the policy class
 870   can be picked by default) and for readability.</p>
 871
 872   <p>The first policy provides all the mathematical functions on the base
 873   type needed to define the functions on the interval type. The second one
 874   sets the way exceptional cases encountered during computations are
 875   handled.</p>
 876
 877   <p>We could foresee situations where any combination of these policies
 878   would be appropriate. Moreover, we wanted to enable the user of the library
 879   to reuse the <code>interval</code> class template while at the same time
 880   choosing his own behavior. See this <a href="guide.htm">page</a> for some
 881   examples.</p>
 882
 883   <p><strong>Rounding policy.</strong> The library provides specialized
 884   implementations of the rounding policy for the primitive types float and
 885   double. In order for these implementations to be correct and fast, the
 886   library needs to work a lot with rounding modes. Some processors are
 887   directly dealt with and some mechanisms are provided in order to speed up
 888   the computations. It seems to be heavy and hazardous optimizations for a
 889   gain of only a few computer cycles; but in reality, the speed-up factor can
 890   easily go past 2 or 3 depending on the computer. Moreover, these
 891   optimizations do not impact the interface in any major way (with the design
 892   we have chosen, everything can be added by specialization or by passing
 893   different template parameters).</p>
 894
 895   <p><strong>Pred/succ.</strong> In a previous version, two functions
 896   <code>pred</code> and <code>succ</code>, with various corollaries like
 897   <code>widen</code>, were supplied. The intent was to enlarge the interval
 898   by one ulp (as little as possible), e.g. to ensure the inclusion property.
 899   Since making interval a template of T, we could not define <i>ulp</i> for a
 900   random parameter. In turn, rounding policies let us eliminate entirely the
 901   use of ulp while making the intervals tighter (if a result is a
 902   representable singleton, there is no use to widen the interval). We decided
 903   to drop those functions.</p>
 904
 905   <p><strong>Specialization of <code>std::less</code>.</strong> Since the
 906   operator <code>&lt;</code> depends on the comparison namespace locally
 907   chosen by the user, it is not possible to correctly specialize
 908   <code>std::less</code>. So you have to explicitely provide such a class to
 909   all the algorithms and templates that could require it (for example,
 910   <code>std::map</code>).</p>
 911
 912   <p><strong>Input/output.</strong> The interval library does not include I/O
 913   operators. Printing an interval value allows a lot of customization: some
 914   people may want to output the bounds, others may want to display the median
 915   and the width of intervals, and so on. The example file io.cpp shows some
 916   possibilities and may serve as a foundation in order for the user to define
 917   her own operators.</p>
 918
 919   <p><strong>Mixed operations with integers.</strong> When using and reusing
 920   template codes, it is common there are operations like <code>2*x</code>.
 921   However, the library does not provide them by default because the
 922   conversion from <code>int</code> to the base number type is not always
 923   correct (think about the conversion from a 32bit integer to a single
 924   precision floating-point number). So the functions have been put in a
 925   separate header and the user needs to include them explicitely if she wants
 926   to benefit from these mixed operators. Another point, there is no mixed
 927   comparison operators due to the technical way they are defined.</p>
 928
 929   <p><strong>Interval-aware functions.</strong> All the functions defined by
 930   the library are obviously aware they manipulate intervals and they do it
 931   accordingly to general interval arithmetic principles. Consequently they
 932   may have a different behavior than the one commonly encountered with
 933   functions not interval-aware. For example, <code>max</code> is defined by
 934   canonical set extension and the result is not always one of the two
 935   arguments (if the intervals do not overlap, then the result is one of the
 936   two intervals).</p>
 937
 938   <p>This behavior is different from <code>std::max</code> which returns a
 939   reference on one of its arguments. So if the user expects a reference to be
 940   returned, she should use <code>std::max</code> since it is exactly what
 941   this function does. Please note that <code>std::max</code> will throw an
 942   exception when the intervals overlap. This behavior does not predate the
 943   one described by the C++ standard since the arguments are not "equivalent"
 944   and it allows to have an equivalence between <code>a &lt;= b</code> and
 945   <code>&amp;b == &amp;std::max(a,b)</code>(some particular cases may be
 946   implementation-defined). However it is different from the one described by
 947   SGI since it does not return the first argument even if "neither is greater
 948   than the other".</p>
 949
 950   <h2 id="acks">History and Acknowledgments</h2>
 951
 952   <p>This library was mostly inspired by previous work from Jens Maurer. Some
 953   discussions about his work are reproduced <a href=
 954   "http://www.mscs.mu.edu/%7Egeorgec/IFAQ/maurer1.html">here</a>. Jeremy Siek
 955   and Maarten Keijzer provided some rounding control for MSVC and Sparc
 956   platforms.</p>
 957
 958   <p>Guillaume Melquiond, Herv&eacute; Br&ouml;nnimann and Sylvain Pion
 959   started from the library left by Jens and added the policy design.
 960   Guillaume and Sylvain worked hard on the code, especially the porting and
 961   mostly tuning of the rounding modes to the different architectures.
 962   Guillaume did most of the coding, while Sylvain and Herv&eacute; have
 963   provided some useful comments in order for this library to be written.
 964   Herv&eacute; reorganized and wrote chapters of the documentation based on
 965   Guillaume's great starting point.</p>
 966
 967   <p>This material is partly based upon work supported by the National
 968   Science Foundation under NSF CAREER Grant CCR-0133599. Any opinions,
 969   findings and conclusions or recommendations expressed in this material are
 970   those of the author(s) and do not necessarily reflect the views of the
 971   National Science Foundation (NSF).</p>
 972   <hr>
 973
 974   <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
 975   "../../../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
 976   height="31" width="88"></a></p>
 977
 978   <p>Revised
 979   <!--webbot bot="Timestamp" s-type="EDITED" s-format="%Y-%m-%d" startspan -->2006-12-25<!--webbot bot="Timestamp" endspan i-checksum="12174" --></p>
 980
 981   <p><i>Copyright &copy; 2002 Guillaume Melquiond, Sylvain Pion, Herv&eacute;
 982   Br&ouml;nnimann, Polytechnic University<br>
 983   Copyright &copy; 2003-2006 Guillaume Melquiond, ENS Lyon</i></p>
 984
 985   <p><i>Distributed under the Boost Software License, Version 1.0. (See
 986   accompanying file <a href="../../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a>
 987   or copy at <a href=
 988   "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
 989 </body>
 990 </html>