summation
Compensated summation
reduces numerical error when summing sequences of Double.
This does not eliminate rounding errors, but reduces them by orders of magnitude.
val numbers = listOf(0.1, 0.2, 0.1, 0.2, 0.1, 0.2, 0.1)
numbers.sumOf { it } // 1.0000000000000002 (naive)
numbers.accurateSumOf { it } // 1.0 (compensated)
Most of the functions use “second-order iterative Kahan–Babuška algorithm” suggested by Klein (2005).
Install
settings.gradle.kts
sourceControl {
gitRepository(java.net.URI("https://github.com/rtmigo/summation_kt.git")) {
producesModule("io.github.rtmigo:summation")
}
}
build.gradle.kts
dependencies {
implementation("io.github.rtmigo:summation") {
version { branch = "staging" }
}
}
Import in Kotlin code:
import io.github.rtmigo.summation.* // Kotlin
Lambda functions with compensated sums
val sequence = listOf(1, 2, 3)
// sum
sequence.accurateSumOf { it * 0.1 } // equals 0.6
// arithmetic mean
sequence.accurateMeanOf { it * 0.1 } // equals 0.2
// standard deviation and mean
val (stdev, mean) = sequence.accurateStdMeanOf { it * 0.1 }
Running compensated sum
Running sum, immutable version:
var sum = AccurateSum(5.0) // 5.0 is optional starting value
sum += 0.1 // create new object and reassign var
sum += listOf(0.2, 0.3) // create new object and reassign var
println(sum.value) // 5.6
sum -= 0.2 // create new object and reassign var
println(sum.value) // 5.4
Running sum, mutable version (faster):
val sum = MutableAccurateSum(5.0) // 5.0 is optional starting value
sum.add(0.1) // mutate the sum object
sum.add(listOf(0.2, 0.3)) // mutate the sum object
println(sum.value) // 5.6
sum.add(-0.2) // mutate the sum object
println(sum.value) // 5.4
Other functions
kahanSumOf implements Kahan compensated summation algorithm
in its traditional form.
The calculation accuracy is slightly lower than accurateSumOf (by Klein),
but still much better than the naive sum.
val sequence = listOf(1, 2, 3)
println( sequence.kahanSumOf { it * 0.1 } ) // 0.6
welfordMeanOf calculates the arithmetic mean, avoiding overflow when summing too large
values.
val sequence = listOf(1, 2, 3)
println( sequence.welfordMeanOf { it * 0.1 } ) // 0.3
