I have a sequence of $(X,Y)$ pairs: $(X_0,Y_0),\ldots(X_N,Y_N)$
I add a new pair to the sequence at every time step, $t$
At some time in the distant future, $t_n$, I want to use a function to reduce the sequence into a number.
The function takes the sequence of pairs and an input $Z$: $$ f(Z) = \left(\frac{1}{X_0}-\frac{1}{Z}\right)\cdot Y_0 + \left(\frac{1}{X_1}-\frac{1}{Z}\right)\cdot Y_1 + \ldots + \left(\frac{1}{X_N}-\frac{1}{Z}\right)\cdot Y_N $$ My problem:
I don't want to store every pair of these sequences. This would require too much space.
I want to reduce the sequence into some kind of incremental representation that will allow me to
- Store much fewer pairs
- Compute $f(Z)$ without any loss of precision, at any time
How do I go about doing this?
The function you have is this: $$f(Z) = \left(\frac{1}{X_0}-\frac{1}{Z}\right)Y_0 + \left(\frac{1}{X_1}-\frac{1}{Z}\right)Y_1 + \ldots + \left(\frac{1}{X_N}-\frac{1}{Z}\right)Y_N$$
Expand the multiplications: $$f(Z) = \frac{Y_0}{X_0}-\frac{Y_0}{Z} + \frac{Y_1}{X_1}-\frac{Y_1}{Z} + \ldots + \frac{Y_N}{X_N}-\frac{Y_N}{Z}$$
Rearrange: $$f(Z) = \left(\frac{Y_0}{X_0}+ \frac{Y_1}{X_1} + \ldots + \frac{Y_N}{X_N} \right) - \left( \frac{Y_0}{Z} + \frac{Y_1}{Z} + \ldots + \frac{Y_N}{Z}\right)$$
So we get: $$f(Z) = S - \frac{T}{Z}$$ where $$S = \frac{Y_0}{X_0}+ \frac{Y_1}{X_1} + \ldots + \frac{Y_N}{X_N}$$ and $$T = Y_0 + Y_1 + \ldots + Y_N$$ Those $S$ and $T$ are easy to update when you get an additional pair.