# Rolling Sum

**URL:** <https://discourse.julialang.org/t/rolling-sum/30793>\
**Category:** Statistics\
**Tags:** question\
**Created:** [November 6, 2019, 2:01pm UTC](https://discourse.julialang.org/t/rolling-sum/30793 "2019-11-06T14:01:50Z")\
**Posts on this page:** 9\
**Page:** 2

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [November 7, 2019, 1:10pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/22 "2019-11-07T13:10:37Z")

</div>

To clarify, there probably isn’t a faster way: for a vector of length L, the cumulative sum can be computed in `L` operations. Therefore a rolling sum of length `n`, for arbitrary `n`, can be computed in `2L` operations. A naive rolling sum of length `n` is `n*L` operations, which for `n>2` is slower than using `cumsum`. For very large rolling sums, the difference will be dramatic.

This focus on operations count ignores roundoff errors, which ~~are indeed much~~ may be worse for the `cumsum` approach. If that’s important to you, then @klaff’s [Rolling Sum - #4 by klaff](https://discourse.julialang.org/t/rolling-sum/30793/4) is a better approach. That one is also `2L`, so there’s no real reason not to use it.

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [November 7, 2019, 2:01pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/23 "2019-11-07T14:01:13Z")

</div>

> [@tim.holy](#):
>
> This focus on operations count ignores roundoff errors, which are indeed much worse for the `cumsum` approach. If that’s important to you, then @klaff’s [Rolling Sum](https://discourse.julialang.org/t/rolling-sum/30793/4) is a better approach. That one is also `2L` , so there’s no real reason not to use it.

Out of curiosity, why do you say that the cumsum approach is worse than the

```julia
    out[i] = out[i-1]-a[i-1]+a[i+n-1]

```

technique proposed in @klaff’s approach?

Admittedly I haven’t given much thought to this question, but I don’t see any obvious reason why one approach would be better than the other. And in some specific cases (for example when dealing with positive numbers), my intuition would even lead me to favor the cumsum approach (again, just intuition, I haven’t performed a serious error analysis…)

---

<div class="post-metadata">

**Author:** ![klaff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klaff/32/7637_2.png) [@klaff](https://discourse.julialang.org/u/klaff)\
**Post date:** [November 7, 2019, 2:18pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/24 "2019-11-07T14:18:08Z")

</div>

Wouldn’t an approach around Base.cumsum need to allocate arrays for the two intermediate sums? Maybe I’m not thinking correctly about how that would work.

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [November 7, 2019, 2:23pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/25 "2019-11-07T14:23:50Z")

</div>

No, there is only one array of cumulative sums. The two intermediate partial sums (that are subtracted from one another in the end) are two elements of the same array.

There could be a second array if you wanted to also store the rolling sums (instead of computing them on the fly, when the window size is known, using a single subtraction operation).

---

<div class="post-metadata">

**Author:** ![klaff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klaff/32/7637_2.png) [@klaff](https://discourse.julialang.org/u/klaff)\
**Post date:** [November 7, 2019, 2:32pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/26 "2019-11-07T14:32:07Z")

</div>

Got it, thanks. Caffeine still being absorbed this morning.

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [November 7, 2019, 2:37pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/27 "2019-11-07T14:37:14Z")

</div>

I haven’t done a serious analysis either. For the purposes of discussion let’s consider a list of numbers that are uniformly distributed between 0 and 1. The magnitude of the cumsum grows linearly with `i`, and consequently once you’ve summed `2/eps()` of them together you’ll stop incrementing altogether due to a complete loss of precision. In contrast

```julia
out[i] = out[i-1]-a[i-1]+a[i+n-1]

```

intuitively seems like it should accumulate error as `sqrt(i)`.

---

<div class="post-metadata">

**Author:** ![klaff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klaff/32/7637_2.png) [@klaff](https://discourse.julialang.org/u/klaff)\
**Post date:** [November 7, 2019, 2:41pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/28 "2019-11-07T14:41:17Z")

</div>

The threaded version I wrote (trolling\_sum) recomputes the sum at the beginning of each thread’s segment (necessary so the threads can be independent), which limits the accumulated error.

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [November 7, 2019, 2:43pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/29 "2019-11-07T14:43:32Z")

</div>

> [@tim.holy](#):
>
> In contrast
> 
> ```julia
> out[i] = out[i-1]-a[i-1]+a[i+n-1]
> 
> ```
> 
> intuitively seems like it should accumulate error as `sqrt(i)` .

On the other hand, this formula is prone to cancellations (where the relative error is unbounded), whereas in the cumsum of positive numbers, the relative error at each operation is (as you noted) bounded by eps().

But I’ll try to avoid derailing this thread any more, and perform a real error analysis instead of waving my hands 🙂

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [November 7, 2019, 2:45pm UTC](https://discourse.julialang.org/t/rolling-sum/30793/30 "2019-11-07T14:45:36Z")

</div>

I just want to pop in here and say that the beauty of RollingFunctions.jl is mostly in its ease. I’ve used it many times to create rolling versions of my own functions. It strikes the balance between general functionality and performance quite well. It already uses `views` and very tight loops.

If you are doing something simple like a sum, of course a specialized method will be faster.

[Previous page](https://discourse.julialang.org/t/rolling-sum/30793.md?page=1)