math-functions-0.3.4.4: Collection of tools for numeric computations

Copyright | (c) 2014 Bryan O'Sullivan
License | BSD3
Maintainer | bos@serpentine.com
Stability | experimental
Portability | portable
Safe Haskell | None
Language | Haskell2010

Numeric.Sum

Contents

- Summation type class
  - Usage
- Kahan-Babuška-Neumaier summation
- Order-2 Kahan-Babuška summation
- Less desirable approaches
  - Kahan summation
  - Pairwise summation
- References

Description

Functions for summing floating point numbers more accurately than the naive `sum` function and its counterparts in the `vector` package and elsewhere.

When used with floating point numbers, in the worst case, the `sum` function accumulates numeric error at a rate proportional to the number of values being summed. The algorithms in this module implement different methods of /compensated summation/, which reduce the accumulation of numeric error so that it either grows much more slowly than the number of inputs (e.g. logarithmically), or remains constant.

Synopsis

- class Summation s where
  - zero :: s
  - add :: s -> Double -> s
  - sum :: Foldable f => (s -> Double) -> f Double -> Double
- sumVector :: (Vector v Double, Summation s) => (s -> Double) -> v Double -> Double
- data KBNSum = KBNSum !Double !Double
- kbn :: KBNSum -> Double
- data KB2Sum = KB2Sum !Double !Double !Double
- kb2 :: KB2Sum -> Double
- data KahanSum = KahanSum !Double !Double
- kahan :: KahanSum -> Double
- pairwiseSum :: Vector v Double => v Double -> Double

# Summation type class

class Summation s where Source #

A class for summation of floating point numbers.

Minimal complete definition

zero, add

Methods

zero :: s Source #

The identity for summation.

add :: s -> Double -> s Source #

Add a value to a sum.

sum :: Foldable f => (s -> Double) -> f Double -> Double Source #

Sum a collection of values.

Example: `foo = `sum` `kbn` [1,2,3]`

#### Instances

Instances details

Summation KB2Sum Source # |
Instance details Defined in Numeric.Sum Methods zero :: KB2Sum Source # add :: KB2Sum -> Double -> KB2Sum Source # sum :: Foldable f => (KB2Sum -> Double) -> f Double -> Double Source #
Summation KBNSum Source # |
Instance details Defined in Numeric.Sum Methods zero :: KBNSum Source # add :: KBNSum -> Double -> KBNSum Source # sum :: Foldable f => (KBNSum -> Double) -> f Double -> Double Source #
Summation KahanSum Source # |
Instance details Defined in Numeric.Sum Methods zero :: KahanSum Source # add :: KahanSum -> Double -> KahanSum Source # sum :: Foldable f => (KahanSum -> Double) -> f Double -> Double Source #
Summation Double Source # |
Instance details Defined in Numeric.Sum Methods zero :: Double Source # add :: Double -> Double -> Double Source # sum :: Foldable f => (Double -> Double) -> f Double -> Double Source #

sumVector :: (Vector v Double, Summation s) => (s -> Double) -> v Double -> Double Source #

O(n) Sum a vector of values.

## Usage

Most of these summation algorithms are intended to be used via the `Summation` typeclass interface. Explicit type annotations should not be necessary, as the use of a function such as `kbn` or `kb2` to extract the final sum out of a `Summation` instance gives the compiler enough information to determine the precise type of summation algorithm to use.

As an example, here is a (somewhat silly) function that manually computes the sum of elements in a list.

    sillySumList :: [Double] -> Double
    sillySumList = loop zero
      where loop s []     = kbn s
            loop s (x:xs) = seq s' loop s' xs
              where s'    = add s x

In most instances, you can simply use the much more general `sum` function instead of writing a summation function by hand.

    -- Avoid ambiguity around which sum function we are using.
    import Prelude hiding (sum)
    --
    betterSumList :: [Double] -> Double
    betterSumList xs = sum kbn xs

