Interval package: Difference between revisions

772 bytes added ,  18 January 2015
m
→‎What to expect: Added runtime information
m (→‎Motivation: Added bullet: System dependent results)
m (→‎What to expect: Added runtime information)
Line 51: Line 51:


''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 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.
All arithmetic interval operations are simulated in high-level octave language using C99 or multi-precision floating-point routines, which is a lot slower than a hardware implementation [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 floating-point matrix arithmetic in GNU Octave. Good interval versions of these still have to be found and implemented. For example, multiplication of matrices with many elements becomes unfeasible as it takes a lot of time. (For that purpose one could use the [[#Related work|INTLAB toolbox]], which uses a less accurate arithmetic)
 
{| class="wikitable" style="margin: auto; align:right"
|+align="bottom" | Approximate runtime (wall clock time in seconds) on an Intel® Core™ i5-4340M CPU
!Matrix dimension
!Interval <code>plus</code>
!Interval <code>log</code>
!Interval <code>mtimes</code>
!Interval <code>inv</code>
|-
|align="right"| 10
|align="right"| < 0.1
|align="right"| < 0.1
|align="right"| 0.4
|align="right"| 3.3
|-
|align="right"| 20
|align="right"| < 0.1
|align="right"| < 0.1
|align="right"| 2.3
|style="text-align:right; font-weight: bold; color:orange"| 32.3
|-
|align="right"| 30
|align="right"| < 0.1
|align="right"| < 0.1
|align="right"| 7.0
|style="text-align:right; font-weight: bold; color:red"| 142.1
|-
|align="right"| 40
|align="right"| < 0.1
|align="right"| 0.1
|align="right"| 15.6
|-
|align="right"| 50
|align="right"| 0.1
|align="right"| 0.2
|style="text-align:right; font-weight: bold; color:orange"| 29.1
|}


''Why is the interval package accurate?''
''Why is the interval package accurate?''
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 GNU Octave builtin floating-point routines are not useful for interval arithmetic: Their results depend on hardware, system libraries and compilation options.  


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.
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.
240

edits