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