# Kahan-Babuška-Neumaier summation

data KBNSum Source #

Kahan-Babuška-Neumaier summation. This is a little more computationally costly than plain Kahan summation, but is always at least as accurate.

Constructors

KBNSum !Double !Double |

#### Instances

Instances details

NFData KBNSum Source # |
Instance details Defined in Numeric.Sum Methods rnf :: KBNSum -> () Source #
Monoid KBNSum Source # | Since: 0.3.0.0
Instance details Defined in Numeric.Sum Methods mempty :: KBNSum Source # mappend :: KBNSum -> KBNSum -> KBNSum Source # mconcat :: [KBNSum] -> KBNSum Source #
Semigroup KBNSum Source # | Since: 0.3.0.0
Instance details Defined in Numeric.Sum Methods (<>) :: KBNSum -> KBNSum -> KBNSum Source # sconcat :: NonEmpty KBNSum -> KBNSum Source # stimes :: Integral b => b -> KBNSum -> KBNSum Source #
Data KBNSum Source # |

Instance details

Defined in Numeric.Sum

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> KBNSum -> c KBNSum Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c KBNSum Source #

toConstr :: KBNSum -> Constr Source #

dataTypeOf :: KBNSum -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c KBNSum) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c KBNSum) Source #

gmapT :: (forall b. Data b => b -> b) -> KBNSum -> KBNSum Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> KBNSum -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> KBNSum -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> KBNSum -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> KBNSum -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> KBNSum -> m KBNSum Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> KBNSum -> m KBNSum Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> KBNSum -> m KBNSum Source #

Show KBNSum Source # |
Instance details Defined in Numeric.Sum Methods showsPrec :: Int -> KBNSum -> ShowS Source # show :: KBNSum -> String Source # showList :: [KBNSum] -> ShowS Source #
Eq KBNSum Source # |
Instance details Defined in Numeric.Sum Methods (==) :: KBNSum -> KBNSum -> Bool Source # (/=) :: KBNSum -> KBNSum -> Bool Source #
Summation KBNSum Source # |
Instance details Defined in Numeric.Sum Methods zero :: KBNSum Source # add :: KBNSum -> Double -> KBNSum Source # sum :: Foldable f => (KBNSum -> Double) -> f Double -> Double Source #
Unbox KBNSum Source # |
Instance details Defined in Numeric.Sum
Vector Vector KBNSum Source # |

Instance details

Defined in Numeric.Sum

Methods

basicUnsafeFreeze :: Mutable Vector s KBNSum -> ST s (Vector KBNSum)

basicUnsafeThaw :: Vector KBNSum -> ST s (Mutable Vector s KBNSum)

basicLength :: Vector KBNSum -> Int

basicUnsafeSlice :: Int -> Int -> Vector KBNSum -> Vector KBNSum

basicUnsafeIndexM :: Vector KBNSum -> Int -> Box KBNSum

basicUnsafeCopy :: Mutable Vector s KBNSum -> Vector KBNSum -> ST s ()

elemseq :: Vector KBNSum -> KBNSum -> b -> b

MVector MVector KBNSum Source # |

Instance details

Defined in Numeric.Sum

Methods

basicLength :: MVector s KBNSum -> Int

basicUnsafeSlice :: Int -> Int -> MVector s KBNSum -> MVector s KBNSum

basicOverlaps :: MVector s KBNSum -> MVector s KBNSum -> Bool

basicUnsafeNew :: Int -> ST s (MVector s KBNSum)

basicInitialize :: MVector s KBNSum -> ST s ()

basicUnsafeReplicate :: Int -> KBNSum -> ST s (MVector s KBNSum)

basicUnsafeRead :: MVector s KBNSum -> Int -> ST s KBNSum

basicUnsafeWrite :: MVector s KBNSum -> Int -> KBNSum -> ST s ()

basicClear :: MVector s KBNSum -> ST s ()

