= 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].

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