NAME

Math::Summation - add numbers in ways that give less numerical errors

SYNOPSIS

    use Math::Summation 'sum';  # and/or 'kahansum' etc.

    my @values = (1, 1e100, 1, -1e100);

    # use the standard way of adding numbers
    my $sum = sum(@values);

    # use the Kahan summation algorithm
    my $sum_khn = kahansum(@values);

    # use the Neumaier summation algorithm
    my $sum_nmr = neumaiersum(@values);

    # use the Klein summation algorithm
    my $sum_kln = kleinsum(@values);

    # use the pairwise summation algorithm
    my $sum_pws = pairwisesum(@values);

DESCRIPTION

This module implements various algorithms that significantly reduces the numerical error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared to the obvious approach.

No functions are exported by default. The desired functions can be imported like in the following example:

    use Math::Summation 'sum';      # and/or 'kahansum' etc.

To import all exportable functions, use the 'all' tag:

    use Math::Summation ':all';     # import all fucntions

FUNCTIONS

sum LIST

Returns the sum of the elements in LIST. This is done by naively adding each number directly to the accumulating total.

    # use the standard way of adding numbers
    my $sum = sum(@values);
kahansum LIST

Returns the sum of the elements in LIST.

    # use the Kahan summation algorithm
    my $sum_khn = kahansum(@values);

The Kahan summation algorithm, also known as "compensated summation", significantly reduces the numerical error in the total obtained by adding a sequence of finite-precision floating-point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors).

This function is more accurate than a direct summation, but at the expence of more computational complexity.

neumaiersum LIST

Returns the sum of the elements in LIST.

    # use the Neumaier summation algorithm
    my $sum_nmr = neumaiersum(@values);

Neumaier introduced an improved version of the Kahan algorithm, which Neumaier calls an "improved Kahan–Babuška algorithm", which also covers the case when the next term to be added is larger in absolute value than the running sum, effectively swapping the role of what is large and what is small.

The difference between Neumaier's algorithm and Kahan's algorithm can be seen when summing the four numbers (1, 1e100, 1, -1e100) with double or quad precision. Kahan's algorithm gives 0, but Neumeier's algorithm gives 2, which is the correct result.

kleinsum LIST

Returns the sum of the elements in LIST.

    # use the Klein summation algorithm
    my $sum_kln = kleinsum(@values);

Higher-order modifications of the above algorithms, to provide even better accuracy are also possible. Klein suggested what he called a second-order "iterative Kahan–Babuška algorithm".

This method has some advantages over Kahan's and Neumaier's algorithms, but at the expense of even more computational complexity.

pairwisesum LIST

Returns the sum of the elements in LIST.

    # use the pairwise summation algorithm
    my $sum_pws = pairwisesum(@values);

The summation is done by recursively splitting the set in half and computing the sum of each half.

This algorithm has the same number of arithmetic operations as a direct summation, but the recursion introduces some overhead.

BUGS

Please report any bugs through the web interface at https://rt.cpan.org/Ticket/Create.html?Queue=Math-Summation (requires login). We will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

    perldoc Math::Summation

You can also look for information at:

SEE ALSO

LICENSE AND COPYRIGHT

Copyright (c) 2020 Peter John Acklam.

This program is free software; you may redistribute it and/or modify it under the same terms as Perl itself.

AUTHOR

Peter John Acklam <pjacklam (at) gmail.com>.