basicSet :: MVector s KBNSum -> KBNSum -> ST s ()

basicUnsafeCopy :: MVector s KBNSum -> MVector s KBNSum -> ST s ()

basicUnsafeMove :: MVector s KBNSum -> MVector s KBNSum -> ST s ()

basicUnsafeGrow :: MVector s KBNSum -> Int -> ST s (MVector s KBNSum)

newtype Vector KBNSum Source # |
Instance details Defined in Numeric.Sum newtype Vector KBNSum = V_KBNSum (Vector (Double, Double))
newtype MVector s KBNSum Source # |
Instance details Defined in Numeric.Sum newtype MVector s KBNSum = MV_KBNSum (MVector s (Double, Double))

kbn :: KBNSum -> Double Source #

Return the result of a Kahan-Babuška-Neumaier sum.

# Order-2 Kahan-Babuška summation

data KB2Sum Source #

Second-order Kahan-Babuška summation. This is more computationally costly than Kahan-Babuška-Neumaier summation, running at about a third the speed. Its advantage is that it can lose less precision (in admittedly obscure cases).

This method compensates for error in both the sum and the first-order compensation term, hence the use of "second order" in the name.

Constructors

KB2Sum !Double !Double !Double |

#### Instances

Instances details

NFData KB2Sum Source # |
Instance details Defined in Numeric.Sum Methods rnf :: KB2Sum -> () Source #
Monoid KB2Sum Source # | Since: 0.3.0.0
Instance details Defined in Numeric.Sum Methods mempty :: KB2Sum Source # mappend :: KB2Sum -> KB2Sum -> KB2Sum Source # mconcat :: [KB2Sum] -> KB2Sum Source #
Semigroup KB2Sum Source # | Since: 0.3.0.0
Instance details Defined in Numeric.Sum Methods (<>) :: KB2Sum -> KB2Sum -> KB2Sum Source # sconcat :: NonEmpty KB2Sum -> KB2Sum Source # stimes :: Integral b => b -> KB2Sum -> KB2Sum Source #
Data KB2Sum Source # |

Instance details

Defined in Numeric.Sum

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> KB2Sum -> c KB2Sum Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c KB2Sum Source #

toConstr :: KB2Sum -> Constr Source #

dataTypeOf :: KB2Sum -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c KB2Sum) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c KB2Sum) Source #

gmapT :: (forall b. Data b => b -> b) -> KB2Sum -> KB2Sum Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> KB2Sum -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> KB2Sum -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> KB2Sum -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> KB2Sum -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> KB2Sum -> m KB2Sum Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> KB2Sum -> m KB2Sum Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> KB2Sum -> m KB2Sum Source #

Show KB2Sum Source # |
Instance details Defined in Numeric.Sum Methods showsPrec :: Int -> KB2Sum -> ShowS Source # show :: KB2Sum -> String Source # showList :: [KB2Sum] -> ShowS Source #
Eq KB2Sum Source # |
Instance details Defined in Numeric.Sum Methods (==) :: KB2Sum -> KB2Sum -> Bool Source # (/=) :: KB2Sum -> KB2Sum -> Bool Source #
Summation KB2Sum Source # |
Instance details Defined in Numeric.Sum Methods zero :: KB2Sum Source # add :: KB2Sum -> Double -> KB2Sum Source # sum :: Foldable f => (KB2Sum -> Double) -> f Double -> Double Source #
Unbox KB2Sum Source # |
Instance details Defined in Numeric.Sum
Vector Vector KB2Sum Source # |

Instance details

Defined in Numeric.Sum

Methods

basicUnsafeFreeze :: Mutable Vector s KB2Sum -> ST s (Vector KB2Sum)

basicUnsafeThaw :: Vector KB2Sum -> ST s (Mutable Vector s KB2Sum)

basicLength :: Vector KB2Sum -> Int

