PDA

View Full Version : Number Sort Algorithm



T.Jackson
- 21st July 2007, 03:28
Number sorting algo that I spat out yesterday can sort 10,000 64 BIT numbers in 15 seconds on a PIII 866MHz. Considering the simplicity of it - this is fast! The code is in Visual Basic but shouldn't be too hard to port to PBP. I don't have time to do it at the moment, anyone up for it? If you feel that you have an even better solution, please post it here.



Private Function Sort_Numbers(ByRef Num_Array)

' (An easy to get your head around algo)

Dim Compare_A As Long
Dim Compare_B As Long
Dim Swap As Long
Dim Array_Pos As Long
Dim i As Long
Dim j As Long
Dim k As Long

i = UBound(Num_Array) ' Size / last index of array
k = i ' Copy of i used to show progress - indexes sorted thus far

Do Until i = 0 ' Loop until entire list has been sorted
Compare_A = Num_Array(i) ' Load comparison var (starting at bottom of list)
For j = Array_Pos To i ' Try to find a bigger num (starting from top of list)
Compare_B = Num_Array(j) '
If Compare_B > Compare_A Then ' This num bigger?
Swap = Num_Array(i) ' Swap them
Num_Array(i) = Compare_B '
Num_Array(j) = Swap
Array_Pos = j '
Exit For ' Bail out, but we need to come back (might be an even bigger num)
End If
Next
If j > i Then ' Num is in correct pos - nothing bigger exists
i = i - 1 ' Move to next index
Array_Pos = 0

' Show user how many have been sorted so far (yes this will slow things down marginally)
Progress = "Sorted " & (k - i) & " numbers"
DoEvents
End If
Loop

End Function

T.Jackson
- 21st July 2007, 04:06
As you can see from the screen grab below, it sorted 1,000 numbers in 697mS. This figure starts to badly degrade with more than 1,000.

<img src="http://www.picbasic.co.uk/forum/attachment.php?attachmentid=1872&stc=1&d=1184983103">

T.Jackson
- 21st July 2007, 05:37
Will it sort a million numbers? - Yes it will. In around an estimated 131.94 hours that is. Divide that figure by bout 10 for a really fast modern PC. Maybe even more for a quad core. Happy sorting!

Melanie
- 21st July 2007, 07:05
Let's swing sorting slightly towards PBP... not quite a million numbers though... can't recall too many PICs with that kind of RAM capability, and with other forms of storage you're then relying on their I/O speed characteristics.

However, in professional embedded applications, when you take an ADC reading, good practice states that you take more than one and eradicate any anomalies. That way, when your sensor sits at the end of a length of cable, you can eliminate lightning strikes and the odd Redneck trying to weld his pickup truck in near proximity.

Well, the way I achieve that is to take say 16 ADC readings, sort them in sequential order of value, junk the top and bottom four readings as being 'out-of-range', sum and average the middle eight... this makes ADC readings in industrial applications pretty much bomb-proof...

