240
edits
Interval package: Difference between revisions
m
Removed dependency to fenv package
(→What to expect: Removed fenv package) |
m (Removed dependency to fenv package) |
||
| Line 1: | Line 1: | ||
The [https://sourceforge.net/p/octave/interval/ interval package] provides data types and fundamental operations for real valued interval arithmetic based on the common floating-point format “binary64” a. k. a. double-precision. It aims to be standard compliant with the (upcoming) [http://standards.ieee.org/develop/project/1788.html IEEE 1788] and therefore implements the ''set-based'' interval arithmetic flavor. '''Interval arithmetic''' produces mathematically proven numerical results. | The [https://sourceforge.net/p/octave/interval/ interval package] provides data types and fundamental operations for real valued interval arithmetic based on the common floating-point format “binary64” a. k. a. double-precision. It aims to be standard compliant with the (upcoming) [http://standards.ieee.org/develop/project/1788.html IEEE 1788] and therefore implements the ''set-based'' interval arithmetic flavor. '''Interval arithmetic''' produces mathematically proven numerical results. | ||
Warning: The package has not yet been released. If you want to experience the development version, you may (1 | Warning: The package has not yet been released. If you want to experience the development version, you may (1) download a [https://sourceforge.net/p/octave/interval/ci/default/tarball snapshot version of the interval package], (2) install the [http://www.mpfr.org/mpfr-current/#download development library of MPFR] for your system, (3) execute <code>make install</code> in the <code>src/</code> subfolder, (5) navigate to the <code>inst/</code> subfolder and run octave. | ||
== Motivation == | == Motivation == | ||
| Line 46: | Line 46: | ||
''Why is the interval package slow?'' | ''Why is the interval package slow?'' | ||
All arithmetic interval operations are simulated in high-level octave language using C99 floating-point routines, which is a lot slower than hardware implementations [https://books.google.de/books?id=JTc4XdXFnQIC&pg=PA61]. Building interval arithmetic operations from floating-point routines is easy for simple monotonic functions, e. g., addition and subtraction, but is complex for others, e. g., [http://exp.ln0.de/heimlich-power-2011.htm interval power function], atan2, or [[#Reverse_arithmetic_operations|reverse functions]]. For some interval operations it is not even possible to rely on floating-point routines, since not all required routines are available in C99 or BLAS | All arithmetic interval operations are simulated in high-level octave language using C99 floating-point routines or multi-precision floating-point routines, which is a lot slower than hardware implementations [https://books.google.de/books?id=JTc4XdXFnQIC&pg=PA61]. Building interval arithmetic operations from floating-point routines is easy for simple monotonic functions, e. g., addition and subtraction, but is complex for others, e. g., [http://exp.ln0.de/heimlich-power-2011.htm interval power function], atan2, or [[#Reverse_arithmetic_operations|reverse functions]]. For some interval operations it is not even possible to rely on floating-point routines, since not all required routines are available in C99 or BLAS. | ||
Great algorithms and optimizations exist for matrix arithmetic in GNU octave. Good interval versions of these still have to be found and implemented. | Great algorithms and optimizations exist for matrix arithmetic in GNU octave. Good interval versions of these still have to be found and implemented. | ||
| Line 55: | Line 53: | ||
Some basic operations are provided by the C library on common platforms with directed rounding and correctly rounded result: plus, minus, division, multiplication and square root. All other GNU Octave arithmetic functions are not guaranteed to produce accurate results, because they are based on C99 floating-point routines [http://www.gnu.org/software/libc/manual/html_node/Errors-in-Math-Functions.html#Errors-in-Math-Functions]. Their results depend on hardware, system libraries and compilation options. | Some basic operations are provided by the C library on common platforms with directed rounding and correctly rounded result: plus, minus, division, multiplication and square root. All other GNU Octave arithmetic functions are not guaranteed to produce accurate results, because they are based on C99 floating-point routines [http://www.gnu.org/software/libc/manual/html_node/Errors-in-Math-Functions.html#Errors-in-Math-Functions]. Their results depend on hardware, system libraries and compilation options. | ||
The interval package handles all functions with the help of the [http://www.mpfr.org/ GNU MPFR library]. With MPFR it is possible to compute system-independent, valid and tight enclosures of the correct results. | The interval package handles all arithmetic functions with the help of the [http://www.mpfr.org/ GNU MPFR library]. With MPFR it is possible to compute system-independent, valid and tight enclosures of the correct results. | ||
== Quick start introduction == | == Quick start introduction == | ||
| Line 220: | Line 218: | ||
octave:1> sin (infsup (0.5)) | octave:1> sin (infsup (0.5)) | ||
ans ⊂ [.47942553860420294, . | ans ⊂ [.47942553860420294, .47942553860420301] | ||
octave:2> pow (infsup (2), infsup (3, 4)) | octave:2> pow (infsup (2), infsup (3, 4)) | ||
ans = [8, 16] | ans = [8, 16] | ||
octave:3> atan2 (infsup (1), infsup (1)) | octave:3> atan2 (infsup (1), infsup (1)) | ||
ans ⊂ [. | ans ⊂ [.7853981633974482, .7853981633974484] | ||
=== Reverse arithmetic operations === | === Reverse arithmetic operations === | ||
| Line 233: | Line 231: | ||
In the following example, we compute the constraints for base and exponent of the power function <code>pow</code> as shown in the figure. | In the following example, we compute the constraints for base and exponent of the power function <code>pow</code> as shown in the figure. | ||
octave:1> x = powrev1 (infsup ("[1.1, 1.45]"), infsup (2, 3)) | octave:1> x = powrev1 (infsup ("[1.1, 1.45]"), infsup (2, 3)) | ||
x ⊂ [1. | x ⊂ [1.6128979635153646, 2.7148547265657915] | ||
octave:2> y = powrev2 (infsup ("[2.14, 2.5]"), infsup (2, 3)) | octave:2> y = powrev2 (infsup ("[2.14, 2.5]"), infsup (2, 3)) | ||
y ⊂ [. | y ⊂ [.7564707973660299, 1.4440113978403284] | ||
=== Numerical operations === | === Numerical operations === | ||
| Line 251: | Line 249: | ||
Above mentioned operations can also be applied element-wise to interval vectors and matrices. Many operations use [http://www.gnu.org/software/octave/doc/interpreter/Vectorization-and-Faster-Code-Execution.html#Vectorization-and-Faster-Code-Execution vectorization techniques]. | Above mentioned operations can also be applied element-wise to interval vectors and matrices. Many operations use [http://www.gnu.org/software/octave/doc/interpreter/Vectorization-and-Faster-Code-Execution.html#Vectorization-and-Faster-Code-Execution vectorization techniques]. | ||
In addition, there are matrix operations on interval matrices. These operations comprise: tight | In addition, there are matrix operations on interval matrices. These operations comprise: tight dot product, tight matrix multiplication, tight vector sums, matrix inversion, matrix powers, and solving linear systems. As a result of missing hardware / low-level library support and missing optimizations, these operations are quite slow compared to familiar operations in floating-point arithmetic. | ||
octave:1> A = infsup ([1, 2, 3; 4, 0, 0; 0, 0, 1]); A (2, 3) = "[0, 6]" | octave:1> A = infsup ([1, 2, 3; 4, 0, 0; 0, 0, 1]); A (2, 3) = "[0, 6]" | ||