Running sum of the last n integers in an array

Question

Let's suppose that a process receives a new integer every 60 seconds. I would like to keep a running total of the last 5 numbers. For example:

3 1 99 10 8 0 7 9 --> running total is 10+8+0+7+9==34
       <--------->

Sixty seconds later, we receive a new integer. The list of received integers now looks like this:

3 1 99 10 8 0 7 9 2 --> running total is now 8+0+7+9+2==26
          <-------->

It's easy to implement this if you have storage space to save the last 5 integers. I'm trying to come up with an algorithm that's more memory efficient than that. Does anybody have any ideas?

Answer 1

Since you can reconstruct the last n numbers, for example if you feed in n zeros, anything you do is equivalent to storing the last n numbers.

Assuming the numbers can be truly random and each number is b bits long, any correct algorithm can therefore exactly reproduce nb random bits. This requires at least nb bits of storage.