PDA

View Full Version : 32-bit averaging help



Bobb Fwed
05-15-2010, 04:56 AM
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 (http://obex.parallax.com/objects/488/) - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database (http://obex.parallax.com/objects/493/) - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library (http://obex.parallax.com/objects/543/) - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm (http://obex.parallax.com/objects/546/) - Fast communication between two propellers (1.37MB/s @100MHz)!

Bean
05-15-2010, 05:02 AM
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. [RUSH - Freewill]

Chris Savage
05-15-2010, 05:15 AM
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
05-15-2010, 05:18 AM
@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 (http://obex.parallax.com/objects/488/) - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database (http://obex.parallax.com/objects/493/) - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library (http://obex.parallax.com/objects/543/) - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm (http://obex.parallax.com/objects/546/) - Fast communication between two propellers (1.37MB/s @100MHz)!

Bobb Fwed
05-15-2010, 05:20 AM
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 (http://obex.parallax.com/objects/488/) - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database (http://obex.parallax.com/objects/493/) - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library (http://obex.parallax.com/objects/543/) - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm (http://obex.parallax.com/objects/546/) - Fast communication between two propellers (1.37MB/s @100MHz)!

lonesock
05-15-2010, 05:25 AM
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
05-15-2010, 05:33 AM
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 (http://obex.parallax.com/objects/488/) - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database (http://obex.parallax.com/objects/493/) - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library (http://obex.parallax.com/objects/543/) - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm (http://obex.parallax.com/objects/546/) - Fast communication between two propellers (1.37MB/s @100MHz)!

lonesock
05-15-2010, 05:40 AM
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
05-15-2010, 06:12 AM
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
05-15-2010, 06:15 AM
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 [8^)

Jonathan

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

Bobb Fwed
05-15-2010, 06:31 AM
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 (http://obex.parallax.com/objects/488/) - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database (http://obex.parallax.com/objects/493/) - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library (http://obex.parallax.com/objects/543/) - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm (http://obex.parallax.com/objects/546/) - Fast communication between two propellers (1.37MB/s @100MHz)!

pullmoll
05-15-2010, 06:46 AM
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[ 2]
long avg32
long cog

PUB start(table_addr)
params[ 0] := table_addr
params[ 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 (http://pmbits.ath.cx/prop/)

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

Bobb Fwed
05-15-2010, 07:40 AM
@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 (http://obex.parallax.com/objects/488/) - Programmable Schmitt inputs, frequency reading, and more!
Simple Propeller-based Database (http://obex.parallax.com/objects/493/) - Making life easier and more readable for all your EEPROM storage needs.
String Manipulation Library (http://obex.parallax.com/objects/543/) - Don't allow strings to be the bane of the Propeller, bend them to your will!
Fast Inter-Propeller Comm (http://obex.parallax.com/objects/546/) - Fast communication between two propellers (1.37MB/s @100MHz)!