Now, whilst there's quite a few tricks and treats within this, here's a simple sort routine for doing just that (when you analyse it, it's pretty similar to your example Trent albeit a little more compact)... The Data to be sorted sits in an array called RawData, and when it falls out of the subroutine, RawData is in sequential order. Change DataA and RawData variables to WORDS if you need them. Those that know will notice that the additional variable DataA is only needed because PBP's SWAP command doesn't work with arrays.



CounterA var Byte
DataA var Byte
RawData var Byte [16]
.. ..

'
' Sort Array
' ----------
SortArray:
CounterA=0
SortLoop:
If RawData(CounterA+1) < RawData(CounterA) then
DataA=RawData(CounterA)
RawData(CounterA)=RawData(CounterA+1)
RawData(CounterA+1+0)=DataA
If CounterA > 0 then CounterA=CounterA-2
endif
CounterA=CounterA+1
If CounterA < 15 then goto SortLoop
Return

T.Jackson
- 21st July 2007, 07:29
RawData(CounterA+1+0)=DataA


+ 0 ? :eek:

*Like the multiple sample theory - something I never really thought about. But then again, I'm not an engineer.

Melanie
- 21st July 2007, 07:38
Yes, +0, other than Bruce, Darrel (and perhaps Mister_E), who on this forum knows why?

T.Jackson
- 21st July 2007, 08:17
I normally have the ability to at least come up with some sort of opinion with most things (often it's wrong), but on that, I can't even think of one guess, not even an obviously far-fetched one.

Melanie
- 21st July 2007, 08:36
Going back to the early days of PBP, before Microcode studio, to the days when you carved your code into slate tablets, there was an anomaly/bug with PBP sometimes handling math within array parenthesis. The workaround was to simply add a dummy argument (which goes to show how old that code is). Now I can't remember at which point the error was eradicated without compiling a bunch of test samples across more than half-a-dozen versions of PBP. The code I posted above pretty much works with all versions, though if absolute speed is your thing, you can probably lose the +0 if your PBP is relatively up-to-date.

T.Jackson
- 21st July 2007, 09:01
Oh! - well that puts my mind at ease, it's things like that keep me from getting a good nights sleep. I'll be able to switch off tonight and get some rest.

Ioannis
- 25th July 2007, 11:55
...Those that know will notice that the additional variable DataA is only needed because PBP's SWAP command doesn't work with arrays.

Well, there is a way to swap two variables without the need of a third dummy one:

a=a^b
b=a^b
a=a^b

If you test it with binary numbers be surprised that finally there is swap without dummy!

Ioannis

Darrel Taylor
- 25th July 2007, 12:55
Cool.

And I suppose if someone wanted to test the "Surprise", they might do something like this ...


;Initialize your hardware first

A VAR WORD
B VAR WORD
TempA VAR WORD
TempB VAR WORD

LCDOUT $FE,1

For A = 0 to 65535
LCDOUT $FE,2,"A=",DEC A
For B = 0 to 65535
TempA = A
TempB = B
TempA = TempA ^ TempB
TempB = TempA ^ TempB
TempA = TempA ^ TempB
IF (TempA <> B) OR (TempB <> A) THEN ; Test Failed
LCDOUT $FE,1,"Test Failed",$FE,$C0,"A=",DEC A,", B =",DEC B
STOP
ENDIF
Next B
Next A

LCDOUT $FE,1,"Test Passed!"
STOP

Then some 40 hours later (@ 20Mhz) [that's over 4 billion combinations],
you would no doubt see the message "Test Passed!" on the LCD.

Only a half hour into it, but it's still passing. Kinda obvious what the result will be.

Update: 43hrs, Test Passed! (obviously)
<br>

Ioannis
- 25th July 2007, 14:41
Nice routine Darrel! 40 hours to wait for "Test Passed!", wow!

Ioannis

Darrel Taylor
- 25th July 2007, 15:25
LOL,

I think I'll need those 40 hrs. just to wrap my head around why it works.

It does work, but the explanation eludes me.

@ Don't tell me, I've still got 38 hrs to go :)
<br>

Darrel Taylor
- 25th July 2007, 18:32
Programs still running, but I think I got the XOR thing figured out.
Not that I could explain it though.

Practicing my Flash at the same time :)

.. Flash moved down ..

Bruce
- 25th July 2007, 21:42
How this logic works is pretty cool. I saw this on the PIClist a few years back.

Here's how it works.

a VAR BYTE
b VAR BYTE
a = %11001100
b = %00110011

a=a^b ' a now = %11001100 ^ %00110011 which = %11111111

1 ^ 0 = 1. 1 ^ 1 = 0. 0 ^ 0 = 0.

b=a^b ' b now = %11111111 ^ %00110011 which = %11001100 (value of original a)

b now contains the original value of a.

a=a^b ' a now = $11111111 ^ %11001100 which = %00110011 (value of orignal b)

Now that b = the original value held in a, ^-oring a with b returns the orignal
value of b, in a.

Using any two values, it still works the same. Like this;

a = %11011100
b = %00110011

a=a^b ' a now = %11011100 ^ %00110011 which = %11101111
b=a^b ' b now = %11101111 ^ %00110011 which = %11011100 (value of original a)
a=a^b ' a now = $11101111 ^ %11011100 which = %00110011 (value of orignal b)

Pretty nifty way of swapping variables.

Ioannis
- 26th July 2007, 08:51
And is as fast as using swap technique!

I was wondering where I first read about it and after alot of searching, it was on a summer double Elektor issue.

Ioannis

Darrel Taylor
- 26th July 2007, 10:15
Ioannis,

Thanks for the interesting idea to ponder.

And thanks for the extra examples Bruce. But while it does show that it gets from A to B and visa versa, it didn't really answer the Why? that had me so baffeled. When I get baffeled I usually become obsessed at figuring out the why, especially when it seems like it should be so simple (Like 3 XOR's in a row).

My biggest problem was thinking it was combining the bits with the first A=A^B, then somehow pulling the bits back out with the next XOR. But none of that was making any sense.

