Large numers without overflow

I am attempting to build an Amp-hour meter for 12V DC applications. I want to make current measurements (either every 10 seconds for 24 hours - 8640 in total, or every minute for a week - 10080 total) and use the result to calculate average amp-hours.
I'm trying to keep the hardware simple, avoiding external memory if possible and probably using an 18X with RTC and LCD to show the results.
I plan to use READADC10 to get the measurements. A formula to calculate the running average is
xbar = (N. old xbar + latest x) / (N+1)
after N+1 measurements.
I'm looking for advice on avoiding overflow while not losng too much detail in performing this calculation. Or is there a difernet approach I should try?
Thanks,
Derek

I do not know a way over that, but seeing as you have already got the base of i2c setup for the RTC you jsut as well use eeprom or ram chip, but bare in mind that the ram only stores data while it is powerd but has next to now read/write time
________
Lorenzo Bandini

Hi

This is a tricky one because the overall sum of readings will be a very large number and doing traditional division on this isn't easy.

However I can think of a way that would work, but could be slow:

1. Have the sum value stored in multiple words. Say 4 words, this will store a sum of 65536^4 - 1, a big number !
a) You need a clear routine to just zero the Sum bytes. Easy.

b) You need an addition routine to add a word value to this total. This really isn't that difficult to do. You just do it like normal arithmetic using carry to ripple up the words.

2. The division routine is the simplest form ... You need a subtractrion routine to subtract N (a word) from the Sum. You keep subtracting until the Sum <= 0. The count of times you needed to do this is the result. THIS MAY BE SLOW THOUGH ! Accurate answer though.

Worth a try perhaps evenso. The code won't be very long for this.



Edited by - jeremy leach on 29/04/2007 22:00:43

You could try just using a large value like 50-100 or so as your "N" value, and just multiply that by the previous average to try to "weight" it. What is the current range that you are measuring? (i.e. how many digits is each measurement?). That might give you a decent approximation.

second thought: You compute your running average for a certain number of samples that you can comfortably do without overflowing. Then you store that "average" in the onboard EEPROM (you should have 256 bytes free). If each average is one word, that gives you 128 samples (or 256 if you can get it down to 1 byte). As long as you can calculate enough samples in your running average, say 80 or so if your average is going to be a 16-bit number, then you can average all of your stored averages at the end, and it should still be valid without losing any detail (except for the decimal part).

Derek, on second thoughts there's a quick way with complete accuracy, but it will take
some explaining. Ok, here goes...

<b>Av0 = SumI / N </b>
Where:
Av0 is the previous average.
SumI is the sum of all the previous current readings.
N is the number of samples.

This division can be expressed as a whole and remainder part:

<b>Av0 = Whole0 + (Remainder0/N) </b>

Therefore SumI = (Whole0 * N) + Remainder0 ....Equ1

The new average is:

Av1 = (SumI + I1)/(N+1)

Using Eqn1...
Av1 = [(Whole0 * N) + Remainder0 + I1]/(N+1)
<b>Av1 = [(Whole0 * N)/(N+1)] + [Remainder0 / (N+1)] + [I1/(N+1)] ...Eqn2 </b>

So we've got three terms to evaluate to get a new average ( note the whole objective here
is to be able to calculate a new average value from the old average value, the new current
value and the new sample count).

One thing to point out first is we know that because the current values are Word values
the average value will always be a Word value too.

<b>Term1 = [(Whole0 * N)/(N+1)] </b>
Whole0 and N are both Word values, which multiplied together will be a double word (ie
overflow), however the result of this division is always going to be a Word value because
it involves N/N+1.

My way of calculating this Term1 without overflow is to use an iterative technique. Imagine
we've got three words in this division operation:
(Word1 * Word2) / Word3
= (Word1/Word3) * Word2
= (Whole + Remainder/Word3) * Word2
= (Whole * Word2) + [(Remainder * Word2)/Word3]

Now if, as in our case, the division is going to be a word value, then we know that
(Whole * Word2) isn't going to overflow. And the term [(Remainder * Word2)/Word3] is in
exactly the same form as we started with, ie A*B/C. What this means is that this lends
itself to an iterative technique. We start by setting a 'WholeTotal' variable to zero,
we then work out a whole value, add to this total, then submit the [(Remainder * Word2)/Word3]
bit back into the routine. We keep doing this until the whole part is 0 and we're left with
a remainder.

The end 'WholeTotal' value, and the remainder value are the result of this division, and
all this occurs without overflow.

<b>Term2 = [Remainder0 / (N+1)] </b>
Here, Remainder0 is a word value, so is N+1, so we simply get whole and remainder values
from this division using normal Word operators &quot;/&quot; and &quot;//&quot; (modulus).

<b>Term3 = [I1/(N+1)] </b>
Again all Word values and we get whole and remainder values using normal word operators.


<b> END RESULT </b>
Ok, so now we have evaluated all three terms and have got whole and remainder values.
We now add the Whole values together to give a WholeTotal. Then we add the remainder
values together. If the RemainderTotal is &gt; N+1 then we add another 1 to the WholeTotal
and set RemainderTotal = RemainderTotal - N - 1.

