32-bit averaging help

Bobb Fwed · 2010-05-14 20:56

Any of you mathematicians know a way to average a bunch (20 to 100 -- the number is flexible at this point if there is some limitation) of 32-bit values without resorting to float math? The desire not to use float math is purely for the purpose of speed, so if the integer math method is slower than the float math, that won't work.

The two methods my feeble brain came up with won't work:
The normal add and divide method will likely overflow with the numbers I am using.
The other option of divide then add is also not practical as I will loose way too much precision.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
April, 2008: when I discovered the answers to all my micro-computational-botherations!

Some of my objects:
MCP3X0X ADC Driver - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm - Fast communication between two propellers (1.37MB/s @100MHz)!

Bean · 2010-05-14 21:02

Bobb,
What is your input value range ? In other words do the input values use ALL of the 32 bits ?

Bean

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Use BASIC on the Propeller with the speed of assembly language.
PropBASIC thread http://forums.parallax.com/showthread.php?p=867134

March 2010 Nuts and Volts article·http://www.parallax.com/Portals/0/Downloads/docs/cols/nv/prop/col/nvp5.pdf
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
There are two rules in life:
· 1) Never divulge all information
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
If you choose not to decide, you still have made a choice. [noparse][[/noparse]RUSH - Freewill]

Chris Savage · 2010-05-14 21:15

Bobb,

I don't know the details of your values...but if no two values will ever exceed a 32-bit value then you can do a running average always averaging the previous result with the next value by adding and dividing. This also works good if the values aren't stored, but coming in steadily. You save memory if you only need the average.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chris Savage

Parallax Engineering
·

Bobb Fwed · 2010-05-14 21:18

@Bean Good point. They are actually limited to 31-bits, it will stay away from the sign bit. But the numbers will be anywhere between a 5 or 6 bit value up to 30 or 31.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
April, 2008: when I discovered the answers to all my micro-computational-botherations!

Some of my objects:
MCP3X0X ADC Driver - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm - Fast communication between two propellers (1.37MB/s @100MHz)!

Bobb Fwed · 2010-05-14 21:20

The system cannot be a running average, it is essentially logging the last few minutes of values and averaging them. As time goes on the old values drop off.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
April, 2008: when I discovered the answers to all my micro-computational-botherations!

Some of my objects:
MCP3X0X ADC Driver - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm - Fast communication between two propellers (1.37MB/s @100MHz)!

lonesock · 2010-05-14 21:25

Will you be computing the average in Spin or PASM? You can split each number into Hi and Lo values (say 16 bits each), and keep a running sum of both, then do some math at the end for your division. And note that if you limit your number of samples to be a power of 2 (e.g. 32 or 64), the division and recombination step will be much easier.

Jonathan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lonesock
Piranha are people too.

Bobb Fwed · 2010-05-14 21:33

I will be using SPIN. I was already thinking the power thing (so I can just shift things around for quick math), probably 64 values would be sufficient.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
April, 2008: when I discovered the answers to all my micro-computational-botherations!

Some of my objects:
MCP3X0X ADC Driver - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm - Fast communication between two propellers (1.37MB/s @100MHz)!

lonesock · 2010-05-14 21:40

So something like (untested)

CON
  ShiftVal = 6

PUB t | i, sumLo, sumHi
  sumLo~
  sumHi~
  repeat i from |<30-63 to |<30
    sumLo += i & $FFFF
    sumHi += i >> 16

  sumLo += constant( |<(ShiftVal - 1) )     ' for rounding
  sumLo >>= ShiftVal            ' divide the low accumulator
  sumLo += sumHi << constant( 16 - ShiftVal ) ' divide the high accumulator and shift back into pos in 1 step
  ' sumLo now has the average value

Jonathan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lonesock
Piranha are people too.

localroger · 2010-05-14 22:12

