intervals

= Intervals -- Interval arithmetic in Ruby

Besides making obvious a possible loss of precision during floating point calculations, interval arithmetic provides not-so-conventional methods for a variety of computational applications.

This library implements an interval system in the extended real set that is closed under arithmetic operations. Correct rounding ensures that the operations are inclusion-wise monotonic.

== Introduction

Fire up ruby's interactive shell by typing

irb

on the command line. Take into consideration the rather innocent looking function

def f(x,y) (333.75-x2)* y6 + x2 * (11* x2 * y2-121 * y4 -2) + 5.5 * y**8 + x/(2*y) end

We can calculate it for some specific +x+ and +y+,

f(77617.0,33096.0) # => 1.17260394005318

There is only one problem: this result is WRONG. The correct result can be obtained by calculating separately the numerator and denominator of +f+ using integer arithmetic.

def f_num(x,y) ((33375- 100 * x2)* y6 + 100 * x2 * (11* x2 * y2-121 * y4 -2) + 550 * y**8) * 2*y + 100 *x end

def f_den(x,y) 200*y end

f_num(77617, 33096).to_f / f_den(77617, 33096).to_f # => -0.827396059946821

The result obtained by directly calculating +f+ is completely wrong: sign, order of magnitude, and all digits are wrong. No warnings, no errors are generated, but the computation simply yields unreliable results.

Using interval arithmetic it is possible to detect the loss of precision due to floating-point roundings.

require "interval" # See below if the library isn't installed yet

1/Interval[3.0] # => Interval[0.333333333333333, 0.333333333333333]

yields an interval that is very sharp. Its width

(1/Interval[3.0]).width # => 5.55111512312578e-17

corresponds to one bit in the least significant position. We cannot do any-better with floating point operations. But if we calculate +f+ with intervals we obtain

f(Interval[77617.0], Interval[33096.0]) # => Interval[-2.36118324143482e+21, 1.18059162071741e+21]

The result has an uncertainity of the order of 10 to the power of 21 !

== Cool Applications

Obviously, interval arithmetics allows us to detect whenever floating-point calculations become unreliable. But it also has other interesting applications.

Finding all solutions of an equation that fall into an interval, for instance. Take the equation

x**3 == x

We rewrite it first in the form

x**3 - x == 0

The left-hand side of this equation has derivative

3* x**2 - 1

To find all solutions in [-100,100] we do

Interval[-100,100].newton(proc {|x| x3 - x}, proc {|x| 3* x2 - 1}) # => Interval[[-1.0], [-0.0], [1.0]]

which shows that the equation has the three solutions -1, 0, and +1.

== Intervals in Ruby

An Interval can be created starting from a number

a = Interval[3] # Or, in alternative, as b = 3.to_interval # equivalent to above a == b # => true

An Interval can also be created from a pair of numbers that represent its lower and upper bounds:

c = Interval[1,2] # In mathematical notation: [1,2] c.include?(1.5) # => true c.include?(0) # => false c.include?(3) # => false

The interval is closed, i.e., it includes its bounds:

c.include?(1) # => true c.include?(2) # => true

An interval can be unbounded, i.e., one or both of its extrema are infinite:

d = Interval[5,Infinity] # includes all reals > 1 d.include?(Infinity) # => true d.width # => Infinity

An interval can have more than one connected components:

e = Interval[[1,2],[3,4]] # The set {x | 1<= x <= 2 or 3 <= x <= 4}

This way, the set of intervals is closed under set union

a | c # => Interval[[1, 2], [3]]

The intersection is also well-defined on intervals

Interval[1,3] & Interval[2,4] # => Interval[2, 3]

All arithmetic operations are defined on intervals

a + c # => Interval[4, 5] 3 + Interval[1,2] # equivalent to above a * c # => Interval[3, 6] (a | c) + a * c # => Interval[4, 9] (-c) ** 2 # => Interval[1, 4] 1 / a # => Interval[0.333333333333333, 0.333333333333333]

Note that the rounding is consistent with the arithmetic operations. If we look into bits of the result of the last operation, we see that sup is inf plus one bit in the least significant position:

(1/a).inf.to_struct # => Struct::Float[1, 1021, 1501199875790165] (1/a).sup.to_struct # => Struct::Float[1, 1021, 1501199875790166] (1/a).width # => 5.55111512312578e-17 (1/a).width == 2 ** -54 # => true

We say that 1/a is sharp

(1/a).sharp? # => true

== Installation

This project is hosted on RubyForge[http://rubyforge.org/projects/intervals] and you can browse its documentation[http://intervals.rubyforge.org] on-line.

The installation is trivial with RubyGems[http://docs.rubygems.org/]: just type

gem install --remote intervals

on the command-line. In alternative, you can manually download the library[http://rubyforge.org/frs/?group_id=1458] and compile the C extensions

ruby extconf.rb make

You can also browse the project SCM repository[http://rubyforge.org/plugins/scmsvn/viewcvs.php/trunk?root=intervals].

== Testing

A testsuite is included with the library, which can be run from within ruby:

require 'interval' Test::Unit::AutoRunner.run

== References

Eldon Hansen, G. William Walster, {Global Optimization Using Interval Analysis}[http://www.ebooks.dekker.com/eBookCover.asp?eBookID=0824758706&type=ISBN] - Second Edition, Revised and Expanded. John Dekker, Inc., 2003.

David Goldberg, {What Every Computer Scientist Should Know About Floating-Point Arithmetic}[http://docs-pdf.sun.com/800-7895/800-7895.pdf], ACM Computing Surveys, vol. 23 (1991), pp. 5--48.

== Author & License

Copyright (c) 2006, Stefano Taschini.

You can reach me using the concact information provided in http://www.taschini.net/contact .

This work is licensed under the terms of LGPL[http://www.gnu.org/copyleft/lesser.html].

Correctly-rounded transcendetal functions are computed using CRlibm[http://lipforge.ens-lyon.fr/www/crlibm/], which is developed at the {ENS Lyon}[http://www.ens-lyon.fr/LIP/] and is also released under the terms of LGPL.

RDoc template by {Jamis Buck}[http://rubyforge.org/frs/?group_id=1458].