The WholeTotal and RemainderTotal are the new Average, Av1. Note that accuracy isn't lost
at all however many times you calculate a new average value.

If you want to, you can then do a similar calculation to convert the remainder value into
decimal digits for display purposes.


I appreciate this seems a bit long-winded but I'm sure it will work and the code
actually wouldn't be that long. It will also be quick because Term1 won't need many
iterations at all to calculate. If I get some time I can write some code.

This is actually a generic technique for keeping an accurate average of Word values (I think technically it's the arithmetic mean of ALL your current readings, rather than the moving average which is normally only on the previous so many readings).


Edited by - jeremy leach on 30/04/2007 08:16:34

Here's the code. It's a code 'module' that can run on any picaxe. It includes a short demo of how to use it. Basically it will maintain a precise moving average and you can have up to 65535 samples.

It also includes a conversion routine to express the remainder in 4 decimal places so you can use for display purposes. This little routine could be extracted and used for other display routines if necessary too.

<code><pre><font size=2 face='Courier'>
#picaxe 18x

#rem
#############################################################################
# #
# RUNNING AVERAGE DEMO #
# #
#############################################################################
#endrem

Symbol NewX = w6

Demo:
'Run the simulator, and look at the word values. Put simulator breaks after each
'run of UpdateAverage, to see the values returned.

Gosub InitialiseAverage 'sets it to zero
NewX = 12345
Gosub UpdateAverage 'Giving result Av = 12345 (Whole = 12345, Remainder = 0)
NewX = 20342
Gosub UpdateAverage 'Giving result Av = 16343.5 (Whole = 16343, Remainder = 1)
NewX = 12
Gosub UpdateAverage 'Giving result Av = 10899.6666... (Whole = 10899, Remainder = 2)
NewX = 54322
Gosub UpdateAverage 'Giving result Av = 21755.25 (Whole = 21755, Remainder = 1)

'Express the Remainder of the last result in 4 decimal places.
Gosub FourDP
End


#rem
#############################################################################
# #
# RUNNING AVERAGE MODULE #
# #
# Code Version :1A #
# Date :May 2007 #
# PICAXE Type :18x #
# Editor Software :5.07 #
# #
# Author :Jeremy Leach #
# #
#############################################################################

INTRODUCTION:
-------------

This code enables a precise running average (arithmetic mean) of Word values to be kept.
Features are:

- Does not need to keep all the values read.
- The average is held as a Whole and Remainder part and there is no loss of
accuracy as time progresses.
- The code is relatively fast and compact.

METHOD:
-------

Av0 = The previous average = SumX / N
Where:
SumX is the sum of all the previous readings.
N is the number of samples.

This division can be expressed as a whole and remainder part:

Av0 = Whole0 + (Remainder0/N)

Therefore SumI = (Whole0 * N) + Remainder0 ....Equ1

The new average is:

Av1 = (SumX + X1)/(N+1)

Using Eqn1...
Av1 = [(Whole0 * N) + Remainder0 + X1]/(N+1)
Av1 = [(Whole0 * N)/(N+1)] + [Remainder0 / (N+1)] + [X1/(N+1)]
Av1 = Term1 + Term2 + Term3

The method used evaluates Av1 from this expression.
#endrem


'############################################################################
'# VARIABLES #
'############################################################################

'Word0 (b0 and b1)
Symbol TotalWholeW = w0
Symbol WholeW = w0
'Word1 (b2 and b3)
Symbol Re_mainderW = w1
'Word2 (b4 and b5)
Symbol Word1 = w2
'Word3 (b6 and b7)
Symbol Word2 = w3
'Word4 (b8 and b9)
Symbol Word3 = w4
'Word5 (b10 and b11)
Symbol TempW = w5
Symbol DecimalPlaces = w5
'Word6 (b12 and b13)
'Symbol NewX = w6 '!!!Put at start of code !!!

'############################################################################
'# CONSTANTS #
'############################################################################

'RAM constants
Symbol RAM_AvWholeW = 80 '&amp; 81
Symbol RAM_AvRemainderW = 82 '&amp; 83
Symbol RAM_SamplesW = 84 '&amp; 85
Symbol RAM_TotalWholeW = 86 '&amp; 87
Symbol RAM_TotalRemainderW = 88 '&amp; 89
Symbol RAM_LastTotalWholeW = 90 '&amp; 91

'############################################################################
'# ROUTINES #
'############################################################################


InitialiseAverage:
'Sets RAM_SamplesW, RAM_AvWholeW and RAM_AvRemainderW to zero.
Poke RAM_SamplesW, 0,0
Poke RAM_AvWholeW, 0,0
Poke RAM_AvRemainderW, 0,0
Return


UpdateAverage:
'Updates the average value, based on the NewX word value, the new SamplesW value and the
'previous average value.

'ON ENTRY: NewX is the new sampled Word value.
'ON EXIT : The RAM_AvWholeW and RAM_AvRemainderW contain the new average.
' So does WholeW and Re_mainderW.

'Increment Samples, leaving the updated samples value in Word3.
Peek RAM_SamplesW,Word Word3
Inc Word3
Poke RAM_SamplesW,Word Word3

'Set the Whole and Remainder totals to zero.
Poke RAM_TotalWholeW, 0,0
Poke RAM_TotalRemainderW, 0,0

'Evaluate Term1 = [(Whole0 * N)/(N+1)] and set the Whole and Remainder totals.
Peek RAM_AvWholeW, Word Word1 'Load Whole0 into Word1
Word2 = Word3 - 1 'Word2 = N
Gosub Word1Word2DivWord3

Gosub UpdateTotals

'Evaluate Term2 = [Remainder0 / (N+1)] and update the Whole and Remainder totals.
Peek RAM_AvRemainderW, Word Word1
WholeW = Word1 / Word3
Re_mainderW = Word1 // Word3

Gosub UpdateTotals

'Evaluate Term3 = [X1/(N+1)] and update the Whole and Remainder totals.
WholeW = NewX / Word3
Re_mainderW = NewX // Word3

Gosub UpdateTotals

'Set the Whole and Remainder values for the final average result.
Peek RAM_TotalWholeW, Word WholeW
Peek RAM_TotalRemainderW, Word Re_mainderW

'Save this result
Poke RAM_AvWholeW, Word WholeW
Poke RAM_AvRemainderW, Word Re_mainderW
Return


UpdateTotals:
'Update the RAM_TotalWholeW and RAM_TotalRemainderW values.

Peek RAM_TotalRemainderW, Word TempW
TempW = TempW + Re_mainderW

'Adjust values if new remainder exceeds N+1.
WholeW = TempW/Word3 + WholeW
TempW = TempW // Word3

Poke RAM_TotalRemainderW, Word TempW

Peek RAM_TotalWholeW, Word TempW
TempW = TempW + WholeW
Poke RAM_TotalWholeW, Word TempW
Return


Word1Word2DivWord3:
#rem
Calculate (Word1 * Word2) / Word3.

ON ENTRY: Word1,2 and 3 are loaded appropriately.
ON EXIT: WholeW holds the Whole part of the result.
Re_mainderW holds the remainder of the result.

NOTE: This routine assumes that the result is a Word value.

Code is based on ...
(Word1 * Word2) / Word3
= (Word1/Word3) * Word2
= (Whole + Remainder/Word3) * Word2
= (Whole * Word2) + [(Remainder * Word2)/Word3]
#endrem

'Initialise
TotalWholeW = 0
Poke RAM_LastTotalWholeW, 255,255

'Iterate
Do
TempW = Word1/Word3 'Set TempW to be the whole part of Word1/Word3
TotalWholeW = TempW * Word2 + TotalWholeW
Re_mainderW = Word1//Word3 'Calc the remainder part of Word1/Word3

'Check if the last TotalWhole value is the same as this one.
Peek RAM_LastTotalWholeW, Word TempW
If TempW = TotalWholeW Then
'Adjust the Whole and Remainder values if necessary
WholeW = Re_mainderW * Word2 / Word3 + WholeW
Re_mainderW = Re_mainderW * Word2 // Word3

Exit
Endif

'Save this TotalWhole value as the Last TotalWhole Value.
Poke RAM_LastTotalWholeW, Word TotalWholeW

'Set up a new iteration.
Word1 = Re_mainderW
Loop
Return


FourDP:
'This converts a remainder value into a 4 decimal place value.

'ON ENTRY: Re_mainderW holds the remainder word
' Word3 holds the denominator word

'ON EXIT : DecimalPlaces holds a Word where the last 4 digits are the
' decimal place values. E.g if the decimal places were 0.1234
' then DecimalPlaces would hold 1234.

'NOTE: This uses the calculation DP = Remainder/Denominator * 10000

Word1 = Re_mainderW
Word2 = 10000
Gosub Word1Word2DivWord3
DecimalPlaces = WholeW
Return

</font></pre></code>

Edited by - jeremy leach on 30/04/2007 14:13:56

There's a slight issue in Word1Word2DivWord3 I've got to address. Will update the code when I have.

&gt;&gt;&gt;CODE NOW UPDATED.

I was hoping the code could fit into an 08M. It can just but with only bytes to spare. I haven't tried to optimise it though, so there might be some savings to be made.

Word1Word2DivWord3 is a handy routine in general. For instance suppose you want to know a variable percentage of a big number, say 83% of 63126. Normally you'd try 83 * 63126 / 100 but this would result in overflow. This routine won't.


Edited by - jeremy leach on 30/04/2007 14:27:24

Jeremy,
Many thanks for those comprehensive replies. I haven't yet digested the early description of the solution. I'll than move on to understand the detailed code. Then I will move on to coding my problem.
Thanks again,
Derek

Hope it helps. The last idea is much better than the first, and I was interested in developing it for my own purposes too, because it has the very useful spin-off routine to do the accurate division.