]>
Commit | Line | Data |
---|---|---|
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 <<a href= | |
51 | "../../../../boost/numeric/interval.hpp">boost/numeric/interval.hpp</a>> | |
52 | and principally a type which can be used as <code>interval<T></code>. | |
53 | In fact, this interval template is declared as | |
54 | <code>interval<T,Policies></code> where <code>Policies</code> is a | |
55 | policy class that controls the various behaviours of the interval class; | |
56 | <code>interval<T></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<float></code> and <code>interval<double></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 | ≥ 7.1, Intel compiler (≥ 8 on Windows), CodeWarrior (≥ 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> ≤ <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: ∀ <i>x</i> ∈ [<i>a</i>,<i>b</i>], <i>f</i>(<i>x</i>) | |
105 | ∈ <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 [-∞,+∞]).</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<T></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>y and z>t, then | |
142 | it should also hold that x+z > 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>] < [<i>c</i>,<i>d</i>] will be <i>true</i> if and | |
198 | only if: ∀ <i>x</i> ∈ [<i>a</i>,<i>b</i>] ∀ <i>y</i> | |
199 | ∈ [<i>c</i>,<i>d</i>], <i>x</i> < <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>] < [<i>c</i>,<i>d</i>] will be <i>true</i> if and | |
202 | only if: ∃ <i>x</i> ∈ [<i>a</i>,<i>b</i>] ∃ <i>y</i> | |
203 | ∈ [<i>c</i>,<i>d</i>], <i>x</i> < <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<T></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<T></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><</code>, <code><=</code>, | |
229 | <code>></code>, <code>>=</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<T></code>, all combinations of argument types | |
241 | <code>T</code> and <code>interval<T></code> which contain at least | |
242 | one <code>interval<T></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<T></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<T, Policies></code> through the use of <code>Policies | |
251 | := boost::numeric::interval_lib::policies<Rounding,Checking></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 <class T> 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<class Rounding, class Checking> | |
277 | struct interval_policies; | |
278 | ||
279 | /* template class interval; class definition can be found <a href= | |
280 | "#interval">here</a> */ | |
281 | template<class T, class Policies = typename interval_lib::default_policies<T>::type > class interval; | |
282 | ||
283 | /* arithmetic operators involving intervals */ | |
284 | template <class T, class Policies> interval<T, Policies> operator+(const interval<T, Policies>& x); | |
285 | template <class T, class Policies> interval<T, Policies> operator-(const interval<T, Policies>& x); | |
286 | ||
287 | template <class T, class Policies> interval<T, Policies> operator+(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
288 | template <class T, class Policies> interval<T, Policies> operator+(const interval<T, Policies>& x, const T& y); | |
289 | template <class T, class Policies> interval<T, Policies> operator+(const T& x, const interval<T, Policies>& y); | |
290 | ||
291 | template <class T, class Policies> interval<T, Policies> operator-(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
292 | template <class T, class Policies> interval<T, Policies> operator-(const interval<T, Policies>& x, const T& y); | |
293 | template <class T, class Policies> interval<T, Policies> operator-(const T& x, const interval<T, Policies>& y); | |
294 | ||
295 | template <class T, class Policies> interval<T, Policies> operator*(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
296 | template <class T, class Policies> interval<T, Policies> operator*(const interval<T, Policies>& x, const T& y); | |
297 | template <class T, class Policies> interval<T, Policies> operator*(const T& x, const interval<T, Policies>& y); | |
298 | ||
299 | template <class T, class Policies> interval<T, Policies> operator/(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
300 | template <class T, class Policies> interval<T, Policies> operator/(const interval<T, Policies>& x, const T& y); | |
301 | template <class T, class Policies> interval<T, Policies> operator/(const T& r, const interval<T, Policies>& x); | |
302 | ||
303 | /* algebraic functions: sqrt, abs, square, pow, nth_root */ | |
304 | template <class T, class Policies> interval<T, Policies> abs(const interval<T, Policies>& x); | |
305 | template <class T, class Policies> interval<T, Policies> sqrt(const interval<T, Policies>& x); | |
306 | template <class T, class Policies> interval<T, Policies> square(const interval<T, Policies>& x); | |
307 | template <class T, class Policies> interval<T, Policies> pow(const interval<T, Policies>& x, int y); | |
308 | template <class T, class Policies> interval<T, Policies> nth_root(const interval<T, Policies>& x, int y); | |
309 | ||
310 | /* transcendental functions: exp, log */ | |
311 | template <class T, class Policies> interval<T, Policies> exp(const interval<T, Policies>& x); | |
312 | template <class T, class Policies> interval<T, Policies> log(const interval<T, Policies>& x); | |
313 | ||
314 | /* fmod, for trigonometric function argument reduction (see below) */ | |
315 | template <class T, class Policies> interval<T, Policies> fmod(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
316 | template <class T, class Policies> interval<T, Policies> fmod(const interval<T, Policies>& x, const T& y); | |
317 | template <class T, class Policies> interval<T, Policies> fmod(const T& x, const interval<T, Policies>& y); | |
318 | ||
319 | /* trigonometric functions */ | |
320 | template <class T, class Policies> interval<T, Policies> sin(const interval<T, Policies>& x); | |
321 | template <class T, class Policies> interval<T, Policies> cos(const interval<T, Policies>& x); | |
322 | template <class T, class Policies> interval<T, Policies> tan(const interval<T, Policies>& x); | |
323 | template <class T, class Policies> interval<T, Policies> asin(const interval<T, Policies>& x); | |
324 | template <class T, class Policies> interval<T, Policies> acos(const interval<T, Policies>& x); | |
325 | template <class T, class Policies> interval<T, Policies> atan(const interval<T, Policies>& x); | |
326 | ||
327 | /* hyperbolic trigonometric functions */ | |
328 | template <class T, class Policies> interval<T, Policies> sinh(const interval<T, Policies>& x); | |
329 | template <class T, class Policies> interval<T, Policies> cosh(const interval<T, Policies>& x); | |
330 | template <class T, class Policies> interval<T, Policies> tanh(const interval<T, Policies>& x); | |
331 | template <class T, class Policies> interval<T, Policies> asinh(const interval<T, Policies>& x); | |
332 | template <class T, class Policies> interval<T, Policies> acosh(const interval<T, Policies>& x); | |
333 | template <class T, class Policies> interval<T, Policies> atanh(const interval<T, Policies>& x); | |
334 | ||
335 | /* min, max external functions (NOT std::min/max, see below) */ | |
336 | template <class T, class Policies> interval<T, Policies> max(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
337 | template <class T, class Policies> interval<T, Policies> max(const interval<T, Policies>& x, const T& y); | |
338 | template <class T, class Policies> interval<T, Policies> max(const T& x, const interval<T, Policies>& y); | |
339 | template <class T, class Policies> interval<T, Policies> min(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
340 | template <class T, class Policies> interval<T, Policies> min(const interval<T, Policies>& x, const T& y); | |
341 | template <class T, class Policies> interval<T, Policies> min(const T& x, const interval<T, Policies>& y); | |
342 | ||
343 | /* bounds-related interval functions */ | |
344 | template <class T, class Policies> T lower(const interval<T, Policies>& x); | |
345 | template <class T, class Policies> T upper(const interval<T, Policies>& x); | |
346 | template <class T, class Policies> T width(const interval<T, Policies>& x); | |
347 | template <class T, class Policies> T median(const interval<T, Policies>& x); | |
348 | template <class T, class Policies> T norm(const interval<T, Policies>& x); | |
349 | ||
350 | /* bounds-related interval functions */ | |
351 | template <class T, class Policies> bool empty(const interval<T, Policies>& b); | |
352 | template <class T, class Policies> bool singleton(const interval<T, Policies>& x); | |
353 | template <class T, class Policies> bool equal(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
354 | template <class T, class Policies> bool in(const T& r, const interval<T, Policies>& b); | |
355 | template <class T, class Policies> bool zero_in(const interval<T, Policies>& b); | |
356 | template <class T, class Policies> bool subset(const interval<T, Policies>& a, const interval<T, Policies>& b); | |
357 | template <class T, class Policies> bool proper_subset(const interval<T, Policies>& a, const interval<T, Policies>& b); | |
358 | template <class T, class Policies> bool overlap(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
359 | ||
360 | /* set manipulation interval functions */ | |
361 | template <class T, class Policies> interval<T, Policies> intersect(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
362 | template <class T, class Policies> interval<T, Policies> hull(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
363 | template <class T, class Policies> interval<T, Policies> hull(const interval<T, Policies>& x, const T& y); | |
364 | template <class T, class Policies> interval<T, Policies> hull(const T& x, const interval<T, Policies>& y); | |
365 | template <class T, class Policies> interval<T, Policies> hull(const T& x, const T& y); | |
366 | template <class T, class Policies> std::pair<interval<T, Policies>, interval<T, Policies> > bisect(const interval<T, Policies>& x); | |
367 | ||
368 | /* interval comparison operators */ | |
369 | template<class T, class Policies> bool operator<(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
370 | template<class T, class Policies> bool operator<(const interval<T, Policies>& x, const T& y); | |
371 | template<class T, class Policies> bool operator<(const T& x, const interval<T, Policies>& y); | |
372 | ||
373 | template<class T, class Policies> bool operator<=(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
374 | template<class T, class Policies> bool operator<=(const interval<T, Policies>& x, const T& y); | |
375 | template<class T, class Policies> bool operator<=(const T& x, const interval<T, Policies>& y); | |
376 | ||
377 | template<class T, class Policies> bool operator>(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
378 | template<class T, class Policies> bool operator>(const interval<T, Policies>& x, const T& y); | |
379 | template<class T, class Policies> bool operator>(const T& x, const interval<T, Policies>& y); | |
380 | ||
381 | template<class T, class Policies> bool operator>=(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
382 | template<class T, class Policies> bool operator>=(const interval<T, Policies>& x, const T& y); | |
383 | template<class T, class Policies> bool operator>=(const T& x, const interval<T, Policies>& y); | |
384 | </pre> | |
385 | <pre> | |
386 | template<class T, class Policies> bool operator==(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
387 | template<class T, class Policies> bool operator==(const interval<T, Policies>& x, const T& y); | |
388 | template<class T, class Policies> bool operator==(const T& x, const interval<T, Policies>& y); | |
389 | ||
390 | template<class T, class Policies> bool operator!=(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
391 | template<class T, class Policies> bool operator!=(const interval<T, Policies>& x, const T& y); | |
392 | template<class T, class Policies> bool operator!=(const T& x, const interval<T, Policies>& y); | |
393 | ||
394 | namespace interval_lib { | |
395 | ||
396 | template<class T, class Policies> interval<T, Policies> division_part1(const interval<T, Policies>& x, const interval<T, Policies& y, bool& b); | |
397 | template<class T, class Policies> interval<T, Policies> division_part2(const interval<T, Policies>& x, const interval<T, Policies& y, bool b = true); | |
398 | template<class T, class Policies> interval<T, Policies> multiplicative_inverse(const interval<T, Policies>& x); | |
399 | ||
400 | template<class I> I add(const typename I::base_type& x, const typename I::base_type& y); | |
401 | template<class I> I sub(const typename I::base_type& x, const typename I::base_type& y); | |
402 | template<class I> I mul(const typename I::base_type& x, const typename I::base_type& y); | |
403 | template<class I> I div(const typename I::base_type& x, const typename I::base_type& 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 <class T, class Policies = typename interval_lib::default_policies<T>::type> | |
416 | class interval | |
417 | { | |
418 | public: | |
419 | typedef T base_type; | |
420 | typedef Policies traits_type; | |
421 | ||
422 | interval(); | |
423 | interval(T const &v); | |
424 | template<class T1> interval(T1 const &v); | |
425 | interval(T const &l, T const &u); | |
426 | template<class T1, class T2> interval(T1 const &l, T2 const &u); | |
427 | interval(interval<T, Policies> const &r); | |
428 | template<class Policies1> interval(interval<T, Policies1> const &r); | |
429 | template<class T1, class Policies1> interval(interval<T1, Policies1> const &r); | |
430 | ||
431 | interval &operator=(T const &v); | |
432 | template<class T1> interval &operator=(T1 const &v); | |
433 | interval &operator=(interval<T, Policies> const &r); | |
434 | template<class Policies1> interval &operator=(interval<T, Policies1> const &r); | |
435 | template<class T1, class Policies1> interval &operator=(interval<T1, Policies1> const &r); | |
436 | ||
437 | void assign(T const &l, T const &u); | |
438 | ||
439 | T const &lower() const; | |
440 | T const &upper() const; | |
441 | ||
442 | static interval empty(); | |
443 | static interval whole(); | |
444 | static interval hull(T const &x, T const &y); | |
445 | ||
446 | interval& operator+= (T const &r); | |
447 | interval& operator-= (T const &r); | |
448 | interval& operator*= (T const &r); | |
449 | interval& operator/= (T const &r); | |
450 | interval& operator+= (interval const &r); | |
451 | interval& operator-= (interval const &r); | |
452 | interval& operator*= (interval const &r); | |
453 | interval& operator/= (interval const &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 <= 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<b?a:b</code>, <code>a>b?a:b</code>, | |
539 | <code>a<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]² = [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 ]-∞,∞[ but the union | |
570 | of ]-∞,-1] and [2,∞[. 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 <= z.lower() < 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<I>()</code>, <code>pi_half<I>()</code> and | |
650 | <code>pi_twice<I>()</code>, and they return an object of interval | |
651 | type <code>I</code>. Their respective values are π, π/2 and | |
652 | 2π.</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<T></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 <class T> struct rounded_math; | |
690 | template <> struct rounded_math<float>; | |
691 | template <> struct rounded_math<double>; | |
692 | template <> struct rounded_math<long double>; | |
693 | ||
694 | <span style= | |
695 | "color: #FF0000">/* built-in rounding construction blocks */</span> | |
696 | template <class T> struct rounding_control; | |
697 | ||
698 | template <class T, class Rounding = rounding_control<T> > struct rounded_arith_exact; | |
699 | template <class T, class Rounding = rounding_control<T> > struct rounded_arith_std; | |
700 | template <class T, class Rounding = rounding_control<T> > struct rounded_arith_opp; | |
701 | ||
702 | template <class T, class Rounding> struct rounded_transc_dummy; | |
703 | template <class T, class Rounding = rounded_arith_exact<T> > struct rounded_transc_exact; | |
704 | template <class T, class Rounding = rounded_arith_std <T> > struct rounded_transc_std; | |
705 | template <class T, class Rounding = rounded_arith_opp <T> > struct rounded_transc_opp; | |
706 | ||
707 | template <class Rounding> struct save_state; | |
708 | template <class Rounding> struct save_state_nothing; | |
709 | ||
710 | <span style="color: #FF0000">/* built-in checking policies */</span> | |
711 | template <class T> struct checking_base; | |
712 | template <class T, class Checking = checking_base<T>, class Exception = exception_create_empty> struct checking_no_empty; | |
713 | template <class T, class Checking = checking_base<T> > struct checking_no_nan; | |
714 | template <class T, class Checking = checking_base<T>, class Exception = exception_invalid_number> struct checking_catch_nan; | |
715 | template <class T> struct checking_strict; | |
716 | ||
717 | <span style= | |
718 | "color: #FF0000">/* some metaprogramming to manipulate interval policies */</span> | |
719 | template <class Rounding, class Checking> struct policies; | |
720 | template <class OldInterval, class NewRounding> struct change_rounding; | |
721 | template <class OldInterval, class NewChecking> struct change_checking; | |
722 | template <class OldInterval> struct unprotect; | |
723 | ||
724 | <span style= | |
725 | "color: #FF0000">/* constants, need to be explicitly templated */</span> | |
726 | template<class I> I pi(); | |
727 | template<class I> I pi_half(); | |
728 | template<class I> 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 <class T, class Policies> bool cerlt(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
735 | template <class T, class Policies> bool cerlt(const interval<T, Policies>& x, const T& y); | |
736 | template <class T, class Policies> bool cerlt(const T& x, const interval<T, Policies>& y); | |
737 | ||
738 | template <class T, class Policies> bool cerle(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
739 | template <class T, class Policies> bool cerle(const interval<T, Policies>& x, const T& y); | |
740 | template <class T, class Policies> bool cerle(const T& x, const interval<T, Policies>& y); | |
741 | ||
742 | template <class T, class Policies> bool cergt(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
743 | template <class T, class Policies> bool cergt(const interval<T, Policies>& x, const T& y); | |
744 | template <class T, class Policies> bool cergt(const T& x, const interval<T, Policies>& y); | |
745 | ||
746 | template <class T, class Policies> bool cerge(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
747 | template <class T, class Policies> bool cerge(const interval<T, Policies>& x, const T& y); | |
748 | template <class T, class Policies> bool cerge(const T& x, const interval<T, Policies>& y); | |
749 | ||
750 | template <class T, class Policies> bool cereq(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
751 | template <class T, class Policies> bool cereq(const interval<T, Policies>& x, const T& y); | |
752 | template <class T, class Policies> bool cereq(const T& x, const interval<T, Policies>& y); | |
753 | ||
754 | template <class T, class Policies> bool cerne(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
755 | template <class T, class Policies> bool cerne(const interval<T, Policies>& x, const T& y); | |
756 | template <class T, class Policies> bool cerne(const T& x, const interval<T, Policies>& y); | |
757 | ||
758 | template <class T, class Policies> bool poslt(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
759 | template <class T, class Policies> bool poslt(const interval<T, Policies>& x, const T& y); | |
760 | template <class T, class Policies> bool poslt(const T& x, const interval<T, Policies>& y); | |
761 | ||
762 | template <class T, class Policies> bool posle(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
763 | template <class T, class Policies> bool posle(const interval<T, Policies>& x, const T& y); | |
764 | template <class T, class Policies> bool posle(const T& x, const interval<T, Policies>& y); | |
765 | ||
766 | template <class T, class Policies> bool posgt(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
767 | template <class T, class Policies> bool posgt(const interval<T, Policies>& x, const T& y); | |
768 | template <class T, class Policies> bool posgt(const T& x, const interval<T, Policies> & y); | |
769 | ||
770 | template <class T, class Policies> bool posge(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
771 | template <class T, class Policies> bool posge(const interval<T, Policies>& x, const T& y); | |
772 | template <class T, class Policies> bool posge(const T& x, const interval<T, Policies>& y); | |
773 | ||
774 | template <class T, class Policies> bool poseq(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
775 | template <class T, class Policies> bool poseq(const interval<T, Policies>& x, const T& y); | |
776 | template <class T, class Policies> bool poseq(const T& x, const interval<T, Policies>& y); | |
777 | ||
778 | template <class T, class Policies> bool posne(const interval<T, Policies>& x, const interval<T, Policies>& y); | |
779 | template <class T, class Policies> bool posne(const interval<T, Policies>& x, const T& y); | |
780 | template <class T, class Policies> bool posne(const T& x, const interval<T, Policies>& 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] < [c,d] to be !([a,b] >= [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><</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 <= b</code> and | |
945 | <code>&b == &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é Brö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é have | |
963 | provided some useful comments in order for this library to be written. | |
964 | Hervé 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 © 2002 Guillaume Melquiond, Sylvain Pion, Hervé | |
982 | Brönnimann, Polytechnic University<br> | |
983 | Copyright © 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> |