After making the Flash, I realized that the XOR gate should really be called the "They're Different" gate, which is what the XOR does. If both inputs are the same the output is 0, if they're different, the output is 1.

Then it all made perfect sense.

The first A = A^B determines if both bits are Different or not, and stores it back in A.

Since you still know the original B value, and you know if the 2 are different then ...

If B = 1 and "They are Different" then A used to be = 0, which accounts for the B = A^B

The last A = A^B does the same thing. If they are different, and you know the new B is a 0, then the new A has to be a 1.

<OBJECT CLASSID= "clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" WIDTH="600" HEIGHT="300" CODEBASE="http://active.macromedia.com/flash5/cabs/swflash.cab#version=5,0,0,0"><PARAM NAME="MOVIE" VALUE="http://www.pbpgroup.com/files/XOR.swf"><PARAM NAME="PLAY" VALUE="true"><PARAM NAME="LOOP" VALUE="true"><PARAM NAME="WMODE" VALUE="opaque"><PARAM NAME="QUALITY" VALUE="high"><EMBED SRC="http://www.pbpgroup.com/files/XOR.swf" WIDTH="600" HEIGHT="300" PLAY="true" LOOP="true" WMODE="opaque" QUALITY="high" PLUGINSPAGE="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash"></EMBED></OBJECT>

I feel better now. :)
<br>

Ioannis
- 26th July 2007, 10:37
Cool Darrel!

But what is buzzing me more, is how one can think about it in the first place. He/she must be really clever one. So simple, so clever!

Ioannis

Bruce
- 26th July 2007, 13:06
I've found a few nifty tricks like this on the Microchip forum in the Tips &
Tricks section http://forum.microchip.com/tm.aspx?m=165770

Really gets one to thinking.

The PIClist is another good resource, but the signal-to-noise ratio there can
be pretty high.

Nice job on the Flash XOR gate Darrel...;o}

Darrel Taylor
- 26th July 2007, 13:39
Thank you, thank you,

So now that I've proven to myself that it works, ...
back to the topic ...

I think that changes Melanie's Sort from Post #4, to ...

CounterA var Byte
RawData var Byte [16]
.. ..

'
' Sort Array
' ----------
SortArray:
CounterA=0
SortLoop:
If RawData(CounterA+1) < RawData(CounterA) then
RawData(CounterA) = RawData(CounterA) ^ RawData(CounterA+1)
RawData(CounterA+1+0) = RawData(CounterA) ^ RawData(CounterA+1)
RawData(CounterA) = RawData(CounterA) ^ RawData(CounterA+1)
If CounterA > 0 then CounterA=CounterA-2
endif
CounterA=CounterA+1
If CounterA < 15 then goto SortLoop
Return

Now I've got to wonder if it makes any difference? :confused:

edit: The added array operations would probably even slow it down.
<br>

Ioannis
- 26th July 2007, 14:30
The one thing for sure is that code will use one variable less.

As for speed, I don't know. Operation either on swap or with the XOR thing i believe are the same...

Ioannis

T.Jackson
- 26th July 2007, 15:16
You know, if you say Super-cala-fragile-listic-expealidoius, backwards, at exactly 3:03 am, the Blair Witch will appear before you and grant you with exactly one wish. Be careful what you wish for though.

Ioannis
- 27th July 2007, 09:26
You know, if you say Super-cala-fragile-listic-expealidoius, backwards, at exactly 3:03 am, the Blair Witch will appear before you and grant you with exactly one wish. Be careful what you wish for though.

Didn't that was said by Mary Poppins? Iliked it a lot!

But how does this connect with the above? Sorry I cannot understand, as english is second language to me.

Ioannis

Melanie
- 27th July 2007, 09:39
It doesn't work (because Trent forgot to use his spellchecker)... I'm worried about the 'fragile' section in the middle of the word...

Ioannis
- 27th July 2007, 09:57
and needs an 'c' in expealidoius like: expealidocius

Ioannis

Darrel Taylor
- 27th July 2007, 10:50
The biggest problem is that it takes longer than a second to say it.

There's no way to say the whole thing at exactly 3:03 am.

But backwards (according to the movie) would be.
dociousaliexpiisticfragilcalirupus

docious-ali-expi-istic-fragil-cali-rupus
<br>

T.Jackson
- 27th July 2007, 11:30
Legend has it that if you stand in front of a mirror, any time past midnight, and say three times; "I don't believe in the Bell Witch" - the next morning you will wakeup with finger nail scratches on your cheek.

