= 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-x**2)* y**6 + x**2 * (11* x**2 * y**2-121 * y**4 -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 * x**2)* y**6 +
100 * x**2 * (11* x**2 * y**2-121 * y**4 -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| x**3 - x}, proc {|x| 3* x**2 - 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 | 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, 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, 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 Lyon[http://www.ens-lyon.fr/LIP/] and is also released
under the terms of LGPL.

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