precise
Implements compensated summation for sequences of Double. Reduces rounding errors associated with limited precision of floating-point numbers.
val numbers = List(420) { 0.1 } // 420 x 0.01
numbers.preciseSumOf { it } // 42.0 (compensated sum)
numbers.sumOf { it } // 42.00000000000033 (naive sum)
The table shows the total error when summing the same sequence of random numbers. All the terms were rounded to 0.0001 before addition. In the % column, the error of preciseSumOf compared to sumOf.
| Terms | err( sum ) | err( preciseSum ) | % |
|---|---|---|---|
| 10 | 0.00000000003 | 0.00000000003 | 100.0% |
| 100 | 0.0000000008 | 0.00000000002 | 3.03% |
| 1,000 | 0.000000001 | 0.0000000001 | 9.57% |
| 10,000 | 0.00000002 | 0.0000000007 | 3.57% |
| 100,000 | 0.0000005 | 0.000000004 | 0.77% |
| 1,000,000 | 0.000009 | 0.000000003 | 0.03% |
% is err(preciseSum) / err(sum)
Most of the functions use "second-order iterative KahanโBabuลกka algorithm" by Klein (2005) .
Install
settings.gradle.kts
sourceControl {
gitRepository(java.net.URI("https://github.com/rtmigo/precise_kt.git")) {
producesModule("io.github.rtmigo:precise")
}
}
build.gradle.kts
dependencies {
implementation("io.github.rtmigo:precise") {
version { branch = "staging" }
}
}
Import in Kotlin code:
import io.github.rtmigo.precise.* // Kotlin
Lambda functions
val sequence = listOf(1, 2, 3)
// sum
sequence.preciseSumOf { it * 0.1 } // equals 0.6
// arithmetic mean
sequence.preciseMeanOf { it * 0.1 } // equals 0.2
// standard deviation and mean
val (stdev, mean) = sequence.preciseStdevMean { it * 0.1 }
Running sum
Running sum, immutable version:
var sum = PreciseSum(5.0) // 5.0 is optional starting value
sum += 0.1
sum += listOf(0.2, 0.3)
println(sum.value) // 5.6
sum -= 0.2
println(sum.value) // 5.4
Running sum, mutable version (faster):
val sum = MutablePreciseSum(5.0) // 5.0 is optional starting value
sum.add(0.1)
sum.add(listOf(0.2, 0.3))
println(sum.value) // 5.6
sum.add(-0.2)
println(sum.value) // 5.4
Benchmarks
An alternative to compensated summation is to use BigDecimal: there is no error when summing them. However, even in the case of a pre-generated array, BigDecimals are 5-10 times slower.
| Method | Time |
|---|---|
List<Double>.sumOf (naive) |
17 ms |
List<Double>.preciseSumOf |
48 ms |
MutablePreciseSum |
50 ms |
PreciseSum (immutable) |
75 ms |
List<BigDecimal>.sumOf |
501 ms |
List<Double>.sumOf { it.toBigDecimal() } |
3192 ms |
Other functions
kahanSumOf implements Kahan compensated summation algorithm in its traditional form. The accuracy is worse than preciseSumOf, but better than the naive sum.
val sequence = listOf(1, 2, 3)
sequence.kahanSumOf { it * 0.1 } // 0.6
cascadeSumOf performs pairwise summation. The accuracy is worse than preciseSumOf, but better than the naive sum.
val sequence = listOf(1, 2, 3)
sequence.cascadeSumOf { 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
37 Dec 9, 2022
5 Sep 28, 2022
2 Oct 27, 2022
5 Dec 8, 2022
3 Jun 18, 2022
18 Nov 24, 2022
19 Nov 17, 2022
2 Nov 8, 2022
73 Nov 28, 2022
8 Nov 7, 2022
8 Nov 29, 2022
1 May 6, 2022
148 Jan 8, 2023
3 Nov 5, 2022
1.5k Dec 30, 2022
14 Nov 5, 2022
19 Sep 8, 2022
13 Dec 16, 2022
6 Jun 27, 2022