Module 3
Prefix sums: O(1) window math
Rolling beta over a trailing window boils down to four sums. With ticker returns x and baseline returns y, beta over any window of N return pairs is (N·Σxy − Σx·Σy) / (N·Σy² − (Σy)²) — so for every output day the engine needs Σx, Σy, Σxy and Σy² over that day's trailing window.
The naive approach re-adds the window every day: O(w) work per output day, so a query of n days costs O(n·w). With a 50-year window (w ≈ 12,600 trading days) that's ruinous — and completely unnecessary, because consecutive windows share almost all of their terms.
The fix is one of the oldest tricks in the book: prefix sums. Precompute, once, prefix[i] = sum of the first i elements. Then the sum over any window is prefix[hi] − prefix[lo] — two array lookups and one subtraction, no matter whether the window covers 20 days or 50 years. Build cost is O(n) once; every window after that is O(1).
Drag the window around and watch the two computations agree — at wildly different cost.
🎛 Window-sum explorer
Daily values (the naive path sums the highlighted bars)
Prefix array — prefix[i] = sum of the first i values (the prefix path reads only the two highlighted cells)
0
[0]
4
[1]
11
[2]
14
[3]
22
[4]
27
[5]
29
[6]
38
[7]
44
[8]
47
[9]
54
[10]
58
[11]
66
[12]
68
[13]
74
[14]
79
[15]
86
[16]
Naive: sum the 8 bars
44
adds: 7
Prefix: prefix[11] − prefix[3]
58 − 14 = 44
adds: 1 subtraction
Same answer, every time — move the sliders and watch the two totals stay equal.
Operations per output day, at real window sizes
w = 20
naive: 19
prefix: 2
10× fewer
w = 252
naive: 251
prefix: 2
126× fewer
w = 12,600
naive: 12,599
prefix: 2
6,300× fewer
This is exactly what PairSeries.moments(firstReturn, lastReturn)does in the beta service: four prefix arrays (Σx, Σy, Σxy, Σy²) are built once when a pair is aligned, and any trailing window's sums come back as two array reads and one subtraction — O(1) per day whether the window is 20 days or 50 years. Educational tool — not investment advice.
The real code: four prefix arrays, built once
In the beta service, PairSeriesholds a ticker/baseline pair and builds all four prefix arrays in a single pass when the pair is aligned. Each slot adds one day's log-return moments onto the running totals:
for (int m = 1; m < k; m++) {
double x = Math.log(closeX[m] / closeX[m - 1]);
double y = Math.log(closeY[m] / closeY[m - 1]);
px[m] = px[m - 1] + x;
py[m] = py[m - 1] + y;
pxy[m] = pxy[m - 1] + x * y;
pyy[m] = pyy[m - 1] + y * y;
}From PairSeries.align() — core-api, com.schonfeld.betaservice.store.PairSeries
After that, any window of return indices [firstReturn .. lastReturn] is answered by differencing — all four moments at once, in O(1):
public WindowMoments moments(int firstReturn, int lastReturn) {
// ... bounds check elided ...
int before = firstReturn - 1;
return new WindowMoments(
lastReturn - firstReturn + 1,
px[lastReturn] - px[before],
py[lastReturn] - py[before],
pxy[lastReturn] - pxy[before],
pyy[lastReturn] - pyy[before]);
}PairSeries.moments() — the whole O(1) trick in nine lines
The payoff shows up in measurement, not just theory: the service's warm-query benchmarks are flat from w = 20 all the way to w = 12,600 — a fifty-year window costs the same as a one-month window, where the naive recompute would be roughly 600× slower. Warm queries are O(n) in the number of output days, full stop.
Same file, second idea: aligning two calendars honestly
Before any sums exist, the two series have to line up. Ticker and baseline don't trade on identical days — one may be halted, or listed on an exchange with different holidays. PairSeries.align walks both sorted date arrays like a merge, keeping only dates on which both have a price:
while (i < tickerDays.length && j < baselineDays.length) {
if (tickerDays[i] == baselineDays[j]) {
common[k] = tickerDays[i];
closeX[k] = tickerClose[i];
closeY[k] = baselineClose[j];
k++; i++; j++;
} else if (tickerDays[i] < baselineDays[j]) {
i++;
} else {
j++;
}
}The merge-intersection in PairSeries.align() — O(len(ticker) + len(baseline))
When a day is dropped, the next return spans the gap on both legs — each (x, y) pair covers exactly the same interval. What the code deliberately does not do is forward-fill the missing price: a carried-over close would fabricate a zero return on one leg while the other leg moved, and that fabricated zero biases beta toward 0. Dropping the day keeps the regression honest; filling it quietly corrupts it.
Things to try
- • Drag the window to a single element (hi = lo + 1). Naive needs 0 adds, prefix still needs 1 subtraction — the trick only wins for w ≥ 3, but it wins by miles.
- • Make the window span all 16 values. Naive does 15 adds; the prefix path is still exactly prefix[16] − prefix[0].
- • Slide the whole window right by one step. Notice the naive path redoes all its adds even though only two values changed — that waste is what O(n·w) means.
- • Look at the ops counter for w = 12,600: 12,599 adds vs 2 reads, per output day, for every day in the query.