[Haskell-cafe] Re: Interval Arithmetics
Al Falloon
afalloon at synopsys.com
Fri Aug 10 11:45:08 EDT 2007
Mitar wrote:
> Hi!
>
> First, disclaimer: everything I know about interval arithmetics comes
> from this video:
>
> http://video.google.com/videoplay?docid=-2285617608766742834
The discussion in the implementation of the Boost Interval Arithmetic
Library is also useful.
http://www.boost.org/libs/numeric/interval/doc/interval.htm
>
> I would like to know if there is any implementation of interval
> arithmetics in Haskell? I would like to play a little with that. I
> checked the web and the straightforward approach I found:
>
> http://cs.guc.edu.eg/faculty/sabdennadher/Publikationen/paper-wflp99.ps.gz
>
> has from my point of view invalid implementation. For example, lower
> bound in the sum should not be just calculated as the sum of lower
> bounds of summands. It should return the greatest representable number
> which is smaller or equal to the exact value of the sum. With just
> boldly making a sum we ignore any errors we could introduce and this
> is somehow against the idea of interval arithmetics.
Correct.
>
> And as it is said at the end of the talk, a system behind interval
> arithmetics should do a lot of work to make those intervals as small
> as possible while still correct and counting in all the errors we
> accumulated.
>
> I think a strict-typed and lazy language like Haskell would be a good
> place to implement this. But I would like to know if this would be
> possible to do from the language itself, without making changes to the
> compiler and/or runtime itself? Because, for example, a good
> implementation should reformulate equations at the runtime accordingly
> to exact values it wants to compute them on.
For intervals of floating point numbers you will need to gain access to
the FPU rounding modes for the machine (see some discussion here
http://www.boost.org/libs/numeric/interval/doc/rounding.htm). I don't
think that that is provided in the basic libraries so you would need to
use the FFI to get it from C. And proper rounding isn't available on all
platforms.
For unbounded values defined in Haskell (like Integer and Rational) you
need to provide round-down and round-up versions of operations that
won't produce exact answers (like division on Integer and sqrt on
Rational). Probably some sort of clever type-class setup could be used
to provide rounding functions for intervals (the same way Ix does clever
indexing for Array).
> Has it been done already?
Sorry, not that I know of.
More information about the Haskell-Cafe
mailing list