search

ekmett / intervals

Interval Arithmetic
http://hackage.haskell.org/package/intervals
BSD 2-Clause "Simplified" License
27 stars 13 forks source link

kaucher multiplication #38

Open comius opened 9 years ago

comius commented 9 years ago

Do you realize current multiplication is not really Kaucher? (Except on proper intervals?)

dmcclean commented 9 years ago

Current definition for reference:

  I a b * I a' b' =
    minimum [a * a', a * b', b * a', b * b']
    ...
    maximum [a * a', a * b', b * a', b * b']
  {-# INLINE (*) #-}

I still don't honestly understand what the Kaucher semantics are supposed to be or exactly when they are useful, so I can't comment on whether comius is right or what it should say instead.

comius, if you are feeling ambitious it would be awesome if we had more doctests / quickcheck properties for the Kaucher module like we have for the NonEmpty module, because it would help explain how it's meant to work.

dmcclean commented 9 years ago

See http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=17E479E72606E7C7DDA2897EEF6308B4?doi=10.1.1.134.6947&rep=rep1&type=pdf#4

definition

It looks like comius is correct, unless the current definition is clever in a way that I don't see. Although the definition in (10) doesn't seem to cover all cases(?), because I don't see where it matches if either a+ = a- or b+ = b-.

comius commented 9 years ago

Wow, that's a fast reply. Basically I was looking for a good/better implementation - to find this out. Most implementations I've seen are split into 16 cases that aren't really appealing - described in [1] - also original Kaucher article is the same . The formulas you cited give three quite complicated cases, and there are another formulas you can find on page 47 in [2] called Lakeyev formulas. They are simple but I guess need to be optimized for multiplication with zero.

[1] http://www.paultaylor.eu/ASD/dedras/multiplication [2] http://www.sbras.ru/interval/shary/Papers/ANewTech.pdf

dmcclean commented 9 years ago

Yikes, the 16 cases really aren't appealing. But unappealing and correct has something going for it. The ones in [2] seem to be correct because of algebraic properties of arithmetic on the underlying scalar type, which could possibly be problematic if the scalar type is approximate?

ekmett commented 9 years ago

Seems like * is flawed then.