basicUnsafeSlice :: Int -> Int -> Vector KB2Sum -> Vector KB2Sum

basicUnsafeIndexM :: Vector KB2Sum -> Int -> Box KB2Sum

basicUnsafeCopy :: Mutable Vector s KB2Sum -> Vector KB2Sum -> ST s ()

elemseq :: Vector KB2Sum -> KB2Sum -> b -> b

MVector MVector KB2Sum Source # |

Instance details

Defined in Numeric.Sum

Methods

basicLength :: MVector s KB2Sum -> Int

basicUnsafeSlice :: Int -> Int -> MVector s KB2Sum -> MVector s KB2Sum

basicOverlaps :: MVector s KB2Sum -> MVector s KB2Sum -> Bool

basicUnsafeNew :: Int -> ST s (MVector s KB2Sum)

basicInitialize :: MVector s KB2Sum -> ST s ()

basicUnsafeReplicate :: Int -> KB2Sum -> ST s (MVector s KB2Sum)

basicUnsafeRead :: MVector s KB2Sum -> Int -> ST s KB2Sum

basicUnsafeWrite :: MVector s KB2Sum -> Int -> KB2Sum -> ST s ()

basicClear :: MVector s KB2Sum -> ST s ()

basicSet :: MVector s KB2Sum -> KB2Sum -> ST s ()

basicUnsafeCopy :: MVector s KB2Sum -> MVector s KB2Sum -> ST s ()

basicUnsafeMove :: MVector s KB2Sum -> MVector s KB2Sum -> ST s ()

basicUnsafeGrow :: MVector s KB2Sum -> Int -> ST s (MVector s KB2Sum)

newtype Vector KB2Sum Source # |
Instance details Defined in Numeric.Sum newtype Vector KB2Sum = V_KB2Sum (Vector (Double, Double, Double))
newtype MVector s KB2Sum Source # |
Instance details Defined in Numeric.Sum newtype MVector s KB2Sum = MV_KB2Sum (MVector s (Double, Double, Double))

kb2 :: KB2Sum -> Double Source #

Return the result of an order-2 Kahan-Babuška sum.

# Less desirable approaches

## Kahan summation

data KahanSum Source #

Kahan summation. This is the least accurate of the compensated summation methods. In practice, it only beats naive summation for inputs with large magnitude. Kahan summation can be less accurate than naive summation for small-magnitude inputs.

This summation method is included for completeness. Its use is not recommended. In practice, `KBNSum` is both 30% faster and more accurate.

Constructors

KahanSum !Double !Double |

#### Instances

Instances details

NFData KahanSum Source # |
Instance details Defined in Numeric.Sum Methods rnf :: KahanSum -> () Source #
Monoid KahanSum Source # | Since: 0.3.0.0
Instance details Defined in Numeric.Sum Methods mempty :: KahanSum Source # mappend :: KahanSum -> KahanSum -> KahanSum Source # mconcat :: [KahanSum] -> KahanSum Source #
Semigroup KahanSum Source # | Since: 0.3.0.0
Instance details Defined in Numeric.Sum Methods (<>) :: KahanSum -> KahanSum -> KahanSum Source # sconcat :: NonEmpty KahanSum -> KahanSum Source # stimes :: Integral b => b -> KahanSum -> KahanSum Source #
Data KahanSum Source # |

Instance details

Defined in Numeric.Sum

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> KahanSum -> c KahanSum Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c KahanSum Source #

toConstr :: KahanSum -> Constr Source #

dataTypeOf :: KahanSum -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c KahanSum) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c KahanSum) Source #

gmapT :: (forall b. Data b => b -> b) -> KahanSum -> KahanSum Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> KahanSum -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> KahanSum -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> KahanSum -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> KahanSum -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> KahanSum -> m KahanSum Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> KahanSum -> m KahanSum Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> KahanSum -> m KahanSum Source #

