Data.Array.Accelerate.Numeric.Sum

Functions for summing floating point numbers more accurately than the straightforward sum operation.

In the worst case, the sum function accumulates 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 grows much more slowly than the number of inputs (e.g. logarithmically), or remains constant.

Summation type class

class (Elt a, Elt (s a)) => Summation s a where

A class for the summation of floating-point numbers

Methods

add :: Exp (s a) -> Exp (s a) -> Exp (s a)

Add a value to the sum

zero :: Exp (s a)

The identity of the summation

into :: Proxy s -> Exp a -> Exp (s a)

Insert a value into the summation

from :: Proxy s -> Exp (s a) -> Exp a

Summarise the result of summation

Instances

Summation Kahan Double

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan Double) -> Exp (Kahan Double) -> Exp (Kahan Double)

zero :: Exp (Kahan Double)

into :: Proxy Kahan -> Exp Double -> Exp (Kahan Double)

from :: Proxy Kahan -> Exp (Kahan Double) -> Exp Double

Summation Kahan Float

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan Float) -> Exp (Kahan Float) -> Exp (Kahan Float)

zero :: Exp (Kahan Float)

into :: Proxy Kahan -> Exp Float -> Exp (Kahan Float)

from :: Proxy Kahan -> Exp (Kahan Float) -> Exp Float

Summation Kahan CDouble

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan CDouble) -> Exp (Kahan CDouble) -> Exp (Kahan CDouble)

zero :: Exp (Kahan CDouble)

into :: Proxy Kahan -> Exp CDouble -> Exp (Kahan CDouble)

from :: Proxy Kahan -> Exp (Kahan CDouble) -> Exp CDouble

Summation Kahan CFloat

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan CFloat) -> Exp (Kahan CFloat) -> Exp (Kahan CFloat)

zero :: Exp (Kahan CFloat)

into :: Proxy Kahan -> Exp CFloat -> Exp (Kahan CFloat)

from :: Proxy Kahan -> Exp (Kahan CFloat) -> Exp CFloat

Summation KB2 Double

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 Double) -> Exp (KB2 Double) -> Exp (KB2 Double)

zero :: Exp (KB2 Double)

into :: Proxy KB2 -> Exp Double -> Exp (KB2 Double)

from :: Proxy KB2 -> Exp (KB2 Double) -> Exp Double

Summation KB2 Float

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 Float) -> Exp (KB2 Float) -> Exp (KB2 Float)

zero :: Exp (KB2 Float)

into :: Proxy KB2 -> Exp Float -> Exp (KB2 Float)

from :: Proxy KB2 -> Exp (KB2 Float) -> Exp Float

Summation KB2 CDouble

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 CDouble) -> Exp (KB2 CDouble) -> Exp (KB2 CDouble)

zero :: Exp (KB2 CDouble)

into :: Proxy KB2 -> Exp CDouble -> Exp (KB2 CDouble)

from :: Proxy KB2 -> Exp (KB2 CDouble) -> Exp CDouble

Summation KB2 CFloat

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 CFloat) -> Exp (KB2 CFloat) -> Exp (KB2 CFloat)

zero :: Exp (KB2 CFloat)

into :: Proxy KB2 -> Exp CFloat -> Exp (KB2 CFloat)

from :: Proxy KB2 -> Exp (KB2 CFloat) -> Exp CFloat

Summation KBN Double

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN Double) -> Exp (KBN Double) -> Exp (KBN Double)

zero :: Exp (KBN Double)

into :: Proxy KBN -> Exp Double -> Exp (KBN Double)

from :: Proxy KBN -> Exp (KBN Double) -> Exp Double

Summation KBN Float

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN Float) -> Exp (KBN Float) -> Exp (KBN Float)

zero :: Exp (KBN Float)

into :: Proxy KBN -> Exp Float -> Exp (KBN Float)

from :: Proxy KBN -> Exp (KBN Float) -> Exp Float

Summation KBN CDouble

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN CDouble) -> Exp (KBN CDouble) -> Exp (KBN CDouble)

zero :: Exp (KBN CDouble)

into :: Proxy KBN -> Exp CDouble -> Exp (KBN CDouble)

from :: Proxy KBN -> Exp (KBN CDouble) -> Exp CDouble

Summation KBN CFloat

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN CFloat) -> Exp (KBN CFloat) -> Exp (KBN CFloat)

zero :: Exp (KBN CFloat)

into :: Proxy KBN -> Exp CFloat -> Exp (KBN CFloat)

from :: Proxy KBN -> Exp (KBN CFloat) -> Exp CFloat

sum :: (Summation s a, Shape sh) => Proxy s -> Acc (Array (sh :. Int) a) -> Acc (Array sh a)

Sum an array using a particular compensation scheme.

>>> let xs = [1.0, 1.0e100, 1.0, -1.0e100] :: [Double]
>>> Prelude.sum xs
0.0

>>> let ys = fromList (Z:.4) [1.0, 1.0e100, 1.0, -1.0e100] :: Vector Double
>>> sum kbn (use ys)
Scalar Z [2.0]