If you know how many values you will be averaging before they come in, you could divide them individually by the number of samples before adding. It's not even that much more computationally intensive if you use a power of 2 for shift-divide.

lonesock · 2010-05-14 22:15

Bobb Fwed said...
...But the numbers will be anywhere between a 5 or 6 bit value up to 30 or 31.

The "5 or 6 bit" case would make pre-dividing by 64 inadvisable [noparse][[/noparse]8^)

Jonathan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
lonesock
Piranha are people too.

Bobb Fwed · 2010-05-14 22:31

As I said before: "The other option of divide then add is also not practical as I will loose way too much precision."

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
April, 2008: when I discovered the answers to all my micro-computational-botherations!

Some of my objects:
MCP3X0X ADC Driver - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm - Fast communication between two propellers (1.37MB/s @100MHz)!

pullmoll · 2010-05-14 22:46

Bobb Fwed said...
The system cannot be a running average, it is essentially logging the last few minutes of values and averaging them. As time goes on the old values drop off.

If you have 20..100 values where each value can be up to 31 bits, you will definitely need a 64 bit accumulation. I'd suggest to use a power of 2 number of values, like 64, and then pre-scale the addends. I would do it in PASM, as it is easier and, of course, faster to do 64 bit math there.

VAR
                long    params[noparse][[/noparse] 2]
                long    avg32
                long    cog

PUB start(table_addr)
        params[noparse][[/noparse] 0] := table_addr
        params[noparse][[/noparse] 1] := @avg32
        cog := COGNEW(@entry, @params)
        return cog => 0

PUB average
        avg32 := -1
        repeat while avg32 == -1
        return avg32

DAT
                org     0
entry
                mov     t1, par                          ' get address of parameters
                rdlong  table_ptr, t1                    ' get first parameter : table address
                add     t1, #4
                rdlong  result_ptr, t1                   ' get second parameter : result address

:wait
                rdlong  t1, result_ptr                   ' get result value
                cmp     t1, minus1                wz     ' is it -1?
        if_nz   jmp     #:wait                           ' no, wait

                mov     count, #64                       ' average 64 values
                mov     accu, #0                         ' clear 64 bit accu
                mov     accu + 1, #0
:loop
                rdlong  value, table_ptr                 ' read 32 bit value
                add     table_ptr, #4                    ' next address
                mov     value + 1, value                 ' value to less significant long also
                shr     value, #6                        ' more significant 26 bits in #25..0
                shl     value + 1, #32 - 6               ' less significant 6 bits in #31..26
                add     accu + 1, value + 1              ' add low
                addx    accu, value                      ' add high with carry
                djnz    count, #:loop

                sub     table_ptr, #4*64                 ' back off table pointer
                wrlong  accu, result_ptr                 ' write the result
                jmp     #:wait

table_ptr       long    0-0                              ' pointer to 64 longs to average
result_ptr      long    0-0                              ' pointer to result long
count           long    0                                ' counter value
accu            long    0, 0                             ' 64 bit accumulator
value           long    0, 0                             ' 64 bit value
t1              long    0
minus1          long    -1

The table can be a round-robin list where your new value automatically overwrites the oldest from the list.

If you want to use another table size, you would have to adjust the #6 and #32-6 accordingly (e.g. 7 for 128 values, 8 for 256 and so on).
If your values are signed longs, you would have to change the shr into an sar.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Pullmoll's Propeller Projects

Post Edited (pullmoll) : 5/14/2010 11:02:10 PM GMT

Bobb Fwed · 2010-05-14 23:40

@pullmoll Thanks! I didn't want to do it in PASM, I didn't want to use another cog, but I have modified it, so the cog is only alive when doing the needed calculations. These calcs are only needed once per second, so not too much urgency.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
April, 2008: when I discovered the answers to all my micro-computational-botherations!

Some of my objects:
MCP3X0X ADC Driver - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm - Fast communication between two propellers (1.37MB/s @100MHz)!

32-bit averaging help

Comments