Show KahanSum Source # |
Instance details Defined in Numeric.Sum Methods showsPrec :: Int -> KahanSum -> ShowS Source # show :: KahanSum -> String Source # showList :: [KahanSum] -> ShowS Source #
Eq KahanSum Source # |
Instance details Defined in Numeric.Sum Methods (==) :: KahanSum -> KahanSum -> Bool Source # (/=) :: KahanSum -> KahanSum -> Bool Source #
Summation KahanSum Source # |
Instance details Defined in Numeric.Sum Methods zero :: KahanSum Source # add :: KahanSum -> Double -> KahanSum Source # sum :: Foldable f => (KahanSum -> Double) -> f Double -> Double Source #
Unbox KahanSum Source # |
Instance details Defined in Numeric.Sum
Vector Vector KahanSum Source # |

Instance details

Defined in Numeric.Sum

Methods

basicUnsafeFreeze :: Mutable Vector s KahanSum -> ST s (Vector KahanSum)

basicUnsafeThaw :: Vector KahanSum -> ST s (Mutable Vector s KahanSum)

basicLength :: Vector KahanSum -> Int

basicUnsafeSlice :: Int -> Int -> Vector KahanSum -> Vector KahanSum

basicUnsafeIndexM :: Vector KahanSum -> Int -> Box KahanSum

basicUnsafeCopy :: Mutable Vector s KahanSum -> Vector KahanSum -> ST s ()

elemseq :: Vector KahanSum -> KahanSum -> b -> b

MVector MVector KahanSum Source # |

Instance details

Defined in Numeric.Sum

Methods

basicLength :: MVector s KahanSum -> Int

basicUnsafeSlice :: Int -> Int -> MVector s KahanSum -> MVector s KahanSum

basicOverlaps :: MVector s KahanSum -> MVector s KahanSum -> Bool

basicUnsafeNew :: Int -> ST s (MVector s KahanSum)

basicInitialize :: MVector s KahanSum -> ST s ()

basicUnsafeReplicate :: Int -> KahanSum -> ST s (MVector s KahanSum)

basicUnsafeRead :: MVector s KahanSum -> Int -> ST s KahanSum

basicUnsafeWrite :: MVector s KahanSum -> Int -> KahanSum -> ST s ()

basicClear :: MVector s KahanSum -> ST s ()

basicSet :: MVector s KahanSum -> KahanSum -> ST s ()

basicUnsafeCopy :: MVector s KahanSum -> MVector s KahanSum -> ST s ()

basicUnsafeMove :: MVector s KahanSum -> MVector s KahanSum -> ST s ()

basicUnsafeGrow :: MVector s KahanSum -> Int -> ST s (MVector s KahanSum)

newtype Vector KahanSum Source # |
Instance details Defined in Numeric.Sum newtype Vector KahanSum = V_KahanSum (Vector (Double, Double))
newtype MVector s KahanSum Source # |
Instance details Defined in Numeric.Sum newtype MVector s KahanSum = MV_KahanSum (MVector s (Double, Double))

kahan :: KahanSum -> Double Source #

Return the result of a Kahan sum.

## Pairwise summation

pairwiseSum :: Vector v Double => v Double -> Double Source #

O(n) Sum a vector of values using pairwise summation.

This approach is perhaps 10% faster than `KBNSum`, but has poorer bounds on its error growth. Instead of having roughly constant error regardless of the size of the input vector, in the worst case its accumulated error grows with O(log n).

# References

- Kahan, W. (1965), Further remarks on reducing truncation errors. Communications of the ACM 8(1):40.
- Neumaier, A. (1974), Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen. Zeitschrift für Angewandte Mathematik und Mechanik 54:39–51.
- Klein, A. (2006), A Generalized Kahan-Babuška-Summation-Algorithm. Computing 76(3):279-293.
- Higham, N.J. (1993), The accuracy of floating point summation. SIAM Journal on Scientific Computing 14(4):783–799.