0

I need to make an efficient algorithm, for moving integers.

For e.g,,an avg of 100 items. So as the 100 numbers come, the average for 1..100 numbers.. as 101 number comes average of 2..101.. as 102 number comes average of 3..102..

I thought of one solution but i cant come up so that minimum numbers can be stored(as after wards, i have to do in microprocessor, but first, efficient in C/C++):

Step 1: store numbers from 1..100 and take average step 2: replace 1 by 101, and take average: 101,2,3...100 step 3: replace 2 by 102, and take average: 101,102,3,4...100

But it is not efficient, as i need to use less division operator also.

Can anyone help me out please.

user2387900
  • 215
  • 1
  • 6
  • 13
  • google for moving average – Mitch Wheat Jul 08 '13 at 02:15
  • 1
    If you store the sum (rather than the average) of the previous step, you won't have to recompute the average for all 100 numbers completely. You just substract one value from the sum and add the new value, and the you divide the sum by 100. That doesn't reduce the number of divisions, though. – jogojapan Jul 08 '13 at 02:15
  • You *need* to use the division operator less? Or you just feel like asking that to make the problem harder and the solution "faster"? – Potatoswatter Jul 08 '13 at 02:16
  • Is this a duplicate? http://stackoverflow.com/questions/10990618/calculate-rolling-moving-average-in-c-or-c – jogojapan Jul 08 '13 at 02:20
  • @jogojapan it doesn't reduce the division, its ok, but to make it more efficient, what could be other approach. ? – user2387900 Jul 08 '13 at 02:20
  • @Potatoswatter in microprocessor, division takes many cycles, so it should be less as i need to make it efficient. – user2387900 Jul 08 '13 at 02:21
  • @user2387900: If your CPU has a hardware division unit, then it will probably be pipelined, and so the fact that it takes many cycles will affect only latency, not throughput... – Oliver Charlesworth Jul 08 '13 at 02:24
  • 1
    "Microprocessor" is any microchip that can execute a complete instruction set. If you mean "8-bit microcontroller", then that is much more specific. But merely having certain hardware doesn't justify such a design decision, and "use division less" isn't a real engineering requirement. If you need to restrict it to shift operations or something, or if some results may be approximate, then say so. – Potatoswatter Jul 08 '13 at 02:31
  • I voted to close as a duplicate, not for a failure to demonstrate a minimal understanding, which I don't think applies here. There's certainly a failure to think, but the same applies to the answer Mitch gave and then deleted when I pointed out its obvious flaw. – Jim Balter Jul 08 '13 at 04:33
  • If you have a continuous stream of input you can do a poor-man's average on the fly, which is basically this: `average = average * 0.99 + newvalue * 0.01` - it has a basic 'boot-up' time, but works nicely in many situations. – paddy Jul 08 '13 at 05:11
  • average = average * 0.99 + newvalue * 0.01, i did not got this perfectly...i have a stream of any random values...@paddy – user2387900 Jul 09 '13 at 21:35
  • i read one formula : accumulator = (alpha * new_value) + (1.0 - alpha) * accumulator,,,,but i am not understanding it ??/ from http://stackoverflow.com/questions/10990618/calculate-rolling-moving-average-in-c-or-c?lq=1 ... Do you think, keeping in the array would be the best option ? – user2387900 Jul 09 '13 at 21:37

2 Answers2

2

Your basic approach is good: use a circular buffer with 100 elements. A key insight: say you're at the "replace 2 by 102" stage, and 2 is 50 while 102 is 70 - the total will change by the difference of +20: you just divide the new total by 100 to get the new average, without adding up all the elements again.

In the unlikely event that the division is so slow it's making a significant and problematic difference to your overall performance, then there's only a couple things you could try (but do measure - they might actually slow you down depending on your exact hardware):

  • if the range of numbers if small, you could create a lookup table (i.e. an array) from value to 100th of the value, then by adding/removing these scaled values to the total you directly maintain the average

  • check whether your system is faster using float or double types (counterintuitively, some systems are)

  • there are some bizarre "recipes" for division by 100 on the 'net, such as (((((uint32_t)A * (uint32_t)0x47AF) >> 16U) + A) >> 1) >> 6 from http://embeddedgurus.com/stack-overflow/2009/06/division-of-integers-by-constants/

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
  • 6
    It's worth noting that this approach can leading to numerical problems in floating-point arithmetic (adding `x[n]` to the sum and then subtracting `x[n]` later may not exactly cancel). In integer arithmetic, this works perfectly. – Oliver Charlesworth Jul 08 '13 at 02:18
  • Also, division be exactly 100 every time doesn't account for the case where the circular buffer is not yet full. Usually that can just be called part of the program startup. And usually the buffer size can be made a power of 2 to simplify that part. Also remember to round-to-nearest by adding half the buffer size to the sum before performing floored division. – Potatoswatter Jul 08 '13 at 02:49
  • @Potatoswatter: true - I've focused on optimisations that can kick in once in steady-state mode with the buffer full. – Tony Delroy Jul 08 '13 at 02:51
1

The easiest way to do a moving average is with a moving sum. Sum the numbers n[0] through n[99] to start; the average is this sum divided by 100. For the next sum, subtract n[0] and add n[100]; divide by 100 again for the average.

This works best with integers as there won't be any rounding errors in the sum; with floating point any errors will accumulate and get worse as you go along.

If you're using positive integers, you can eliminate division by making your window size a power of 2. Using 128 instead of 100 means you can divide using a right shift of 7 on the sum.

You can also eliminate division by multiplying by the inverse. Instead of dividing by 100, multiply by 1/100. If you're working with integers you may need to use fixed point, and you may also run out of bits if you're not careful.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • so u suggest after average of n[0] to n[99], i should remove n[0] and add n[100] at the n[0] position only ? and i take an array of [100].. – user2387900 Jul 09 '13 at 21:40
  • @user2387900 what I mean is to keep the sum from the previous calculation and just change it. So the first sum (sum0) is the total of n[0] through n[99]. The second sum (sum1) is sum0-n[0]+n[100]. The third would be sum1-n[1]+n[101]. Etc. – Mark Ransom Jul 09 '13 at 21:44