|
14 | 14 |
|
15 | 15 | #include <algorithm> |
16 | 16 | #include <cmath> |
| 17 | +#include <cstring> |
| 18 | +#include <limits> |
17 | 19 | #include <numeric> |
18 | 20 | #include <string> |
19 | 21 | #include <vector> |
20 | 22 |
|
21 | 23 | namespace pineforge { |
22 | 24 |
|
23 | | -// --- KahanWindowSum (window_sum.hpp): ta.sma / math.sum arithmetic --- |
| 25 | +// --- ExactWindowSum (window_sum.hpp): correctly rounded SMA window sum --- |
| 26 | + |
| 27 | +ExactWindowSum::ExactWindowSum(int length) : length_(length) { |
| 28 | + static_assert(std::numeric_limits<double>::is_iec559 && |
| 29 | + std::numeric_limits<double>::radix == 2 && |
| 30 | + std::numeric_limits<double>::digits == 53 && |
| 31 | + std::numeric_limits<double>::max_exponent == 1024 && |
| 32 | + sizeof(double) == sizeof(std::uint64_t), |
| 33 | + "ExactWindowSum requires IEEE binary64"); |
| 34 | +} |
| 35 | + |
| 36 | +void ExactWindowSum::update_word(Magnitude& magnitude, std::size_t index, |
| 37 | + std::uint64_t word, bool remove) { |
| 38 | + // A source spans at most two words. Propagating each word's carry or |
| 39 | + // borrow separately uses only standard unsigned 64-bit arithmetic. |
| 40 | + while (word != 0 && index < magnitude.size()) { |
| 41 | + const std::uint64_t before = magnitude[index]; |
| 42 | + if (remove) { |
| 43 | + magnitude[index] = before - word; |
| 44 | + word = before < word ? 1 : 0; |
| 45 | + } else { |
| 46 | + magnitude[index] = before + word; |
| 47 | + word = magnitude[index] < before ? 1 : 0; |
| 48 | + } |
| 49 | + ++index; |
| 50 | + } |
| 51 | +} |
| 52 | + |
| 53 | +void ExactWindowSum::update(double src, bool remove) { |
| 54 | + std::uint64_t bits; |
| 55 | + std::memcpy(&bits, &src, sizeof(bits)); |
| 56 | + const bool negative = (bits >> 63) != 0; |
| 57 | + const unsigned exponent = static_cast<unsigned>((bits >> 52) & UINT64_C(0x7ff)); |
| 58 | + if (exponent == 0x7ff) { |
| 59 | + // NA never enters this class; these are signed infinities. |
| 60 | + int& count = negative ? negative_infinities_ : positive_infinities_; |
| 61 | + count += remove ? -1 : 1; |
| 62 | + return; |
| 63 | + } |
| 64 | + |
| 65 | + std::uint64_t significand = bits & UINT64_C(0x000fffffffffffff); |
| 66 | + if (exponent != 0) significand |= UINT64_C(1) << 52; |
| 67 | + const unsigned shift = exponent == 0 ? 0 : exponent - 1; |
| 68 | + const std::size_t index = shift / 64; |
| 69 | + const unsigned offset = shift % 64; |
| 70 | + Magnitude& magnitude = negative ? negative_ : positive_; |
| 71 | + update_word(magnitude, index, significand << offset, remove); |
| 72 | + if (offset != 0) { |
| 73 | + update_word(magnitude, index + 1, significand >> (64 - offset), remove); |
| 74 | + } |
| 75 | +} |
| 76 | + |
| 77 | +double ExactWindowSum::push(double src) { |
| 78 | + saved_count_ = count_; |
| 79 | + saved_pushed_ = true; |
| 80 | + saved_evicted_ = count_ >= length_; |
| 81 | + if (saved_evicted_) { |
| 82 | + saved_evicted_value_ = values_.back(); |
| 83 | + values_.pop_back(); |
| 84 | + update(saved_evicted_value_, true); |
| 85 | + } |
| 86 | + values_.push_front(src); |
| 87 | + update(src, false); |
| 88 | + if (count_ < length_) ++count_; |
| 89 | + return sum(); |
| 90 | +} |
| 91 | + |
| 92 | +void ExactWindowSum::note_no_push() { |
| 93 | + saved_pushed_ = false; |
| 94 | +} |
| 95 | + |
| 96 | +void ExactWindowSum::unpush() { |
| 97 | + if (!saved_pushed_) return; |
| 98 | + update(values_.front(), true); |
| 99 | + values_.pop_front(); |
| 100 | + if (saved_evicted_) { |
| 101 | + values_.push_back(saved_evicted_value_); |
| 102 | + update(saved_evicted_value_, false); |
| 103 | + } |
| 104 | + count_ = saved_count_; |
| 105 | + saved_pushed_ = false; |
| 106 | +} |
| 107 | + |
| 108 | +double ExactWindowSum::repush(double src) { |
| 109 | + if (!saved_pushed_) return push(src); |
| 110 | + // The provisional source leaves, but its saved eviction stays absent: |
| 111 | + // the replacement therefore sees exactly the same pre-bar window. |
| 112 | + update(values_.front(), true); |
| 113 | + values_.front() = src; |
| 114 | + update(src, false); |
| 115 | + return sum(); |
| 116 | +} |
| 117 | + |
| 118 | +double ExactWindowSum::sum() const { |
| 119 | + if (positive_infinities_ != 0 && negative_infinities_ != 0) return na<double>(); |
| 120 | + if (positive_infinities_ != 0) return std::numeric_limits<double>::infinity(); |
| 121 | + if (negative_infinities_ != 0) return -std::numeric_limits<double>::infinity(); |
| 122 | + |
| 123 | + int comparison = 0; |
| 124 | + for (std::size_t i = positive_.size(); i-- > 0;) { |
| 125 | + if (positive_[i] != negative_[i]) { |
| 126 | + comparison = positive_[i] > negative_[i] ? 1 : -1; |
| 127 | + break; |
| 128 | + } |
| 129 | + } |
| 130 | + if (comparison == 0) return 0.0; // exact cancellation is canonical +0 |
| 131 | + |
| 132 | + const Magnitude& larger = comparison > 0 ? positive_ : negative_; |
| 133 | + const Magnitude& smaller = comparison > 0 ? negative_ : positive_; |
| 134 | + // Fixed query scratch, not retained history or a saved per-bar snapshot. |
| 135 | + Magnitude magnitude{}; |
| 136 | + std::uint64_t borrow = 0; |
| 137 | + for (std::size_t i = 0; i < magnitude.size(); ++i) { |
| 138 | + const std::uint64_t difference = larger[i] - smaller[i]; |
| 139 | + magnitude[i] = difference - borrow; |
| 140 | + borrow = (larger[i] < smaller[i] || difference < borrow) ? 1 : 0; |
| 141 | + } |
| 142 | + |
| 143 | + std::size_t top = magnitude.size() - 1; |
| 144 | + while (magnitude[top] == 0) --top; // comparison established a nonzero sum |
| 145 | + int highest_bit = static_cast<int>(top * 64); |
| 146 | + for (std::uint64_t word = magnitude[top]; word > 1; word >>= 1) ++highest_bit; |
| 147 | + |
| 148 | + std::uint64_t bits = comparison < 0 ? UINT64_C(1) << 63 : 0; |
| 149 | + if (highest_bit < 52) { |
| 150 | + // Subnormal sums are already exact integers in units of 2^-1074. |
| 151 | + bits |= magnitude[0]; |
| 152 | + } else { |
| 153 | + const unsigned discarded = static_cast<unsigned>(highest_bit - 52); |
| 154 | + const std::size_t index = discarded / 64; |
| 155 | + const unsigned offset = discarded % 64; |
| 156 | + std::uint64_t significand = magnitude[index] >> offset; |
| 157 | + if (offset != 0 && index + 1 < magnitude.size()) { |
| 158 | + significand |= magnitude[index + 1] << (64 - offset); |
| 159 | + } |
| 160 | + if (discarded != 0) { |
| 161 | + const std::size_t guard_index = (discarded - 1) / 64; |
| 162 | + const unsigned guard_offset = (discarded - 1) % 64; |
| 163 | + const bool guard = ((magnitude[guard_index] >> guard_offset) & 1) != 0; |
| 164 | + bool sticky = (magnitude[guard_index] & |
| 165 | + ((UINT64_C(1) << guard_offset) - 1)) != 0; |
| 166 | + for (std::size_t i = 0; i < guard_index; ++i) { |
| 167 | + sticky = sticky || magnitude[i] != 0; |
| 168 | + } |
| 169 | + // Round the magnitude nearest/even: a set guard rounds up only |
| 170 | + // beyond halfway, or at halfway when the retained low bit is odd. |
| 171 | + if (guard && (sticky || (significand & 1) != 0)) ++significand; |
| 172 | + } |
| 173 | + if (significand == (UINT64_C(1) << 53)) { |
| 174 | + significand >>= 1; |
| 175 | + ++highest_bit; |
| 176 | + } |
| 177 | + // Bit k represents 2^(k-1074); its biased normal exponent is k-51. |
| 178 | + const unsigned exponent = static_cast<unsigned>(highest_bit - 51); |
| 179 | + if (exponent >= 0x7ff) { |
| 180 | + bits |= UINT64_C(0x7ff0000000000000); |
| 181 | + } else { |
| 182 | + bits |= static_cast<std::uint64_t>(exponent) << 52; |
| 183 | + bits |= significand & UINT64_C(0x000fffffffffffff); |
| 184 | + } |
| 185 | + } |
| 186 | + double result; |
| 187 | + std::memcpy(&result, &bits, sizeof(result)); |
| 188 | + return result; |
| 189 | +} |
| 190 | + |
| 191 | +// --- KahanWindowSum (window_sum.hpp): legacy math.sum / biased StdDev --- |
| 192 | +// The historical fit below is retained for those consumers. SMA now uses |
| 193 | +// ExactWindowSum above; these notes do not establish its current contract. |
24 | 194 | // TradingView's sliding-window sum (ta.sma, math.sum), fitted 2026-09-05 on |
25 | 195 | // the round-7 synthetic pins (scratchpad r7/pins/sma-pulse-*, sma-ident-*: |
26 | 196 | // OANDA:EURUSD 15, pulse series of known doubles, lengths 3 and 20, three |
@@ -272,6 +442,7 @@ double SMA::compute(double src) { |
272 | 442 | return na<double>(); |
273 | 443 | } |
274 | 444 |
|
| 445 | + // Round the exact current-window sum first, then divide in binary64. |
275 | 446 | double sum = window_.push(src); |
276 | 447 | bar_count++; |
277 | 448 |
|
@@ -535,9 +706,9 @@ double SMA::recompute(double src) { |
535 | 706 | return compute(src); |
536 | 707 | } |
537 | 708 |
|
538 | | - // Replay the bar with the new source: the same evicted addend, the same |
539 | | - // pre-bar (sum, compensation), so a recompute()d bar and a freshly |
540 | | - // computed one with an identical window agree bit-for-bit. |
| 709 | + // Replay the bar with the new raw source and the same saved eviction, |
| 710 | + // so a recompute()d bar and a freshly computed one with an identical |
| 711 | + // window agree bit-for-bit. |
541 | 712 | double sum = window_.repush(src); |
542 | 713 |
|
543 | 714 | if (bar_count < length) { |
|
0 commit comments