Improving the efficiency of exponential smoothing for binary digits Let's say I'm a stock exchange, and I have an order flow for Apple shares. Let's say those numbers look like:


*

*10,000 (buy)

*-3,100 (sell)

*24,243 (buy)


These orders come in very quickly. What I want to know, in realtime, is the balance of the orders, with respect to overall volume. Do buys outweigh sells?
In the end, I want a number that is between -1 and 1, representing sell or buy.
I created a moving average of the form:
$$V_{i+1} = S\alpha + V_i(1-\alpha)$$
where:


*

*$S$ is the side for the individual share, so -1 (sell) or 1 (buy).

*$V$ is my variable estimating the balance of the flow (what we want).

*$\alpha$ is the decay rate

*$i$ is the $i$'th share


The problem:
If I get an order of a million shares, I have to evaluate this formula recursively one million times.
What shortcut or reasonable approximation can I make, so I can apply each order in one step, rather than having to loop over every individual share?
 A: I'd do something along those lines:
First of all you can solve your recurrence in closed form.
$$
V_{i+1} = \alpha S + (1 - \alpha)V_i = \alpha \left(1 + (1 - \alpha) \right)S + (1-\alpha)^2V_{i-1} = \alpha \left(1 + (1 - \alpha) + (1 - \alpha)^2 \right)S + (1-\alpha)^3V_{i-2} = ... = \alpha \left(\sum_{j=0}^{k} (1 - \alpha)^j \right)S + (1-\alpha)^{k+1}V_{i-k} = \alpha \left( \frac{1 - (1-\alpha)^{k+1}}{\alpha}\right)S + (1-\alpha)^{k+1}V_{i-k} = S + (1-\alpha)^{k+1}(V_{i-k}-S)
$$
for $k=i$ we have
$$
V_{i+1} = S + (1-\alpha)^{i+1}(V_0 -S)
$$
Rewriting this in terms of $i$ instead $i+1$ we have
$$
V_i = S + (1-\alpha)^i (V_0 - S)
$$
therefore your problem is characterized by $(1-\alpha)^i$, if you can compute this efficiently with a further multiplication and a couple of sums you're done. Observe that (assuming $i$ even)
$$
(1-\alpha)^i = (1-\alpha)^{i/2}(1-\alpha)^{i/2}
$$
The time complexity of that recurrence is
$$
T(i) = 1 + T(i/2)
$$
which has solution $T(i) = O(\log i)$, if you then have $i = 10^6$ you should get the computation done with $T(10^6) \approx 6 log 10$ iterations.