Kahan-Babuška-Neumaier summation

data KBN a

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

Constructors

KBN a a

Instances

Summation KBN Double

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN Double) -> Exp (KBN Double) -> Exp (KBN Double)

zero :: Exp (KBN Double)

into :: Proxy KBN -> Exp Double -> Exp (KBN Double)

from :: Proxy KBN -> Exp (KBN Double) -> Exp Double

Summation KBN Float

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN Float) -> Exp (KBN Float) -> Exp (KBN Float)

zero :: Exp (KBN Float)

into :: Proxy KBN -> Exp Float -> Exp (KBN Float)

from :: Proxy KBN -> Exp (KBN Float) -> Exp Float

Summation KBN CDouble

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN CDouble) -> Exp (KBN CDouble) -> Exp (KBN CDouble)

zero :: Exp (KBN CDouble)

into :: Proxy KBN -> Exp CDouble -> Exp (KBN CDouble)

from :: Proxy KBN -> Exp (KBN CDouble) -> Exp CDouble

Summation KBN CFloat

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KBN CFloat) -> Exp (KBN CFloat) -> Exp (KBN CFloat)

zero :: Exp (KBN CFloat)

into :: Proxy KBN -> Exp CFloat -> Exp (KBN CFloat)

from :: Proxy KBN -> Exp (KBN CFloat) -> Exp CFloat

Elt a => IsProduct Elt (KBN a)

Defined in Data.Array.Accelerate.Numeric.Sum

Associated Types

type ProdRepr (KBN a) :: Type

Methods

fromProd :: proxy Elt -> KBN a -> ProdRepr (KBN a)

toProd :: proxy Elt -> ProdRepr (KBN a) -> KBN a

prod :: proxy Elt -> KBN a -> ProdR Elt (ProdRepr (KBN a))

(Lift Exp a, Elt (Plain a)) => Lift Exp (KBN a)

Defined in Data.Array.Accelerate.Numeric.Sum

Associated Types

type Plain (KBN a) :: Type

Methods

lift :: KBN a -> Exp (Plain (KBN a))

Elt a => Unlift Exp (KBN (Exp a))

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

unlift :: Exp (Plain (KBN (Exp a))) -> KBN (Exp a)

Show a => Show (KBN a)

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

showsPrec :: Int -> KBN a -> ShowS

show :: KBN a -> String

showList :: [KBN a] -> ShowS

Elt a => Elt (KBN a)

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

eltType :: KBN a -> TupleType (EltRepr (KBN a))

fromElt :: KBN a -> EltRepr (KBN a)

toElt :: EltRepr (KBN a) -> KBN a

type EltRepr (KBN a)

Defined in Data.Array.Accelerate.Numeric.Sum

type EltRepr (KBN a) = (((), EltRepr a), EltRepr a)

type ProdRepr (KBN a)

Defined in Data.Array.Accelerate.Numeric.Sum

type ProdRepr (KBN a) = (((), a), a)

type Plain (KBN a)

Defined in Data.Array.Accelerate.Numeric.Sum

type Plain (KBN a) = KBN (Plain a)

kbn :: Proxy KBN

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

Order-2 Kahan-Babuška summation

data KB2 a

Second-order Kahan-Babuška summation. This is more computationally costly than Kahan-Babuška-Neumaier summation. 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

KB2 a a a

Instances

Summation KB2 Double

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 Double) -> Exp (KB2 Double) -> Exp (KB2 Double)

zero :: Exp (KB2 Double)

into :: Proxy KB2 -> Exp Double -> Exp (KB2 Double)

from :: Proxy KB2 -> Exp (KB2 Double) -> Exp Double

Summation KB2 Float

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 Float) -> Exp (KB2 Float) -> Exp (KB2 Float)

zero :: Exp (KB2 Float)

into :: Proxy KB2 -> Exp Float -> Exp (KB2 Float)

from :: Proxy KB2 -> Exp (KB2 Float) -> Exp Float

Summation KB2 CDouble

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 CDouble) -> Exp (KB2 CDouble) -> Exp (KB2 CDouble)

zero :: Exp (KB2 CDouble)

into :: Proxy KB2 -> Exp CDouble -> Exp (KB2 CDouble)

from :: Proxy KB2 -> Exp (KB2 CDouble) -> Exp CDouble

Summation KB2 CFloat

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (KB2 CFloat) -> Exp (KB2 CFloat) -> Exp (KB2 CFloat)

zero :: Exp (KB2 CFloat)

into :: Proxy KB2 -> Exp CFloat -> Exp (KB2 CFloat)

from :: Proxy KB2 -> Exp (KB2 CFloat) -> Exp CFloat

Elt a => IsProduct Elt (KB2 a)

Defined in Data.Array.Accelerate.Numeric.Sum

Associated Types

type ProdRepr (KB2 a) :: Type

Methods

fromProd :: proxy Elt -> KB2 a -> ProdRepr (KB2 a)

toProd :: proxy Elt -> ProdRepr (KB2 a) -> KB2 a

