-
Notifications
You must be signed in to change notification settings - Fork 0
/
PairwiseSum.cs
146 lines (124 loc) · 3.82 KB
/
PairwiseSum.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//---------------------------------------------------------------------------
// PROJECT : Compensated Accumulators
// COPYRIGHT : Andy Thomas (C) 2019
// WEB URL : https://kuiper.zone
// LICENSE : GPLv3
//---------------------------------------------------------------------------
using System.Collections.Generic;
namespace CompensatedAccumulators
{
/// <summary>
/// A "pairwise" implementation of <see cref="ICompensatedSum"/>. In this, values
/// are buffered. Computation of the result is performed only periodically or when
/// the <see cref="Value"/> is requred.
/// </summary>
public class PairwiseSum : ICompensatedSum
{
private const int BufferSize = 8192;
private const int BaseN = 2;
private readonly List<double> _buffer = new List<double>(BufferSize);
// Cached result
private double _value;
private bool _hasValue = true;
/// <summary>
/// Default constructor.
/// </summary>
public PairwiseSum()
{
}
/// <summary>
/// Constructor with initial value.
/// </summary>
public PairwiseSum(double x)
{
Value = x;
}
/// <summary>
/// Implements <see cref="ICompensatedSum.Value"/>.
/// </summary>
public double Value
{
get
{
return ActualizeCache(false);
}
set
{
_value = value;
_hasValue = true;
_buffer.Clear();
}
}
/// <summary>
/// Implements <see cref="ICompensatedSum.Add(double)"/>.
/// </summary>
public void Add(double x)
{
if (_buffer.Count == BufferSize)
{
// Process buff
ActualizeCache(true);
}
_buffer.Add(x);
_hasValue = false;
}
/// <summary>
/// Implements <see cref="ICompensatedSum.Clear()"/>.
/// </summary>
public void Clear()
{
_value = 0;
_hasValue = true;
_buffer.Clear();
}
/// <summary>
/// Implements <see cref="ICompensatedSum.Clone()"/>.
/// </summary>
public ICompensatedSum Clone()
{
var clone = new PairwiseSum();
clone._value = _value;
clone._hasValue = _hasValue;
clone._buffer.AddRange(_buffer);
return clone;
}
private static double Pairwise(IList<double> values, int start, int end)
{
// https://en.wikipedia.org/wiki/Pairwise_summation
int sz = end - start;
if (sz <= BaseN)
{
double sum = 0;
while(start < end)
{
sum += values[start++];
}
return sum;
}
sz = start + sz / 2 + 1;
return Pairwise(values, start, sz) + Pairwise(values, sz, end);
}
private double ActualizeCache(bool clear)
{
if (!_hasValue)
{
if (_buffer.Count > 0)
{
_value = Pairwise(_buffer, 0, _buffer.Count);
}
else
{
_value = 0;
}
_hasValue = true;
}
if (clear || _buffer.Count >= BufferSize)
{
// Already cached here
_buffer.Clear();
_buffer.Add(_value);
}
return _value;
}
}
}