Darrel Taylor
- 27th July 2007, 11:41
Do you have any more of those pills?

And, can I have some?? :D
<br>

T.Jackson
- 27th July 2007, 12:45
That legend is for real Darrel.

Melanie
- 27th July 2007, 14:06
> next morning you will wakeup with finger nail scratches on your cheek.

... and there I was wondering why I never get dated more than once!

vaporized
- 7th November 2009, 13:47
Hello.
I apologize for reviving old thread but forum is already crowded with so many topics I don't want to aggrandize it further.

In mrs. Melanie's routine I don't understand the following:


SortArray:
...
IF CounterA>0 then CounterA=CounterA-2
...
CounterA=CounterA+1
IF CounterA<15 THEN SortArray


As I see it, after the first pass through the loop CounterA is 1, so when it hits IF CounterA>0... wouldn't that make CounterA bigger than15 and exit the loop (CounterA war byte so 1-2=255)?
Can someone please explain it to me?

Melanie
- 7th November 2009, 17:16
>Mrs Melanie!

Don't marry me off yet - I'm having way too much fun being single!

This is a SWAP SORT routine with an Array of 16 elements... (this version is in ASCENDING order, ie the smallest value will end up in RawData(0) and the largest value will end up RawData(15).

First time through the loop CounterA=0 (not 1 as you stated).

You compare RawData(1) with RawData(0) and if RawData(1) is smaller you swap them (NOT if it's bigger or if is the same).

There was an ARRAY BUG in PBP V2.42, which caused problems with Array manipulation - for example RawData(CounterA+1), the workaround (before MeLabs fixed it) was to add a dummy proceedure, so this became RawData(CounterA+1+0). This BUG has long been fixed, so you don't actually need the +0 bit nowadays.

Only if you are NOT at the start of the Array Sort (ie CounterA>0) do you then go back and look at the previous set of Array elements and compare those again (because you've just swapped the upper one of them). You actually subtract 2, because the very next step adds one, so in essence you only go back one Array step. If you are already at the beginning of the Array (ie CounterA=0), you DON'T step back, because that will cause you to step outside your array limits, so you move forward by adding 1 to CounterA.

You repeat the process until you've scanned the whole array and CounterA=15 (your upper Array limit).

So... back to your question...

Whether you SWAP or NOT, if CounterA=0 then the -2 will never happen, you can only move FORWARDS to CounterA=1 (ie CounterA=CounterA+1).

If CounterA=1, then if you DON'T Swap, you move FORWARDS (as above), but if you DO SWAP then CounterA will move BACK by ONE Count (ie CounterA=-2+1), which if CounterA was 1 to start with, it will now move back to be Zero.

vaporized
- 8th November 2009, 10:36
Don't marry me off yet - I'm having way too much fun being single!

Please accept my apology, English is not my native language so I make many mistakes.


Thank you very much for your kind and patient response. Now I see how stupid my question really was. I grasped on CounterA+1 & CounterA-2 as a bull on red flag therefore completely dropping the rest out of my sight. I'll put more effort next time instead of bothering with a silliness.
Thanks again for the explanation, as well for sharing the routine.

Kind regards

Melanie
- 8th November 2009, 13:53
*smiles* No appologies are required!

Doesn't matter about asking questions - that is what this forum is here for, everyone who reads learns something from them.

aratti
- 8th November 2009, 17:41
Well, the way I achieve that is to take say 16 ADC readings, sort them in sequential order of value, junk the top and bottom four readings as being 'out-of-range', sum and average the middle eight... this makes ADC readings in industrial applications pretty much bomb-proof...

Miss Melanie, in doing so you are potentially junking good data, but you can also potentially retain and use in your mean bad data, since you have no way to know how many bad readings you will take with your sampling.

A statistically correct approch should be to calculate the mean and the standard deviation (sd), of all your 16 readings, than retain all data within +/- 1 or 2 sd depending esclusively on your need.

A simpler approach could be to decide which threshold (in percentage of the mean) to apply to reduce the variance, than take the mean of all the 16 readings and discard all the data beyond the threshold limit.

In both cases you will not need to sort your array.

Al.

Ioannis
- 8th November 2009, 18:35
But the maths to do those calculations I feel are more code hungry than just sorting...

Ioannis

aratti
- 9th November 2009, 09:43
Ioannis, if the number that you will display has no importance then you can fix it with a constant, display will be rock stable (always the same number). On the other hand, if the number should provide you usefull information then you must treat it in such a way to preserve those information, which means you must use the correct statistical approch, regardless how code hungry the algorithm could be.

Al.

Ioannis
- 9th November 2009, 10:17
Of course I agree with you Al.

I just feel that Melanies approach is faster giving almost same result for most cases.

Sure if you need the most precise results, one in the way to follow.

Ioannis

Melanie
- 9th November 2009, 10:36
There are many ways of accomplishing the same task. Give that task to a dozen engineers, you may get a dozen different approaches, each achieving the desired result, and each achieving that result with different methodology. Really, in electronics and programming there is no SINGLE correct way of doing anything and the methodology you employ rests with your imagination which makes our business just as exciting and creative as any Artist painting a canvas.

If I am measuring ambient temperature for example, I don't expect to take sixteen readings 50uS apart and discover twelve of them to measure around +22.7 Celcius, one to measure -20, one measures -40 Celcius, one measures +400 and one measures +700 Celcius. But that is exactly the kind of result you might get is you experience a local lightning strike with spikes being induced into your electronics. Very short bursts of total rubbish.

Now using a conventional method of summation would produce an erroneous result, but the temperature may well drop to -20 or minus 40 in winter, so that could also be technically valid data, but in the case above, we know that the onset of winter doesn't happen in 100uS, so we need to trash the data at the extreemes (even if it might be good data).

Now in the code I published some years back, I put forward an idea of taking multiple samples, sorting them, discarding those results at the fringes and concentrating only on the centre median of our collection of data. This works good in the majority of industrial and environmental applications and even for motion control on an industrial assembly robot (filtering localised welding spikes). The amount of data you discard is not arbitrary, it depends on the number of samples you've taken and the TIME you've sampled them across. I know lightning tends to be short duration spikes, so out of a milliseconds worth of sampling, I know that anything out of the ordinary lasting 50 or 100uS we can happilly junk. But, if I was creating the firmware for a new Digital Oscilloscope or sampling an Audio waveform for an Amplifier, this would obviously not be the correct approach.

aratti
- 19th December 2009, 18:10
Hi Darrel, I tested the sorting snippet you have posted, using a rather interesting swapping technique.

The code worked, but now and than, it was yielding very fanny results.

From a closer code analysis, I came to the conclusion that :



If CounterA > 0 then CounterA=CounterA-2


should be corrected with:



If CounterA > 1 then CounterA=CounterA-2


After the correction, I didn't see any fanny result for the rest of my testing period.

The explanation I have given is the following:

If CounterA = 1 then CounterA - 2 = 255 and this screw up everything.

Can you confirm?

Al.

Darrel Taylor
- 19th December 2009, 19:28
Hi Darrel, I tested the sorting snippet you have posted, using a rather interesting swapping technique.
The code worked, but now and than, it was yielding very fanny results.
From a closer code analysis, I came to the conclusion that :


If CounterA > 0 then CounterA=CounterA-2

should be corrected with:


If CounterA > 1 then CounterA=CounterA-2

After the correction, I didn't see any fanny result for the rest of my testing period.
The explanation I have given is the following:

If CounterA = 1 then CounterA - 2 = 255 and this screw up everything.

Can you confirm?

Al.Well, I wouldn't think it's a problem.
Right after the IF block that statement is in, Melanie put a ...

CounterA=CounterA+1

So if CounterA = 1, subtracting 2 makes it 255, then adding 1 makes it 0 again.

Had you made any other changes?
<br>

aratti
- 19th December 2009, 19:41
Had you made any other changes?

Yes, a second one, but more for cleaning the code, since it didn't effect functionality:



RawData(CounterA+1+0) = RawData(CounterA) ^ RawData(CounterA+1)


Has been cleaned with:



RawData(CounterA+1) = RawData(CounterA) ^ RawData(CounterA+1)





Well, I wouldn't think it's a problem.
Right after the IF block that statement is in, Melanie put a ...

CounterA=CounterA+1

So if CounterA = 1, subtracting 2 makes it 255, then adding 1 makes it 0 again


But the above make sense, I do better check the whole system again.

Thank you Darrel.

Al.

boroko
- 4th July 2010, 09:05
WOW, must be a good day!
I remembered Melanie had a comment on sorting out changing inputs, but I couldn't find my bookmark for it. I went to the main forum page and there it was on the right column!
Whew! someone must be looking out for me....

My situation involves reading WORD sized data every 30ms (with quite a few spurious readings) and controlling a PWM output with somewhere near a 2-3 second response to drive some mechanicals that require slow reaction. I have been trying to mold Darrel's DT_Average16 routine to make it work, but with little success in this application.

Can someone elaborate a bit on feeding fresh data into this sort and trimming the top and bottom readings? I don't understand how to run this with a continuous data stream without blowing up the sort.

Thanks
Bo

boroko
- 6th July 2010, 11:25
Here is what I have come up with so far.....
it is getting closer.
Derived from Malanie's suggestion about parsing data and DT's averaging scheme * PIC18F2525 @ 8 MHz

ByteData var byte
CounterA var word ' sort counter
CounterB var byte
CounterC var byte
DataA var word ' storage for sorted values
DatSort var byte ' pointer to middle 8 values
DatAvg var word ' averaged value of sorted data
RawData var word[16] ' storage for raw data
Clear
AvgCount CON 8 ' = Number of samples to average
FAspread CON 1000 ' = Fast Average threshold +/-
INCLUDE "AllDigital.pbp"
DEFINE OSC 8
OSCCON = %01110000
DEFINE HSER_RCSTA 90h ' Enable serial port & continuous receive
DEFINE HSER_TXSTA 24h ' Enable transmit, BRGH = 1
DEFINE HSER_CLROERR 1 ' Clear overflow automatically
DEFINE HSER_SPBRG 34 ' 57600 Baud @ 8MHz, -0.79%
SPBRGH = 0
BAUDCON.3 = 1 ' Enable 16 bit baudrate generator

hserout["SortAverage",10,13]
pause 500
goto Start

'Sort Array SUB ** collects 16 readings, sorts, and averages middle 8 ******
SortArray:
CounterA=0
SortLoop: ' sorts 16 readings of RawData in order
If RawData(CounterA+1) < RawData(CounterA) then
DataA=RawData(CounterA)
RawData(CounterA)=RawData(CounterA+1)
RawData(CounterA+1+0)=DataA
If CounterA > 0 then CounterA=CounterA-2
endif
CounterA=CounterA+1
If CounterA < 15 then goto SortLoop
' for CounterC = 0 to 15 ' These three lines O/P the sort results
' hserout["Ordered[",dec CounterC,"]= ", dec RawData[CounterC],10,13]
' next CounterC
'**** Trim and Average ************************************************** *
for DatSort = 4 to 11 ' pick out middle 8 readings
IF ABS (DatAvg - RawData[DatSort]) > FAspread Then CatchUp
IF ABS (DatAvg - RawData[DatSort]) < AvgCount Then RealClose
DatAvg = DatAvg - (DatAvg/AvgCount)
DatAvg = DatAvg + (RawData[DatSort]/AvgCount)
GoTo AVGok
CatchUp:
DatAvg = DatAvg + (RawData[DatSort]/8) ' catch-up by 1/8 value of reading
GoTo AVGok
RealClose:
DatAvg = DatAvg - (RawData[DatSort]/(AvgCount/4))
DatAvg = DatAvg + (DatAvg/(AvgCount/4))
AVGok:
' hserout["Middle[",dec datsort,"] = ",dec RawData[DatSort],10,13] 'SHOW mid 8
next DatSort
Return
'** END SUB************************
Start:
FOR CounterB=0 to 15
HSERIN [RawData[CounterB]]
NEXT CounterB
FOR CounterB=0 to 15
HSEROUT["RawData[",DEC counterB,"] = ",DEC rawdata[CounterB],10,13]
NEXT CounterB
CALL SortArray
HSEROUT ["Sorted Averaged result ",dec DatAvg,10,13]
GOTO start

aratti
- 6th July 2010, 15:06
for DatSort = 4 to 11 ' pick out middle 8 readings
DatAvg = DatAvg + RawData[DatSort]
NEXT DatSort

DatAvg = DatAvg >>3
Return



You can short and semplify your averaging routine with the above example. DatAvg sums up the 8 central values then you devide by 8 for the average.

Al.

boroko
- 8th July 2010, 02:40
Hi Al. Thanks for looking at it.

I like the way you simplified, but my concern was that since I will be working with WORD data, the result of the addition could get big enough that I would have to use LONGs if I didn't use DT's running average scheme (http://www.pbpgroup.com/modules/wfsection/article.php?articleid=7).

So far, I have only tested it with byte data, and it does seem to settle slowly on something close to average. I need to try WORD data and see how that works.

Bo

aratti
- 9th July 2010, 00:09
... but my concern was that since I will be working with WORD data, the result of the addition could get big enough that I would have to use LONGs...


Using a 10 bits adc, the maximun number you can obtain is 1023. Now summing up 8 readings of 1023 each, you will end up with your word variable at 8184 (overflow will occur at 65K)

Since you are using adc , you have to remove
INCLUDE "AllDigital.pbp"
from your code.

Al.

boroko
- 9th July 2010, 07:42
Hi Al,
Thanks for engaging in this thread. Sometimes when one posts and gets no response, you begin to worry if your question is so off the wall that no one is interested.

The values that I'm working with are actually timer values that are WORD sized. The ultimate result is measuring ultrasonic pulse return to calculate distance. In the real program, I'm using a comparator interrupt to grab of the values. That one uses the analog, but here I'm just trying to sort out the averaging scheme.
The response needs to be smoothed considerably due to the high instance of random response of the ultrasonics. The values go on to determine the PWM output that drive a servo valve that controls some heavy hydraulics that can't tolerate quick movement. The response time needs to be in the 2-3 second range with smooth changes to work well. Since the values are 0-65535, and readings every 30mS, I'm trying to use Melanie's suggestions to dump the extremes, and DT's averaging to get away from LONGs and 32 bit math.

Current testing is with a second PIC generating the return pulse timing to separate the circuit from the program so that I can find the weakness. I'm trying to send a serial in to simulate the echo numbers. The next step is to convert the RX bytes into WORDS and see if the program works correctly.

Back to Burn and Turn
Bo

aratti
- 18th July 2010, 20:36
Hi Bo,
clear now. One workaround for not using long and still average them in the conventional way is the following:



RawData[0] = 0
for DatSort = 4 to 11 ' pick out middle 8 readings
RawData[0] = RawData[0] + (RawData[DatSort] - RawData[3]) ' extract the total difference
NEXT DatSort
RawData[0] = RawData[0] >>3 ' average the total difference
DatAvg = RawData[0] + RawData[3] ' add the average difference to the subtractor
Return


You addup in RawData[0] all the differences , then you average them and finally you add them to the RawData[3], the subtractor.

Al.

Dave
- 19th July 2010, 13:29
Al, I'm confused..... Where does RawData[3] come from and whats in it?

Dave Purola,
N8NTA

aratti
- 19th July 2010, 18:44
Al, I'm confused..... Where does RawData[3] come from and whats in it?

Dave, RawData array will contain the 16 readings you have taken from your system (ADC ; counter; etc.) . Once you apply Miss Melanie's sorting algorithm you will end up with your 16 values ordered in ascending order RawData[0] will contain the smallest reading while RawData[15] will contain the largest one.

The suggested technique is to discard the first 4 readings and the last 4 readings and average the central 8 reading, in such a way you will not enter into your average calculation anomalous reading (spikes for instance).

The Boroko issue was that since he is using the 16 bits counter, he was concerned in averaging the 8 raw data in the coventional way, due to the fact that a word will overflow over 65k and he didn't want to use long type variable.

This method, I have proposed, simply extract the differences from the 8 central values, which can be handled with a single word variable. Once the differences are extracted and summed up into RawData[0] (which is available because its content has been discarded) then you calculate the average shifting the bits with this instruction RawData[0] = RawData[0]>>3

Now if you add this average to the subtractor used (in our case RawData[3]) all you get is the data average.

Naturally the code snippet should be called after a call to the sorting routine.

Hoping to have clear the matter.

Al.

boroko
- 22nd July 2010, 17:39
Hi folks,

Well, another learning moment! For the past week or so, I have been working on the previously mentioned sorting algorithm. I have been peeking in on the forum, but saw Al's name as the last one that replied so I didn't open it. Of course, I missed that there were actually 2 replies and that masked that there had been activity.

Thanks for the suggestion. I will study it and see how long it takes me to understand it.

In the mean time, this is where I have been churning. Puzzles me greatly, because it doesn't give anything near what I think it should.
'* : 18F1330 *
'************************************************* ***************
DEFINE OSC 32
OSCCON = %11111100 ' INTOSC primary, 8MHz
OSCTUNE = %11111111 ' ENABLE 4x PLL = 32mHz
DEFINE HSER_RCSTA 90h ' Enable serial port & continuous receive
DEFINE HSER_TXSTA 24h ' Enable transmit, BRGH = 1
DEFINE HSER_CLROERR 1 ' Clear overflow automatically
DEFINE HSER_SPBRG 138 ' 57600 Baud @ 32MHz, -0.08%
SPBRGH = 0
BAUDCON.3 = 1 ' Enable 16 bit baudrate generator

DataA var WORD
RawData var WORD [16] 'full program uses 16 and strips top
DatAvg var byte ' and bottom readings
DatSort var byte '
DatCnt var byte ' count the 16 data entries
AvgCount con 8 ' number of readings to average (1/x)
DatAvg = 2500 ' seed number to start averaging


RawData[4]= 20000 ' this data represents 8 different
RawData[5]= 21000 ' readings that come from a TMR0
RawData[6]= 22000 ' capture that is working. Fixed
RawData[7]= 23000 ' values here for testing
RawData[8]= 24000
RawData[9]= 25000
RawData[10]= 26000
RawData[11]= 27000
pause 2000
'-- Average middle 8 readings ---------------------------------------
Average:
for DatSort = 0 to 7 ' get 8 readings
Hserout["DA=",#DatAvg,", RD",#DatSort,"=",#RawData[DatSort]]
DatAvg = DatAvg - (DatAvg/AvgCount) 'subtract 1/x from Avg
hserout[", 1/x=",#(DatAvg/AvgCount)," DA- = ",#DatAvg]
DatAvg = DatAvg + (RawData[DatSort]/AvgCount) 'add 1/x of new reading
Hserout[", DA+ = ",#DatAvg,13,10]
next DatSort
hserout[13,10]
' hserout[", DA ",#DatAvg,13,10]
goto Average

Here is a RealTerm screen of the output
DA=219, RD4=20000, 1/x=24 DA- = 192, DA+ = 132
DA=132, RD5=21000, 1/x=14 DA- = 116, DA+ = 181
DA=181, RD6=22000, 1/x=19 DA- = 159, DA+ = 93
DA=93, RD7=23000, 1/x=10 DA- = 82, DA+ = 141
DA=141, RD8=24000, 1/x=15 DA- = 124, DA+ = 52
DA=52, RD9=25000, 1/x=5 DA- = 46, DA+ = 99
DA=99, RD10=26000, 1/x=10 DA- = 87, DA+ = 9
DA=9, RD11=27000, 1/x=1 DA- = 8, DA+ = 55

DA=55, RD4=20000, 1/x=6 DA- = 49, DA+ = 245
DA=245, RD5=21000, 1/x=26 DA- = 215, DA+ = 24
DA=24, RD6=22000, 1/x=2 DA- = 21, DA+ = 211
DA=211, RD7=23000, 1/x=23 DA- = 185, DA+ = 244
DA=244, RD8=24000, 1/x=26 DA- = 214, DA+ = 142
DA=142, RD9=25000, 1/x=15 DA- = 125, DA+ = 178
DA=178, RD10=26000, 1/x=19 DA- = 156, DA+ = 78
DA=78, RD11=27000, 1/x=8 DA- = 69, DA+ = 116

I can't yet find a pattern or a reason. Maybe its time for a bit of sleep. I will work on it more later.
Thanks
Bo

boroko
- 23rd July 2010, 11:15
Hi Al
I had the same question as Dave until I mapped it out. Until I put it into Excel, I couldn't understand how that was going to work. Very cool indeed.
The value in RawData[3] didn't matter, since the values were already sorted, it was lower than RD[4]. All it needed to do was act as a reference for the subtraction and then it was added back in canceling itself. I have no idea how you came up with that, but I'm glad folks like you are willing to teach the rest of us.

The .xls is zipped if anyone would like to see it.

Thanks
Bo

boroko
- 23rd July 2010, 12:06
Error found:

The output from the code on post #52 didn't make sense because somewhere I had aliased a word variable to a byte. For some reason, they don't work the same....

Things seem to be going much better now.

Bo

kenif
- 1st September 2021, 21:08
Thank you, thank you,

So now that I've proven to myself that it works, ...
back to the topic ...

I think that changes Melanie's Sort from Post #4, to ...

CounterA var Byte
RawData var Byte [16]
.. ..

'
' Sort Array
' ----------
SortArray:
CounterA=0
SortLoop:
If RawData(CounterA+1) < RawData(CounterA) then
RawData(CounterA) = RawData(CounterA) ^ RawData(CounterA+1)
RawData(CounterA+1+0) = RawData(CounterA) ^ RawData(CounterA+1)
RawData(CounterA) = RawData(CounterA) ^ RawData(CounterA+1)
If CounterA > 0 then CounterA=CounterA-2
endif
CounterA=CounterA+1
If CounterA < 15 then goto SortLoop
Return

Now I've got to wonder if it makes any difference? :confused:

edit: The added array operations would probably even slow it down.
<br>

This sort just saved my butt, thank you.
As the PICs get faster, speed is less of a consideration.