prod :: proxy Elt -> KB2 a -> ProdR Elt (ProdRepr (KB2 a))

(Lift Exp a, Elt (Plain a)) => Lift Exp (KB2 a)

Defined in Data.Array.Accelerate.Numeric.Sum

Associated Types

type Plain (KB2 a) :: Type

Methods

lift :: KB2 a -> Exp (Plain (KB2 a))

Elt a => Unlift Exp (KB2 (Exp a))

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

unlift :: Exp (Plain (KB2 (Exp a))) -> KB2 (Exp a)

Show a => Show (KB2 a)

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

showsPrec :: Int -> KB2 a -> ShowS

show :: KB2 a -> String

showList :: [KB2 a] -> ShowS

Elt a => Elt (KB2 a)

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

eltType :: KB2 a -> TupleType (EltRepr (KB2 a))

fromElt :: KB2 a -> EltRepr (KB2 a)

toElt :: EltRepr (KB2 a) -> KB2 a

type EltRepr (KB2 a)

Defined in Data.Array.Accelerate.Numeric.Sum

type EltRepr (KB2 a) = ((((), EltRepr a), EltRepr a), EltRepr a)

type ProdRepr (KB2 a)

Defined in Data.Array.Accelerate.Numeric.Sum

type ProdRepr (KB2 a) = ((((), a), a), a)

type Plain (KB2 a)

Defined in Data.Array.Accelerate.Numeric.Sum

type Plain (KB2 a) = KB2 (Plain a)

kb2 :: Proxy KB2

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

Kahan summation

data Kahan a

Kahan summation. This is the least accurate of the compensated summation methods. This summation method is included only for completeness.

Constructors

Kahan a a

Instances

Summation Kahan Double

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan Double) -> Exp (Kahan Double) -> Exp (Kahan Double)

zero :: Exp (Kahan Double)

into :: Proxy Kahan -> Exp Double -> Exp (Kahan Double)

from :: Proxy Kahan -> Exp (Kahan Double) -> Exp Double

Summation Kahan Float

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan Float) -> Exp (Kahan Float) -> Exp (Kahan Float)

zero :: Exp (Kahan Float)

into :: Proxy Kahan -> Exp Float -> Exp (Kahan Float)

from :: Proxy Kahan -> Exp (Kahan Float) -> Exp Float

Summation Kahan CDouble

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan CDouble) -> Exp (Kahan CDouble) -> Exp (Kahan CDouble)

zero :: Exp (Kahan CDouble)

into :: Proxy Kahan -> Exp CDouble -> Exp (Kahan CDouble)

from :: Proxy Kahan -> Exp (Kahan CDouble) -> Exp CDouble

Summation Kahan CFloat

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

add :: Exp (Kahan CFloat) -> Exp (Kahan CFloat) -> Exp (Kahan CFloat)

zero :: Exp (Kahan CFloat)

into :: Proxy Kahan -> Exp CFloat -> Exp (Kahan CFloat)

from :: Proxy Kahan -> Exp (Kahan CFloat) -> Exp CFloat

Elt a => IsProduct Elt (Kahan a)

Defined in Data.Array.Accelerate.Numeric.Sum

Associated Types

type ProdRepr (Kahan a) :: Type

Methods

fromProd :: proxy Elt -> Kahan a -> ProdRepr (Kahan a)

toProd :: proxy Elt -> ProdRepr (Kahan a) -> Kahan a

prod :: proxy Elt -> Kahan a -> ProdR Elt (ProdRepr (Kahan a))

(Lift Exp a, Elt (Plain a)) => Lift Exp (Kahan a)

Defined in Data.Array.Accelerate.Numeric.Sum

Associated Types

type Plain (Kahan a) :: Type

Methods

lift :: Kahan a -> Exp (Plain (Kahan a))

Elt a => Unlift Exp (Kahan (Exp a))

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

unlift :: Exp (Plain (Kahan (Exp a))) -> Kahan (Exp a)

Show a => Show (Kahan a)

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

showsPrec :: Int -> Kahan a -> ShowS

show :: Kahan a -> String

showList :: [Kahan a] -> ShowS

Elt a => Elt (Kahan a)

Defined in Data.Array.Accelerate.Numeric.Sum

Methods

eltType :: Kahan a -> TupleType (EltRepr (Kahan a))

fromElt :: Kahan a -> EltRepr (Kahan a)

toElt :: EltRepr (Kahan a) -> Kahan a

type EltRepr (Kahan a)

Defined in Data.Array.Accelerate.Numeric.Sum

type EltRepr (Kahan a) = (((), EltRepr a), EltRepr a)

type ProdRepr (Kahan a)

Defined in Data.Array.Accelerate.Numeric.Sum

type ProdRepr (Kahan a) = (((), a), a)

type Plain (Kahan a)

Defined in Data.Array.Accelerate.Numeric.Sum

type Plain (Kahan a) = Kahan (Plain a)

kahan :: Proxy Kahan

Return the result of a Kahan sum.