0

Programming in C, this is for a microcontroller application, so I really care about computational efficiency here.

I have 16-bit signed integers coming in from an ADC at just north of 16 kHz. Every tick, I get 16 numbers. Of those, I need to average two different sets of 6, so the final output is a set of 6 numbers. Therefore, my application-specific question is how do I average six numbers with the minimum of computing overhead?

I know that with a set of numbers whose length is a power of two, I can divide using bit-shifting after the addition operations. Since I have 6 numbers, what's the best way to accomplish this?

Ben S.
  • 143
  • 6
  • If you discard the two extreme values of the six you have a power of 2 samples remaining. – Weather Vane Jan 17 '20 at 00:53
  • You can check https://stackoverflow.com/questions/5558492/divide-by-10-using-bit-shifts. This is for divide by 10, but it can be applied to divide by 6 as well. – wookiekim Jan 17 '20 at 00:55
  • Or, as you are averaging, you can also introduce a bit of filtering by adding twice the previous average to the six values, giving eight values, a power of 2. – Weather Vane Jan 17 '20 at 00:58
  • 1
    It is generally not possible to compute the average of six integers in integer arithmetic, because about 83% of the results are not integers and hence cannot be represented. Do you want to truncate, round-to-nearest-ties-to-even, round-to-nearest-ties-up, or something else? Does the result have to be completely accurate or can you allow some deviations? – Eric Postpischil Jan 17 '20 at 01:06
  • 2
    This does not make sense: “I need to average two different sets of 6, so the final output is a set of 6 numbers.” Averaging two different sets of numbers produces output of two numbers, not six numbers. (This matters because if you are averaging various sets of six numbers from 16, there may be overlap that can be used to eliminate redundant arithmetic. The problem must be specified clearly.) – Eric Postpischil Jan 17 '20 at 01:08
  • This seems like a more appropriate question for [codereview.se]. You should write a non-optimal version that clearly demonstrates the result you want, then they may be able to help you optimize it for the microcontroller. – Barmar Jan 17 '20 at 01:41
  • I don't understand. You have 16 numbers and on the output you get 6 numbers? Why 6? Why "two different sets of 6"? What sets? How are these sets created? Why the output is a set of 6 numbers? Can you give an example of 16 numbers and example calculations that result in the 6 numbers? Can you write and show a "naive" approach that you would write it in C, that would however work and give the correct answer(s)? What microcontroller do you use? What instruction sets are available on your processor? If the _count_ (not "length") of numbers is a power of two, then you could divide using a shift. – KamilCuk Jan 17 '20 at 01:41
  • come on guys, 16 - 12 = 4, so 4 numbers plus an average of 6 plus an average of 6 is a result of 6 numbers the 4 plus two averages. – old_timer Jan 17 '20 at 02:50
  • you can shift then you need to divide by two. if your processor has a multiply and you have an optimizing compiler like gcc, then you can try result = sum/6; and what you want to see is the compiler does a shift right then multiplies by 1/3 (even if you have a divide instruction) and maybe another few instructions of patching. this assumes your integers are not close to the limit of the variable size. you can also do this yourself and not hope the compiler does it. I dont know of a trick off hand doesnt mean there isnt one but I think you just have to do the divide by 3. – old_timer Jan 17 '20 at 02:53
  • Which microcontroller? Which compiler? Anyway... 1. Trust your compiler, most of them optimize better than you could express in C. -- 2. Check the performance *by measurement(!)*. Don't guess. -- 3. Only if the performance is too low, think about optimizing. For this look at the generated assembly and reason why it is too slow. – the busybee Jan 17 '20 at 06:54
  • @EricPostpischil It makes perfect sense. Every tick, I get sixteen numbers. Take six of them, and average them to produce a single number. That leaves ten of the original sixteen. Take six more from the set of ten, average them, and get another single number. That's two distinct numbers from averaging, and four more that were untouched. Two plus four is six, yes? – Ben S. Jan 19 '20 at 18:00
  • @KamilCuk please see my response to Eric. – Ben S. Jan 19 '20 at 18:00
  • @WeatherVane I thought of that, but 1) I don't seem to get any outliers and 2) discarding two sensors reduces my SNR by sqrt(2). – Ben S. Jan 19 '20 at 18:01
  • @old_timer I am using gcc, so I'll just try the division operator and look into the compiled instructions. For my application, if my integers get close to the variable limit, I have a completely different set of problems! – Ben S. Jan 19 '20 at 18:03
  • @thebusybee It's an NXP Kinetis K66 uC using the gcc compiler. I think I'll have to just rig up my logic analyzer and watch the signals to see if it's firing in time with all this math going on. – Ben S. Jan 19 '20 at 18:06
  • If you don't get any outliers then what is the benefit of averaging over taking a single reading? Discarding two extreme values isn't an unusual technique. – Weather Vane Jan 19 '20 at 18:06
  • @WeatherVane they're six identical (in theory) sensors, all pointed at the same event. By using six, I get a better SNR by a factor of sqrt(6), and discarding two of them would reduce that. – Ben S. Jan 19 '20 at 18:08
  • @Barmar thanks for pointing me in the Code Review direction. I'll post there after I do some performance checks and decide if I need further oprimization. – Ben S. Jan 19 '20 at 18:09
  • @BenS.: Put that in the question. – Eric Postpischil Jan 19 '20 at 18:42
  • I don't understand. Can you write it mathematically? Can you write it in C? Please try not to describe what you want to do, show what you want to do,using code or some notation. You mean you want to write `typedef struct { int avg1, avg2; } type; type func(int n[16]) { return (type){ (n[0]+n[1]+n[2]+n[3]+n[4]+n[5])/6, (n[6]+n[7]+n[8]+n[9]+n[10]+n[11])/6 }; }`? What should happen with `n[12..15]`? – KamilCuk Jan 19 '20 at 21:45
  • Your CPU runs at 180MHz and your input stream is at 16KHz. So your MCU has time to execute ~11250 instructions in between every sensor-readout (16KHz cycle). Even after some generous rounding due to interrupt handling and actually receiving the bytes, I'd argue that you do not need to hand-optimize the integer averaging code part. There are certainly other things to consider for optimization than saving 20-30 instructions of a 10000+ instruction execution window. – markus-nm Jan 21 '20 at 13:55

0 Answers0