Interval_intel
Interval library in OCaml. ONLY FOR INTEL PROCESSORS.
All operations use correct rounding.
It is recommended to open this module. It will put into scope the interval type and a module I
(see Interval
.I) containing interval operations:
open Interval_intel
let x = I.(v 0.5 1. + sin(v 3. 3.125))
When the module I
is open, the integer operators (+
, -
,...) and the floating point ones (+.
, -.
,...) are redefined. If, in the middle of an expression, you need to use the usual operators, locally open the module I.U
as in I.(x /. U.(float(n + 1)))
.
The names symbols for infix operators have been chosen to try to make the standard cases short and the overall expression readable. The rationale is as follows.
+
, -
, *
, /
, ~-
and ~+
act on intervals;+.
, -.
, /.
take an interval to the left and a float to the right, but *.
does the opposite. This is to match the standard presentation of polynomials. Example: I.(3. *. x**2 + 2. *. x +. 4.)
. WARNING: you should only use these functions when the float argument represent the exact mathematical value (taking into account that the compiler will round literals). For example, 42.
is fine while 0.1
is not (because it has an infinite binary representation).+:
, -:
, *:
and /:
are as in the previous point but with the interval and float swapped. Note that +:
and *:
are not really needed because the operations are commutative but are present for consistency.**
has been chosen for integer exponent because they are the more frequent, **.
when the exponent is a float, **:
when the base is a float and ***
for exponentiation of two intervals.You do not have to worry about remembering these rules. The type system will enforce them.
It is not mandatory, but still wise, to read the documentation of the Fpu
module.
This library has been mainly designed to be used in a branch and bound optimization algorithm. So, some choices have been made:
{low=2.;high=3.} /
{low=0.;high=2.}
returns {low=1.;high=Inf}
, while {low=2.;high=3.} / {low=0.;high=0.}
or {low=0.;high=0.} /
{low=0.;high=0.}
raises Interval_base.Division_by_zero
.log
, sqrt
, acos
or asin
are restricted to their definition domain but raise an exception rather than returning an empty interval: for example sqrt {low=-4;high=4}
returns {low=0;high=2}
while sqrt {low=-4;high=-2}
will raise an exception.Another design choice was to have non mutable elements in interval structure, and to maintain an "ordinary" syntax for operations, such as let a = b + c in ...
thus mapping interval computation formula on airthmetic formula. We could have instead chosen to have mutable elements, and to write for example (Interval.add a b c
) to perform “a ← b + c”. The first choice is, to our point of view, more elegant and easier to use. The second is more efficient, especially when computing functions with many temporary results, which force the GC to create and destroy lot of intervals when using the implementation we chose. Nothing's perfect.
The older deprecated interface is still available.
The library is implemented in x87 assembly mode and is quite efficient (see below).
type interval = Interval_base.interval = {
low : float; | (* lower bound, possibly = -∞ *) |
high : float; | (* higher bound, possibly = +∞ *) |
}
The interval type. Be careful however when creating intervals. For example, the following code: let a = {low=1./.3.; high=1./.3.}
creates an interval which does NOT contain the mathematical object 1/3.
If you want to create an interval representing 1/3, you have to write let a = I.(inv(v 3. 3.))
because rounding will then be properly handled by I.inv
and the resulting interval will indeed contain the exact value of 1/3.
module I : sig ... end
Interval operations. Locally open this module — using e.g. I.(...)
— to redefine classical arithmetic operators for interval arithmetic.
module Fpu : sig ... end
Access to low level floating point functions. THIS LIBRARY ONLY WORKS FOR INTEL PROCESSORS.
module RoundDown = Fpu.RoundDown
module RoundUp = Fpu.RoundUp
module Low = RoundDown
module High = RoundUp
The functions below are the ones of the older versions of Interval
. They will soon be removed.
type t = interval
val zero_I : interval
Neutral element for addition
val one_I : interval
Neutral element for multiplication
val pi_I : interval
pi
with bounds properly rounded
val e_I : interval
e
with bounds properly rounded
val printf_I :
( float -> string, unit, string ) Stdlib.format ->
interval ->
unit
Prints an interval with the same format applied to both endpoints. Formats follow the same specification than the one used for the regular printf function
val fprintf_I :
Stdlib.out_channel ->
( float -> string, unit, string ) Stdlib.format ->
interval ->
unit
Prints an interval into an out_channel with the same format applied to both endpoints
val sprintf_I :
( float -> string, unit, string ) Stdlib.format ->
interval ->
string
Returns a string holding the interval printed with the same format applied to both endpoints
val float_i : int -> interval
Returns the interval containing the float conversion of an integer
val compare_I_f : interval -> float -> int
compare_I_f a x
returns 1
if a.high<x
, 0
if a.low<=x<=a.high
and -1
if x<a.low
val size_I : interval -> float
size_I a
returns a.high-a.low
sgn a
returns {low=float (compare a.low 0.);high=float
(compare a.high 0.)}
abs_I a
returns {low=a.low;high=a.high}
if a.low>=0.
, {low=-a.high;high=-a.low}
if a.high<=0.
, and {low=0.;high=max -a.low a.high}
otherwise
union_I_I a b
returns {low=min a.low b.low; high=max a.high b.high}
max_I_I a b
returns {low=max a.low b.low; high=max a.high b.high}
min_I_I a b
returns {low=min a.low b.low; high=min a.high b.high}
a *$. x
multiplies a
by x
according to interval arithmetic and returns the proper result. If x=0.
then zero_I
is returned
x *$. a
multiplies a
by x
according to interval arithmetic and returns the proper result. If x=0.
then zero_I
is returned.
a *$ b
multiplies a
by b
according to interval arithmetic and returns the proper result. If a=zero_I
or b=zero_I
then zero_I
is returned
a /$. x
divides a
by x
according to interval arithmetic and returns the proper result. Raise Failure "/$."
if x=0.
x /.$ a
divides x
by a
according to interval arithmetic and returns the result. Raise Failure "/.$"
if a=zero_I
a /$ b
divides the first interval by the second according to interval arithmetic and returns the proper result. Raise Failure "/$"
if b=zero_I
mod_I_f a f
returns a
mod f
according to interval arithmetic et OCaml mod_float definition. Raise Failure
"mod_I_f"
if f=0.
sqrt_I a
returns {low=sqrt a;high=sqrt b}
if a>=0.
, {low=0.;high=sqrt b}
if a<0.<=b
. Raise Failure "sqrt_I"
if b<0.
Pow_I_i a n
with n
integer returns interval a
raised to nth power according to interval arithmetic. If n=0
then {low=1.;high=1.}
is returned. Raise Failure "pow_I_f"
if n<=0
and a=zero_I
. Computed with exp-log in base2.
a **$. f
returns interval a
raised to f power according to interval arithmetic. If f=0.
then {low=1.;high=1.}
is returned. Raise Failure "**$."
if f<=0. and a=zero_I
or if f is not an integer value and a.high<0.
. Computed with exp-log in base2.
a **$ b
returns interval a
raised to b
power according to interval arithmetic, considering the restriction of x power y to x >= 0. Raise Failure "**$"
if a.high < 0
or (a.high=0. and
b.high<=0.)
x **.$ a
returns float x
raised to interval a
power according to interval arithmetic, considering the restiction of x power y to x >= 0. Raise Failure "**.$"
if x < 0
and a.high <= 0
log_I a
returns {low=log a.low; high=log a.high}
if a.low>0.
, {low=neg_infinity; high=log a.high}
if a.low<0<=a.high
. Raise Failure "log_I"
if a.high<=0.
cos_I a
returns the proper extension of cos to arithmetic interval Returns [-1,1] if one of the bounds is greater or lower than +/-2**53
sin_I a
returns the proper extension of sin to arithmetic interval Returns [-1,1] if one of the bounds is greater or lower than +/-2**53
tan_I a
returns the proper extension of tan to arithmetic interval Returns [-Inf,Inf] if one of the bounds is greater or lower than +/-2**53
acos_I a
raise Failure "acos_I"
if a.low>1. or a.high<-1.
, else returns {low=if a.high<1. then acos a.high else 0;
high=if a.low>-1. then acos a.low else pi}
. All values are in [0,pi].
asin_I a
raise Failure "asin_I"
if a.low>1. or a.high<-1.
else returns {low=if a.low>-1. then asin a.low else -pi/2;
high=if a.low<1. then asin a.high else pi/2}
. All values are in [-pi/2,pi/2].
atan2mod_I_I y x
returns the proper extension of interval arithmetic to atan2 but with values in [-pi,2 pi] instead of [-pi,pi]. This can happen when y.low<0 and y.high>0 and x.high<0: then the returned interval is {low=atan2 y.high
x.high;high=(atan2 y.low x.high)+2 pi}
. This preserves the best inclusion function possible but is not compatible with the standard definition of atan2
Same function as above but when y.low<0 and y.high>0 and x.high<0 the returned interval is [-pi,pi]. This does not preserve the best inclusion function but is compatible with the atan2 regular definition
val size_max_X : interval array -> float
Computes the size of the largest interval of the interval vector
val size_mean_X : interval array -> float
Computes the mean of the size of intervals of the interval vector
val printf_X :
( float -> string, unit, string ) Stdlib.format ->
interval array ->
unit
Prints an interval vector with the same format applied to all endpoints.
val fprintf_X :
Stdlib.out_channel ->
( float -> string, unit, string ) Stdlib.format ->
interval array ->
unit
Prints an interval vector into an out_channel with the same format applied to all endpoints
val sprintf_X :
( float -> string, unit, string ) Stdlib.format ->
interval array ->
string
Returns a string holding the interval vector printed with the same format applied to all endpoints
val print_X : interval array -> unit
Deprecated
val print_I : interval -> unit
Deprecated
val size_X : interval array -> float
Deprecated
val size2_X : interval array -> float
Deprecated
val (<$.) : interval -> float -> int
Deprecated
Intel Atom 230 Linux 32 bits:
ftan
speed (10000000 calls): 2.528158fcos
speed (10000000 calls): 2.076129fsin
speed (10000000 calls): 1.972123I.tan
speed (10000000 calls): 4.416276I.cos
speed (10000000 calls): 4.936308I.sin
speed (10000000 calls): 5.396338fadd
speed (10000000 calls): 0.980062fsub
speed (10000000 calls): 0.980061fmul
speed (10000000 calls): 0.980061fdiv
speed (10000000 calls): 1.424089I.( + )
speed (10000000 calls): 1.656103I.( - )
speed (10000000 calls): 1.636103I.( * )
speed (10000000 calls): 4.568285I.( / )
speed (10000000 calls): 4.552285Intel 980X Linux 64 bits:
ftan
speed (10000000 calls): 0.472029fcos
speed (10000000 calls): 0.400025fsin
speed (10000000 calls): 0.400025I.tan
speed (10000000 calls): 0.752047I.cos
speed (10000000 calls): 1.036065I.sin
speed (10000000 calls): 1.104069fadd
speed (10000000 calls): 0.124008fsub
speed (10000000 calls): 0.120008fmul
speed (10000000 calls): 0.128008fdiv
speed (10000000 calls): 0.156010I.( + )
speed (10000000 calls): 0.340021I.( - )
speed (10000000 calls): 0.332021I.( * )
speed (10000000 calls): 0.556035I.( / )
speed (10000000 calls): 0.468029