[alg] continu het gemiddelde berekenen

[MadMan81]

Het is een redelijk wiskundig probleempje, maar denk dat het hier het meest op z'n plek is.

Het gaat om het volgende: Ik heb een lijst met met getallen en wil daar graag het gemiddelde van weten. Alleen er is 1 probleem: de som van de getallen is te groot voor de grootste integer. Ik kan dus niet simpel alles optellen en delen door het aantal getallen.

Nu had ik zelf bedacht dat het misschien mogelijk was om eerst getal A en B bij elkaar op te tellen en te delen door 2, vervolgens daar getal C bij op te tellen en dat weer door 2 delen etc.. Echter dit kan niet.

Bewijs:

code:

 A + B
------- + C      A + B + C
   2         =  ------------
------------         3
     2

3 (1/2A + 1/2B) + 3C = 2A + 2B + 2C

3/2A + 3/2B + 3C = 2A +2B +2C

C = -1/2A -1/2B

(Als het wel het zelfde was geweest was er aan beide kanten 0 uitgekomen.)

Nu is mijn vraag: zijn hier andere methoden voor? Zonder dat je alle oude getallen (A en B ) moet onthouden!

[Anoniem: 32938]

aan de linker kant bereken je niet het gemiddelde. Maar A+B wordt tweemal gedeeld. Rechts is wel goed. Waarom neem je niet gewoon een groter formaat om mee te delen?

[André]

Wat noem jij de grootste integer? Er zijn toch wel mogelijkheden om gigantisch getal op te slaan?

Hoe groot is een integer ?

[ Voor 24% gewijzigd door André op 03-06-2004 09:15 ]

[Anoniem: 32938]

idd. zie frontpage, waar priemgetallen worden berekend. Een double kan een getal met iets van 308 decimalen opslaan. ik neem niet aan dat je zo groot gaat. Oftwel gewoon berekenen door som(x)/n.

[12_0_13]

Stel je getallen zijn a, b, c, d etc. je houd bij hoeveel getallen je al hebt (n), en het gemiddelde (m)

code:

m = a    (n=1)
m = (n / n+1) * m + 1/(n+1) * b)    (n=2)
m = (n / n+1) * m + 1/(n+1) * c)     (n=3)

Stel a,b,c = 4,5,6

code:

m = 4
m = (1/2) * (4 + 5) = 4,5 = correct
m = (2/3) * (4,5) + (1/3)*6 =  3+2 = 5 = correct

zo denk ik? (let wel op afrondingsfouten.. als je werkt met doubles kom je bij de 10 decimalen (dacht ik) in de problemen)

[ Voor 18% gewijzigd door 12_0_13 op 03-06-2004 09:14 ]

[gorgi_19]

Visual Basic .NET:

Dim averageValue as Double = 0
Dim numberOfItems as Double = 0
Dim maxAverage as Double = 0
Dim ListOfNumbers as ArrayList = Me.GetListWithValues()
For I as Integer = 0 to ListOfNumbers.Count -1
    averageValue = averageValue * (I/(I+1)) + (ListOfNumbers(I) * 1/(I+1))
    maxAverage = Max(maxAverage,averageValue )
Next

iets als dit? 't is in VB.Net, maar wel uit te komen, denk ik.

[ Voor 7% gewijzigd door gorgi_19 op 03-06-2004 09:13 ]

[justmental]

Alleen het aantal metingen beinvloedt het 'gewicht' van de nieuwe meting in het gemiddelde.

Dus iets als:
nieuwe gem = oude gem + ( nieuwe waarde - oude gem ) / aantal waarden

[12_0_13]

justmental schreef op 03 juni 2004 @ 09:12:
Alleen het aantal metingen beinvloedt het 'gewicht' van de nieuwe meting in het gemiddelde.

Ja dat kan ook (en is simpeler)

[Anoniem: 32938]

12_0_13 schreef op 03 juni 2004 @ 09:12:
Stel je getallen zijn a, b, c, d etc. je houd bij hoeveel getallen je al hebt (n), en het gemiddelde (m)

code:

m = a    (n=1)
m = (n / n+1) * m + 1/(n+1) * b)    (n=2)
m = (n / n+1) * m + 1/(n+1) * c)     (n=3)

Stel a,b,c = 4,5,6

code:

m = 4
m = (1/2) * (4 + 5) = 4,5 = correct
m = (2/3) * (4,5) + (1/3)*6 =  3+2 = 5 = correct

zo denk ik? (let wel op afrondingsfouten.. als je werkt met doubles kom je bij de 10 decimalen (dacht ik) in de problemen)

toon volledige bericht

ik vind je manier een beetje omslachtig, het klopt wel, maar kost relatief redelijk wat processor tijd. ik snap niet wat er mis is met som(x)/n, oftewel de definitie van het gemiddelde.

even uit de matlab library:

code:

function y = mean(x,dim)
%MEAN   Average or mean value.
%   For vectors, MEAN(X) is the mean value of the elements in X. For
%   matrices, MEAN(X) is a row vector containing the mean value of
%   each column.  For N-D arrays, MEAN(X) is the mean value of the
%   elements along the first non-singleton dimension of X.
%
%   MEAN(X,DIM) takes the mean along the dimension DIM of X. 
%
%   Example: If X = [0 1 2
%                    3 4 5]
%
%   then mean(X,1) is [1.5 2.5 3.5] and mean(X,2) is [1
%                                                     4]
%
%   See also MEDIAN, STD, MIN, MAX, COV.

%   Copyright 1984-2002 The MathWorks, Inc. 
%   $Revision: 5.17 $  $Date: 2002/06/05 17:06:39 $

if nargin==1, 
  % Determine which dimension SUM will use
  dim = min(find(size(x)~=1));
  if isempty(dim), dim = 1; end

  y = sum(x)/size(x,dim);
else
  y = sum(x,dim)/size(x,dim);
end

[gorgi_19]

ik vind je manier een beetje omslachtig, het klopt wel, maar kost relatief redelijk wat processor tijd. ik snap niet wat er mis is met som(x)/n, oftewel de definitie van het gemiddelde.

MadMan81 schreef op 03 juni 2004 @ 08:48:
Het gaat om het volgende: Ik heb een lijst met met getallen en wil daar graag het gemiddelde van weten. Alleen er is 1 probleem: de som van de getallen is te groot voor de grootste integer. Ik kan dus niet simpel alles optellen en delen door het aantal getallen.

[Anoniem: 32938]

ik zie niet waarom die niet alles zou kunnen optellen. zijn het allemaal getallen die boven 2^150 liggen? (hij zegt integer)

+

ik reken in matlab ook met redelijk grote getallen. En matlab geeft ook geen kick af en toe wat geheugen problemen

[ Voor 46% gewijzigd door Anoniem: 32938 op 03-06-2004 09:33 ]

[MadMan81]

Anoniem: 32938 schreef op 03 juni 2004 @ 09:06:
aan de linker kant bereken je niet het gemiddelde. Maar A+B wordt tweemal gedeeld. Rechts is wel goed. Waarom neem je niet gewoon een groter formaat om mee te delen?

Dat links niet klopt kwam ik ook achter: zie uitwerking

Wat betreft de format: het grootste integer die de omgeving kent is de 16 bit unsigned integer. Het gaat hier ook niet om een pc, maar om een PLC.

@12_0_13: volgens mij klopt die idd, en kun je hem ook voor de eerste gebruiken:

nl met m=0 en n=0 wordt het:

m' = (0 / (0+1))*0 + 1/(0+1)*4 = 4

[RobIII]

Anoniem: 32938 schreef op 03 juni 2004 @ 09:31:
ik zie niet waarom die niet alles zou kunnen optellen. zijn het allemaal getallen die boven 2^150 liggen? (hij zegt integer)

+

ik reken in matlab ook met redelijk grote getallen. En matlab geeft ook geen kick af en toe wat geheugen problemen

Sinds wanneer is een integer 2^150? Een integer is toch echt 2^16 volgens mij (en in sommige gevallen 2^32 tegenwoordig <insert opa icon> )

+

Matlab kan dan misschien wel overweg met die getallen, maar wie zegt dat hij niet in QB zit ofzo?

edit:

Zie je wel MadMan81 was me nét voor Zijn omgeving kan niet met grotere getallen overweg

[ Voor 10% gewijzigd door RobIII op 03-06-2004 09:55 ]

[Reptile209]

Anoniem: 32938 schreef op 03 juni 2004 @ 09:10:
idd. zie frontpage, waar priemgetallen worden berekend. Een double kan een getal met iets van 308 decimalen opslaan. ik neem niet aan dat je zo groot gaat. Oftwel gewoon berekenen door som(x)/n.

Errr... een double kan waarden tot 10³⁰⁸ opslaan, maar bewaaart daarvan maar hooguit 15 signficante decimalen. De 16e - 308e decimaal worden netjes weggemikt en blijven als exponent over. Probeer maar eens om 10¹⁰⁰ - 1 uit te rekenen, krijg je gewoon 10¹⁰⁰ terug.

[bigbeng]

Reptile209 schreef op 03 juni 2004 @ 09:59:
[...]

Errr... een double kan waarden tot 10³⁰⁸ opslaan, maar bewaaart daarvan maar hooguit 15 signficante decimalen. De 16e - 308e decimaal worden netjes weggemikt en blijven als exponent over. Probeer maar eens om 10¹⁰⁰ - 1 uit te rekenen, krijg je gewoon 10¹⁰⁰ terug.

En even ter verduidelijking waarom dit relevant is:
De precisie van een double is afhankelijk van de orde van grootte van de getallen. Het werkt met een sliding window principe. Dit heb ik natuurlijk niet zelf bedacht, maar hier vandaan: http://research.microsoft...dex/coding/ieeefloat.html
(tjeemig research, microsoft en een standaard in 1 url)
Als we uitgaan van een integer van 32 bits, dan past deze volledig in het sliding window (53 bits precisie). Dit betekent dus even snel uitgerekend dat je 53 - 32 bits = 21 bits overhoudt die je ook nog in het sliding window kwijt zou kunnen. Dus zolang het aantal integers wat je optelt onder de 2^21 blijft (kleine 2 miljoen), dan zou je zonder precisie verlies kunnen optellen en dan dus delen door het totaal. Je kunt nog wat scherper op de snede gaan staan door ervan uit te gaan dat je maar enkele getallen zult hebben met max-int waarde.

Moraal van het verhaal: converteer je getallen naar double, tel ze op en delen maar.

Ik hoop dat ik geen cruciale denkfouten heb gemaakt, maar goed ik hoor dat dan wel van de andere tweakers.

[Anoniem: 53025]

Zoals topicstarter al zei gaat het om een PLC en geen PC, deze ondersteunen lang niet altijd double integers.

Denk dat hij moet overstappen op een S7

[Maasluip]

Ik zou zeggen, divide en conquer.

Ik zie dat het voor een PLC is, heb je daar ook alleen maar integers voorhanden?

De simpelste manier om geen grote getallen te krijgen is als volgt:

Stel, je hebt getallen a..z, 26 stuks. Het gemiddelde is dan

(a+b+...+z)/26

Omdat je zegt dat je (a+b+...+z) groter dan een integer wordt schrijf je de optelling uit:

a/26 + b/26 ... + z/26

Hiermee kom je natuurlijk in de knel als je alleen integers hebt en a/26 kleiner dan 1 is. Wat je dan zou kunnen doen is

(a+b+...+m)/26 + (n+o+...+z)/26

Moet je dus even bijhouden wanneer (a+b+..) nog net in je integer past en dan delen.

[Macros]

Wat Maasluip zegt wilde ik ook voorstellen.

[MadMan81]

Als ik idd van te voren wist hoeveel getallen ik zou krijgen zou dat ook een oplossing kunnen zijn, maar helaas dat weet ik niet..

Maar volgens mij gaat de oplossing van Justmental wel werken..

[Maasluip]

MadMan81 schreef op 03 juni 2004 @ 11:55:
Als ik idd van te voren wist hoeveel getallen ik zou krijgen zou dat ook een oplossing kunnen zijn, maar helaas dat weet ik niet..

Maar volgens mij gaat de oplossing van Justmental wel werken..

Je hoeft het ook niet van te voren weten, achteraf is voldoende. Moet je alleen even een array van integers maken en daar dus optellen totdat je aan je MAX_INT komt. Als je alle getallen hebt weet je ook hoeveel het er zijn en dan deel je alle waardes in je array door het aantal waardes en tel je ze bij elkaar op.

Als het er om gaat dat je constant nieuwe waardes krijgt (is dat het 'continu' in het title?) dan moet je gewoon de getallen bijhouden. Dat moet je sowieso doen als je steeds nieuwe getallen krijgt en steeds opnieuw het gemiddelde wil berekenen.

12_0_13 schreef op 03 juni 2004 @ 09:12:
Stel je getallen zijn a, b, c, d etc. je houd bij hoeveel getallen je al hebt (n), en het gemiddelde (m)

code:

m = a    (n=1)
m = (n / n+1) * m + 1/(n+1) * b)    (n=2)
m = (n / n+1) * m + 1/(n+1) * c)     (n=3)

Je formule klopt niet met je berekening. De berekening klopt. In de formule moet de tweede regel n=1 zijn en de derde regel n=2.

[ Voor 22% gewijzigd door Maasluip op 03-06-2004 12:09 ]

[bigbeng]

Je hoeft het ook niet van tevoren te weten. Ik ga voor het gemaak ervan uit dat je een while-lus gebruikt om door je getallen te lopen.

Je kunt dan dus binnen de while lus een tijdelijke som bijhouden, het aantal elementen in die tijdelijke som en het laatstberekende gemiddelde. Zodra je som de maxwaarde gaat overschrijden dan kun je dus justmentals oplossing gebruiken.

Op deze manier maximaliseer je de precisie van je berekening

[MadMan81]

Het probleem alleen is dat PLC's niet zoveel geheugen hebben (in dit geval 1Mb). Dus eerst alle waardes opslaan en daarna het gemiddelde berekenen is geen optie..

Kijk, ik krijg zeg maar iedere sec een nieuw getal, maar wil het gemiddelde over 15 min weten.. Dan kan je idd 900 waardes opslaan en daarna gaan rekenen, maar daar is dus geen ruimte voor. Bovendien zou die eindberekening te veel tijd kosten wat tekoste gaan van de responsetijd van de PLC, iets wat je niet wilt met PLC's

[Maasluip]

MadMan81 schreef op 03 juni 2004 @ 12:07:
Het probleem alleen is dat PLC's niet zoveel geheugen hebben (in dit geval 1Mb). Dus eerst alle waardes opslaan en daarna het gemiddelde berekenen is geen optie..

Dan de formules van 12_0_13 gebruiken, met mijn opmerking erbij dat je wel de goede n gebruikt.
Helpt natuurlijk weer niet als je alleen integers hebt...

[Soultaker]

Als je een moving average (geen idee hoe dat in het Nederlands heet) wil hebben, moet je wel alle waarden afzonderlijk bewaren. Als je 900 waardes moet optellen zou ik er gewoon twee integers voor gebruiken; zo ingewikkeld is dat niet (zelfs voor een PLC).

12_0_13 schreef op 03 juni 2004 @ 09:12:
Stel je getallen zijn a, b, c, d etc. je houd bij hoeveel getallen je al hebt (n), en het gemiddelde (m)

code:

m = a    (n=1)
m = (n / n+1) * m + 1/(n+1) * b)    (n=2)
m = (n / n+1) * m + 1/(n+1) * c)     (n=3)

Dit voorstel werkt alleen met floating point getallen (geen idee of die op de PLC van MadMan81 zitten; misschien niet).

justmental schreef op 03 juni 2004 @ 09:12:
Alleen het aantal metingen beinvloedt het 'gewicht' van de nieuwe meting in het gemiddelde.

Dus iets als:
nieuwe gem = oude gem + ( nieuwe waarde - oude gem ) / aantal waarden

Ook een aardige suggestie, maar als je dit met integer arithmetic doet, dan wordt het misschien wel erg onnauwkeurig, omdat bij die deling afgerond gaat worden.

[Janoz]

Als je nu eens gebruik maakt van fixed point berekeningen icm de oplossing van justmental?

Je zult altijd op een punt uitkomen waarbij de significantie van 1 waarde verwaarloost wordt tov het gemiddelde. Dit zal dan niet meer veranderen. Zelfs al zou je werken met doubles. Mocht het van belang zijn, dan zou je kunnen overwegen om niet het gemiddelde van altijd te nemen maar van de laatste x waardes oid. Op die manier blijft een nieuw toegevoegde waarde altijd redelijk significant.

[Maasluip]

Oh, en je zegt dat je niet alle getallen kan bijhouden. Dat hoeft ook niet. Je moet een aantal integers bijhouden. Alleen als de getallen vaak meer dan 0,5 * MAX_INT zijn dan wordt het een groot array. Als je gemiddelde echter rond de 72 ligt (16 bits MAX_INT / 900) dan heb je maar een int voor je som en een int voor je teller nodig.
Nee, dat is quatsch. Dan krijg je geen voortschrijdend gemiddelde.

@Soultaker: voortschrijdend gemiddelde

[ Voor 16% gewijzigd door Maasluip op 03-06-2004 12:22 ]

[MadMan81]

bigbeng schreef op 03 juni 2004 @ 12:01:
Je hoeft het ook niet van tevoren te weten. Ik ga voor het gemaak ervan uit dat je een while-lus gebruikt om door je getallen te lopen.

Je kunt dan dus binnen de while lus een tijdelijke som bijhouden, het aantal elementen in die tijdelijke som en het laatstberekende gemiddelde. Zodra je som de maxwaarde gaat overschrijden dan kun je dus justmentals oplossing gebruiken.

Op deze manier maximaliseer je de precisie van je berekening

PLC programma's werken wat anders dan gewone programma's (hoewel dit deels weer te omzijlen is..). Een normaal programma heeft een begin en een eind en daar tussen zit een hoop code die je uitvoert. Bij een PLC wordt de code iedere "scan" weer opnieuw uitgevoerd

Bijv: (pseudo code)

code:

if ingang_1 and ingang_2 and !ingang_3 then 
  uitgang_1 = 1; 
  uitgang_2 = 0;
fi

if ingang_1 and !ingang_2 and ingang_3 then 
  uitgang_1 = 0;
  uitgang_2 = 1;
fi

Als nu alleen ingang_1 hoog is verandert er niets aan de uitgangen: dus als ze hoog waren blijven ze hoog, als ze laag waren blijven ze laag..

Dus:
Normaal gesproken heb je een stel invoer gegevens, daar doe je wat mee (iedere "scan" weer opnieuw) en aan de hand van de uitkomst daarvan worden uitgangen ingesteld. Als je wat wilt gebruiken bij de volgende "scan" moet je dat opslaan in registers. En nu is het aantal registers redelijk beperkt..

[MadMan81]

Soultaker schreef op 03 juni 2004 @ 12:14:
Als je een moving average (geen idee hoe dat in het Nederlands heet) wil hebben, moet je wel alle waarden afzonderlijk bewaren. Als je 900 waardes moet optellen zou ik er gewoon twee integers voor gebruiken; zo ingewikkeld is dat niet (zelfs voor een PLC).


[...]

Dit voorstel werkt alleen met floating point getallen (geen idee of die op de PLC van MadMan81 zitten; misschien niet).

[...]

Ook een aardige suggestie, maar als je dit met integer arithmetic doet, dan wordt het misschien wel erg onnauwkeurig, omdat bij die deling afgerond gaat worden.

Hij kent idd allen integers, maar die getallen achter de komma zijn niet zo belangrijk. Ook de eventuele afwijken die daardoor ontstaat niet..

[bigbeng]

MadMan81 schreef op 03 juni 2004 @ 12:07:
Het probleem alleen is dat PLC's niet zoveel geheugen hebben (in dit geval 1Mb). Dus eerst alle waardes opslaan en daarna het gemiddelde berekenen is geen optie..

Kijk, ik krijg zeg maar iedere sec een nieuw getal, maar wil het gemiddelde over 15 min weten.. Dan kan je idd 900 waardes opslaan en daarna gaan rekenen, maar daar is dus geen ruimte voor. Bovendien zou die eindberekening te veel tijd kosten wat tekoste gaan van de responsetijd van de PLC, iets wat je niet wilt met PLC's

Met een kleine aanpassing is mijn aangedragen oplossing om te vormen naar een systeem waarbij je dus 4 variabelen bijhoudt:
- totale waarde tot nog toe (waarover nog geen gemiddelde berekend is)
- aantal tot nu toe (idem)
- laatst berekende gemiddelde...
- totale aantal elementen
Dit zou in totaal dus niet meer dan 4 integers in beslag nemen en dat is, jawel, 64 bits op jouw PLC. Dat moet toch kunnen zou je zeggen.

[Soultaker]

Maasluip schreef op 03 juni 2004 @ 12:19:
@Soultaker: voortschrijdend gemiddelde

Dank u!

MadMan81 schreef op 03 juni 2004 @ 12:21:
Normaal gesproken heb je een stel invoer gegevens, daar doe je wat mee (iedere "scan" weer opnieuw) en aan de hand van de uitkomst daarvan worden uitgangen ingesteld. Als je wat wilt gebruiken bij de volgende "scan" moet je dat opslaan in registers. En nu is het aantal registers redelijk beperkt..

Je had toch 1MB geheugen? Daar moeten toch wel 900 meetwaardes a 4 bytes per stuk in passen?

[MadMan81]

Maar waarom niet met de oplossing van Justmental? Dan heb je maar 2 integers nodig..

[bigbeng]

MadMan81 schreef op 03 juni 2004 @ 12:27:
Maar waarom niet met de oplossing van Justmental? Dan heb je maar 2 integers nodig..

Omdat je zo een iets nauwkeuriger gemiddelde krijgt. Maar goed, je zei eerder al dat het niet zo precies hoeft.

[Soultaker]

Twee redenen: precisie, en je kunt er geen voortschrijdend gemiddelde mee maken. Of was dat ook niet de bedoeling? Dat is wel relevant, want volgens mij is het berekenen van een voortschrijdend gemiddelde zonder alle tussenliggende waarden te bewaren onmogelijk.

[MadMan81]

Soultaker schreef op 03 juni 2004 @ 12:27:
[...]

Dank u!


[...]

Je had toch 1MB geheugen? Daar moeten toch wel 900 meetwaardes a 4 bytes per stuk in passen?

Ja dat zou idd prima passen, alleen dat geheugen wordt grotendeels al gebruikt voor andere dingen.. dus 5 a 10 integers is echt wel het max..

[Macros]

Code is pseudocode.

code:

int nrNumbers = 0;
vector store;
int sum = 0;
while(hasNext()){
  int num = next();
  if(MAX_INT - num > sum){ //we gaan over MAX_INT heen, opslaan in de store
     store.add(sum);
     sum = 0;
  } else {
     sum += num;
  }
  nrNumbers++;
}
int avg = 0; 
for(int i = store.size() -1; i >=0 ;i--){
  avg += store[i]/nrNumbers;
}

Je zou ook in een aparte array bij kunnen houden hoeveel nummers je in elk vakje in je store hebt opgeslagen. Dan moet je iets nauwkeuriger het gemiddelde achteraf kunnen berekenen.

[Janoz]

Voor het voortschreidend gemiddelde hoef je natuurlijk niet alle waardes bij te houden. Als je je voorwaarden ietsje veruimt naar het gemiddelde van de afgelopen 2^n tot 2^n+1 waardes kun je ze opslaan in n integers (mits het optellen van 2^n waardes niet boven max_int uitkomt)

[Macros]

Je kan natuurlijk ook het oude gemiddelde aanpassen met een nieuw getal. De simpelste manier is dan om het gemiddelde te nemen tussen het vorige gemiddelde en het nieuwe getal. Dan hebben alle getallen invloed op het huidige gemiddelde, alleen hoe ouder het getal hoe minder de invloed. Het nieuwste getal heeft 1/2de invloed, die daarvoor heeft 1/4de en die daarop 1/8ste etc. Dat neemt veel minder geheugen in dan dat sliding window gemiddelde en is veel sneller te berekenen. Je kan spelen met de invloed van het nieuwste getal door het oude gemiddelde lichter of zwaarder te wegen. Hoe zwaarder je het laat wegen, hoe 'groter' je 'sliding window'. Een voorbeeld waarbij het huidige gemiddelde 5/6de weegt en het nieuwe getal 1/6:

code:

int gem = 0;
while(true){
   int number = getNext();
   gem = 5*gem/6 + number/6;
}

[MadMan81]

Macros schreef op 03 juni 2004 @ 13:35:
...
Dan hebben alle getallen invloed op het huidige gemiddelde, alleen hoe ouder het getal hoe minder de invloed. Het nieuwste getal heeft 1/2de invloed, die daarvoor heeft 1/4de en die daarop 1/8ste etc.
...

Dat is toch het hele principe van gemiddelde? Als je 8 getallen hebt maken ze allemaal 1/8 uit van het gemiddelde, heb je er 8000 dan allemaal 1/8000.

Verder is de oplossing het zelfde als die van 12_0_13 en justmental.

[Janoz]

Wat macros probeert te vertellen, maar niet goed uitwerkt is dat je de deler een bepaald maximum geeft. Hierdoor gaan oudere waarden minder zwaar meetellen dan de zwaarte die ze volgens het eerder eerder aangegeven algoritme zouden moeten hebben.

Zolang je met een afwijking van het gemiddelde werkt gaat dit goed. De wegingsfactor voor de verschillende waardes is dan niet uniform, maar lijkt meer op een poison verdeling.

[ Voor 27% gewijzigd door Janoz op 03-06-2004 14:07 ]

[WVL_KsZeN]

code:

double oudgemiddelde = 0;
int oudaantal                = nieuwaantal = 0;
int optelsom                 = 0;


neemneemgetalaan[int getal] {
  if (optelsom>=maxint-getal)  //(komt van nieuwgemiddelde+getal>maxint, maar dan met getal aan de andere kant, anders is het resultaat nml groter dan maxint)
    {oudgemiddelde = oudgemiddelde/(oudaantal+nieuwaantal)*oudaantal + optelsom/(oudaantal+nieuwaantal);
     oudaantal=oudaantal+nieuwaantal;
     nieuwaantal=optelsom=0;
     neemgetalaan(getal);
     }
  else
    {optelsom=optelsom+getal;
     nieuwaantal++;
    }
}

double geefgemiddelde(){
    return (oudgemiddelde/(oudaantal+nieuwaantal)*oudaantal+optelsom/(oudaantal+nieuwaantal))
}

in zo'n beetje pseudo-code..., sorry, mn c is niet wat het geweest is

[ Voor 3% gewijzigd door WVL_KsZeN op 03-06-2004 14:23 ]

[Juup]

De vraag zou kunnen zijn, hoe doe ik dit zo efficient mogelijk? Daarbij wil je waarschijnlijk het aantal delingen minimaliseren. Dit kan heel gemakkelijk als je eerst n getallen sommeert en die deelt door n, en daarna de volgende n getallen (van n+1 tot 2n) en die weer door n deelt. Later neem je het gemiddelde van die gemiddelden.

[Hann1BaL]

gaat het niet makkelijk door telkens het gemiddelde wat berekend is * n te doen, dat + nieuw getal. Totaal dan delen door de nieuwe n (dus oude n +1)

Dus:

(gemiddelde*n + nieuwe waarde)/(n+1)

en dan moet je zorgen dat ook de n dus constant meeveranderd.
Dan kan je telkens met het gemiddelde doorrekenen zonder problemen.
Het is elke keer 1 vermenigvuldiging en 1 deling en nog een paar keer optellen.

Het enige wat moet worden is het gemiddelde en het aantal metingen.

edit: excuses!!! D8 dat ik goed gelezen had.....

[ Voor 14% gewijzigd door Hann1BaL op 03-06-2004 15:03 ]

[Soultaker]

Hann1BaL: dat ging dus niet, want gemiddelde*n is te groot voor een register (anders had je de som ook wel kunnen onthouden).

[Janoz]

@Hann1BaL : lees ff de startpost over hoe groot gemiddelde*n zou kunnen worden .

[bigbeng]

Aan de andere kant is het natuurlijk wel zo te herschrijven dat er geen getallen te groot worden in de subberekeningen:

( gem + ( nw / n ) ) / ( ( n + 1 ) / n )

Ik introduceer weliswaar 2 extra delingen die dus tot een nog lagere precisie leiden, maar ik heb wel mn 4VWO wiskunde B weer eens kunnen gebruiken. Voor de leek: ik heb boven en onder de breukstreek gedeeld door n en dat vervolgens uitgewerkt.

[Janoz]

Dit werkt ook niet aangezien we hier slechts met integers werken. Zodra n te groot wordt krijg je enorme afrond fouten.

[bigbeng]

Janoz schreef op 03 juni 2004 @ 15:36:
Dit werkt ook niet aangezien we hier slechts met integers werken. Zodra n te groot wordt krijg je enorme afrond fouten.

Staat ook in mn bericht hoor, ik ontkrachtte vooral het te groot worden van n*gem.
Verder wilde ik ff patsen met mn wiskundeknobbel

[Hann1BaL]

Ik heb het er hier met veel mensen over gehad, maar op deze manier begint het als onmogelijke klus te lijken. Je zal met hele grote (n) of met hele kleine (1/n) getallen moeten werken. Aangezien naarmate het aantal metingen toeneemt ook de verhoudingen anders worden en die houden verband met n.

Het punt is dus dat je het aantal metingen altijd moet meenemen in een berekening. dus deze opdracht lijkt onmogelijk.

Als het wel mogelijk is, ben ik zeer geinteresseerd in de uitkomst.

[Janoz]

Zijn de hier ( [rml]Janoz in "[ alg] continu het gemiddelde berekenen"[/rml] ) gestelde randvoorwaarden acceptabel?

[Macros]

Janoz schreef op 03 juni 2004 @ 14:04:
Wat macros probeert te vertellen, maar niet goed uitwerkt is dat je de deler een bepaald maximum geeft. Hierdoor gaan oudere waarden minder zwaar meetellen dan de zwaarte die ze volgens het eerder eerder aangegeven algoritme zouden moeten hebben.

Zolang je met een afwijking van het gemiddelde werkt gaat dit goed. De wegingsfactor voor de verschillende waardes is dan niet uniform, maar lijkt meer op een poison verdeling.

Als je nieuwe getallen een hele lage weging geeft, dan werkt het als een sliding window gemiddelde.
Voordelen:
- huidige gemiddelde is altijd beschikbaar.
- geen afrond fouten, nooit
- extreem goedkoop in cpu tijd en geheugen (data en code)
- super eenvoudig (altijd een pre )
- tweakable!
Nadelen:
- hoe lager de weging van 1 getal, hoe langer het duurt voordat het sliding gemiddelde een representieve waarde heeft berijkt (kan ondervangen worden door 2 methodes te gebruiken, de simpele sum/n methode totdat je genoeg getallen hebt)
- je hebt nooit een totaal gemiddelde aan het einde (daar zijn andere algoritmes voor die meer geheugen gebruiken)

Misschien kan je zelf met 2 ints een veel groter getal 'simuleren', dan kan je gewoon de som in 2 (of zelfs meer ints) opslaan en dan gewoon delen door het aantal getallen. Als je unsigned ints gebruikt, kan je gewoon controleren of een + operatie op de sum, de sum kleiner maakt dan tevoren, of een exception kan catchen, dan verhoog je de 2de int met 1.
Dat delen aan het einde laat ik aan de lezer over om op te lossen

[ATS]

De optie van Marcos is best een goede: waarom niet een grotere int simuleren? Als je totaal binnen MAXINT^2 blijft, dan is dit een eenvoudige oplossing. Optellen is een kwestie van een check op een overflow en eventueel 1 optellen bij je most significant byte, en delen is ook niet zo'n heksentour. Eventueel kan je bij het berekenen van het gemiddelde alsnog naar een double converteren.
De optie van WVL_KsZeN is ook mooi trouwens.

[WVL_KsZeN]

hmmm.. ik vind idd de optie van een langere int simuleren ook een hele goede waarom heb ik daar niet eerder aan gedacht )

LOL, ik doe dat soort dingen namelijk altijd op mn c64-je, voor mn nieuwste projecte (pinball dreams c64) gebruik ik voor sommige dingen zelfs 4 bytes (zijn integers op de 64).

bv voor de positie.. snelheid is bij mij 3 bytes..

nou ja ), langere integer simuleren is idd wel het beste! lekker snel+makkelijk te programmeren! ideaal.

[MadMan81]

Mensen, het gaat hier om een PLC: dan worden dingen als exceptions en overflows best lastig, als het al niet onmogelijk is. En anders blijft het gewoon te duur (te veel rekentijd), let wel die dingen moeten zo min mogelijk code hebben!!! Bovendien gaat hij straks van 16 meetpunten iedere scan opnieuw het gemiddelde berekenen!

Ook die grote bakken code die sommige posten: het zal waarschijnlijk wel werken, maar is gewoon te duur om het in een PLC te gebruiken.

En wat ik ook al zei: getallen achter de komma zijn niet belangrijk: Als het nauwkeurig kan, graag!!!... maar het is geen must.

Maar wat ik een aantal keer terug ook al vroeg: wat is er mis met deze oplossing van Justmental:?

nieuwe gem = oude gem + ( nieuwe waarde - oude gem ) / aantal waarden

[WVL_KsZeN]

even kijken...

stel dat er tot nu toe k meetwaarden zijn.

het gemiddelde is dan gemiddelde=a1/k+a2/k+...+ak/k.

als er een nieuwe meetwaarde binnenkomt, wordt dit gemiddelde het oude gemiddelde.

het nieuwe gemiddelde zou zijn (l=k+1): a1/l+a2/l+...+a(l-1)/l+al/l

de eerste l-1 termen zijn gelijk aan het oudegemiddelde*k/l = oudgemiddelde * (l-1)/l.

de laatste term is gewoon al/l.

oftewel :

code:

nieuwgemiddelde = oudgemiddelde*(nieuwaantalwaarden-1)/nieuwaantalwaarden+nieuwewaarde/nieuwaantalwaarden

ff kijken of we dat kunnen schrijven zoals justmental deed :

even kort :

oudgemiddelde = o, aantalwaarden = l, n= nieuwe waarde

nieuwgemiddelde = o(l-1)l+n/l= (ol-o)/l+n/l=(ol-o+n)/l=o+(n-o)/l

net zoals justmental schrijft, dus die klopt.

[Anoniem: 70801]

Om mijn nieuwe gemiddelde op school uit te rekenen zonder rekenmachine doe ik altijd als volgt:

Stel je staat een 7 gemiddeld behaald uit 4 toetsen. Op je volgende toets haal je een 9, wat is nu het nieuwe gemiddelde?

7 + (9 - 7) / (4 + 1)

code:

oude gemiddelde + (behaalde cijfer - oude gemiddelde) / nieuwe aantal toetsen

De geldigheid hiervan is eenvoudig aan te tonen, heb ik nu even geen zin in.


* Anoniem: 70801 is weer eens spuit-11

[ Voor 22% gewijzigd door Anoniem: 70801 op 04-06-2004 00:00 ]

[Soultaker]

Ik heb het idee dat er een beetje dubbelop suggesties gedaan worden. Lees alsjeblieft de thread voordat je reageert, want het wordt zo wel erg lastig om de verschillende unieke voorstellen te onderscheiden. Een aantal daarvan zijn trouwens ook ondertussen al ontkracht (lees ook daarvoor de thread, dat ga ik dus ook niet herhalen).

[Janoz]

MadMan81 schreef op 03 juni 2004 @ 23:19:
Maar wat ik een aantal keer terug ook al vroeg: wat is er mis met deze oplossing van Justmental:?

[...]

Het probleem hierbij is dat naarmate het aantal meetwaarden groter wordt het aanpassen van het gemiddelde steeds onnauwkeuriger wordt. Zodra het aantal meetwaarden meer dan 2x zo groot is als de gemiddelde afwijking van het gemiddelde zal de aanpassing altijd 0 zijn. zelfs bij het oplopen van het gemiddelde (telkens .4 aanpassing) zie je dit niet terug in het gemiddelde.

[LuCarD]

Volgens mij kan je twee gemiddelen gebruiken.

Dus wat je doet je pakt een gemiddelde van twee metingen, slaat deze op. Daarna maak je weer een gemiddelde van twee metingen. En telt deze bij het vorige gemiddelde op en deelt deze door 2.


Klein voorbeeld:
je hebt de volgende metingresultaten: 5 7 9 en 12
5+7 = 12 /2 = gemiddelde 6
9+12 = 21 / 2 = gemiddelde 10,5
6+10,5 = 16,5/2 = gemiddelde 8,25

5+7+9+12 = 33 = gemiddelde 8,25

[edit] Leuk geprobeerd maar dit werkt niet...

[ Voor 24% gewijzigd door LuCarD op 04-06-2004 10:25 ]

[12_0_13]

Ik sluit me aan bij Janoz, op een gegeven moment is de factor die nieuwe waarden meekrijgen te klein om => de waarde wordt dan gewogen met 0 en telt niet meer mee.

Een window is inderdaad dan de beste oplossing

Nog even over het formaat (ik neem aan dat het over 32 bit int's gaat?) Er bestaan methoden om "getallen achter de komma" ook op te slaan. Het makkelijkst is bijv vermenigvuldigen met 64, ofwel left shift met 6. Deze "truc" is bekend als 26.6 fixed float format.

@LuCarD volgens mij is dat ongeveer wat de TS heeft geprobeert. Het werkt dus niet. Voor 4 getallen gaat het goed, maar probeer maar eens met 8 (of leuker met 7 getallen) .

[ Voor 24% gewijzigd door 12_0_13 op 04-06-2004 10:18 ]

[LuCarD]

12_0_13 schreef op 04 juni 2004 @ 10:15:

@LuCarD volgens mij is dat precies wat de TS heeft geprobeert, en dat werkt dus niet

je hebt gelijk....

[MadMan81]

Janoz schreef op 04 juni 2004 @ 09:58:
[...]


Het probleem hierbij is dat naarmate het aantal meetwaarden groter wordt het aanpassen van het gemiddelde steeds onnauwkeuriger wordt. Zodra het aantal meetwaarden meer dan 2x zo groot is als de gemiddelde afwijking van het gemiddelde zal de aanpassing altijd 0 zijn. zelfs bij het oplopen van het gemiddelde (telkens .4 aanpassing) zie je dit niet terug in het gemiddelde.

En een "voorschrijdend gemiddelde" zou hiervoor dan de oplossing zijn? Hoe maak ik dan (simpel) zoiets?

[WVL_KsZeN]

toch denk ik dat je vast blijft zitten aan ofwel de methode die ik eerst postte in code, waarbij je dus net zolang blijft optellen tot je aan max_int zit, en dan deelt,

of de methode waarbij je langere int's simuleert.

langere ints-methode :

code:

void neemgetalaan(int){
  optelsom:=optelsom+nieuwewaarde;
  (nu weet ik niet hoe je in c de carry schrijft, maar ik schrijf dus maar gewoon carry)
  groteoptelsom:=groteoptelsom+carry;
  waardes++;
}

int geefgemiddelde(){
  return (optelsom/waardes+waardes/max_int*groteoptelsom);
}

bij deze methode moet je echter uit gaan kijken hoe het zit met negatieve waardes, dus die moet je apart afhandelen enzo..

volgens mij blijf je hoe dan ook met exceptions zitten, als je wilt dat de waardes een beetje nauwkeurig blijven.

btw, misschien is de methode die ik eerst postte wel makkelijker, dan hoef je niet te kutten in het geval van negatieve waardes...

[ Voor 26% gewijzigd door WVL_KsZeN op 04-06-2004 11:43 ]

[MadMan81]

Om nog even terug te komen op het feit of de functie van justmental wel of niet nauwkeurig is. Is dat niet met het bewijs van WVL_KsZeN aangetoond (er van uitgaande dat er niet tussentijds wordt afgerond)?

Ik heb het ff getest met een een set van 100 willekeurige getallen. Zonder afronding is het nl precies het zelfde... Zelfs met afronding is het verschil minimaal (1752 ipv 1750.72).

Ik hoor steed dat de nieuwe waarde steeds minder invloed heeft op het gemiddelde: maar dat is toch logisch, das toch altijd met gemiddelden..

@WVL_KsZeN: het opvangen van de carry is niet mogelijk in de PLC (het is geen C of Delphi of wat voor prog omgevening voor PC's dan ook). De PLC code wordt gemaakt met Concept.

@12_0_13: floats kent ie ook niet..En het zijn 16 bit's integers..

[Anoniem: 53025]

ff een heel andere vraag: wat moet je meten en wat is je scaninterval?

Meeste temperatuurmeters, energiemeters en tellers enzo zijn tegenwoordig leverbaar met RS232 of RS485 en geven keurig het gemiddelde in 16 bits integer op deze poort.

[Macros]

MadMan81 schreef op 04 juni 2004 @ 11:26:
[...]


En een "voorschrijdend gemiddelde" zou hiervoor dan de oplossing zijn? Hoe maak ik dan (simpel) zoiets?

Mijn code is een voorbeeld van een voortschrijdend gemiddelde.
Ook kan je een buffer maken van de grootte van je window en een kleine pointer met waar je je in de buffer bevind (een soort van circulaire buffer).
Elke keer als je een getal erbij krijgt, overschijf je het huidige getal waar je pointer nu op staat en verhoog je je pointer, als je pointer buiten de buffer valt, laat je hem weer aan het begin beginnen. Dan bereken je het gemiddelde van alle waardes in je buffer.

[Janoz]

De simpelste methode voor een voortschreidend gemiddelde is een gewogen gemiddelde waarbij de laatst toegevoegde waarde het zwaarst meetelt en de oudste het minst. De implementatie is erg simpel. ipv dat je de afwijking door het totale aantal deelt, geef je deze waarde een bepaald maximum. Zorg dat je dit maximum zo kiest dat de afwijking significant blijft. Ook is het misschien handig om fixed point getallen te gebruiken om het bereik van het gemiddelde optimaal op het bereik van een 32bit veld te mappen.

Een andere methode die ik had bedacht bepaald het exacte gemiddelde over de laatste 2^(n+1) -1 tot 2^n waardes. Hiervoor heb je n+1 integer velden nodig (mits n>32, maar dat lijkt me meer dan genoeg). De eerste waarde zet je in het eerste veld. en je zet in een controle getal 1 (Dit wordt een bitmap met actieve waardes). De volgende waarde tel je hierbij op en het resultaat deel je door 2 en zet je in de tweede waarde. De waarde in het eerste veld en de nieuwe zijn samengenomen in het tweede veld en het eerste veld is niet meer relevant. In het controle getal zet je nu 2 (alleen het tweede veld is actief). De derde waarde die je binnenkrijgt zet je gewoon weer in het eerste veld. In het controle getal staat nu 3 (eerste 2 velden zijn actief).

Op deze manier sla je dus telkens een groep gemiddelde waarden op en in het controle getal staat welke 'actief' zijn. In het eerste veld staat (mits actief) de laatste waarde. Het tweede veld heeft (mits actief) het gemiddelde van de twee waardes hiervoor. Het derde getal heeft (mits actief) het gemiddelde van de 4 getallen daarvoor.

Het gemiddelde bepaal je nu door een gewogen gemiddelde over deze n getallen te nemen. De eerste telt 1x mee, de 2e 2x en de derde 4x enz. Aan het controle getal kun je zien welke getallen je mee moet nemen.

Als alle getallen actief zijn (controle getal bevat binair n keer een n) baseer je je gemiddelde op 2^(n+1) -1 waardes. Het minimale aantal waardes is waneer alleen het meest significante veld actief is (controle getal bevat binair een 1 en dan n-1 nullen) . Dan wordt het gemiddlede op 2^n waardes gebaseerd (mits genoeg waardes zijn gemeten)

---edit----

Ah, je gebruitk 16 bit. Lees dan 16 ipv 32

[Janoz]

MadMan81 schreef op 04 juni 2004 @ 12:04:

Ik hoor steed dat de nieuwe waarde steeds minder invloed heeft op het gemiddelde: maar dat is toch logisch, das toch altijd met gemiddelden..

Ja, maar als er eigenlijk al 100 keer 0.4 bij het gemiddelde opgeteld zou moeten worden wordt er bij integer berekeningen gewoon telkens 0 opgeteld. Eigenlijk had het gemiddelde dan al 40 hoger moeten liggen, maar gebeurt dit niet. Je hebt gelijk dat een gemiddelde steeds minder meeteld, maar door afrond fouten gebeurt dit al veel eerder en op een wiskundig niet correcte manier.

[farlane]

MadMan81 schreef op 03 juni 2004 @ 09:34:
Wat betreft de format: het grootste integer die de omgeving kent is de 16 bit unsigned integer. Het gaat hier ook niet om een pc, maar om een PLC.

Welk merk ? Behoorlijk oud ofnie ?

[12_0_13]

@12_0_13: floats kent ie ook niet..En het zijn 16 bit's integers..

Ik bedoelde ook int's .

Als je niet het hele bereik nodig hebt van de 16 bit int (bijvoorbeeld omdat je alleen maar waarden tussen 0 en 1024 ofzo binnenkrijgt) kan je float 'emuleren'.

Bij als je 4 opslaat word het normaal: (MSB first)

0000 0000 0000 0100

Nu shift je dat naar links (bijv 4 plaatsen: ), en heb je 4 bits om getallen achter de komma op te slaan. Je slaat eigenlijk 16*4 = 64 op.

0000 0000 0100 0000


Stel nu dat je er 2 optelt en deelt door 2, bijvoorbeel 4 en 5

dat zou dan worden:

0000 0000 0100 0000
0000 0000 0101 0000 +
0000 0000 1001 0000

delen door 2:

0000 0000 0100 1000 = 72 (72/16 = 4,5)

nu heb je 4.5 opgeslagen zonder direct een afrondfout te introduceren. Zo kan je toch een soort float gebruiken (fixed float) terwijl je gewoon ints hebt. Je kan je precisie dus verhogen.

Bij 32 bits int is 26.6 gebruikelijk, dus 6 bits voor het getal achter de komma.

[ Voor 8% gewijzigd door 12_0_13 op 04-06-2004 13:29 ]

[Macros]

Niet fixed float, maar fixed point (in tegenstelling tot floating point)

[12_0_13]

Ik heb de term ook maar overgenomen van de luitjes van de freetype lib, die noemen het fixed float.

Zie halverwege: http://freetype.sourcefor...docs/glyphs/glyphs-6.html

Maar je hebt wel gelijk vind ik

[ACM]

De enige min-of-meer correcte oplossing, die ik kan bedenken, voor een groot aantal gemiddeldes met een redelijk goede voorkoming van zowel over- als underflow is gebruikmaking van statistiek, de wet van de grote aantallen:
Hou het gemiddelde (g) bij en het aantal waarden (n).

De nieuwe waarde x toevoegen gaat als volgt:
n = n + 1
y = x / n, met afronding naar beneden (indien mogelijk, anders wordt het wel lastig ) eventueel is dat natuurlijk ook met aantal iteraties x - n mogelijk tot x - n < n.
z = x % n, bepaal de restwaarde van x / n, evt kan dat ook in de vorige set iteraties (de overgebleven waarde van die iteraties).
dan moet je een random waarde tussen 0 en n bepalen
r = rand(0,n)
g = g + y
En als r < z dan g = g + 1

Dat levert je vast niet exact het gemiddelde op, maar uiteindelijk met veel getallen wel een waarde die met hoge kans dicht bij het werkelijk gemiddelde ligt

Nadeel is natuurlijk die randomwaarde bepalen, daarvan wordt de berekening vrij kostbaar...

[12_0_13]

Als je de wet van de grote getallen gebruikt, én je data is ongeveer symmetrisch verdeeld kan je ook het volgende doen:

* initialiseer je gemiddelde op een willekeurige waarde

een waarde komt binnen:

*is deze waarde hoger dan het gemiddelde, verhoog het gemiddelde dan met het kleinst mogelijke stapje
*is deze waarde lager dan het gemiddelde, verlaag dan het gemiddelde dan met het kleinst mogelijke stapje .

Is nog te optimaliseren door in het begin grotere stappen te maken.

[Janoz]

Als het gemiddelde erg lang hetzelfde is gebleven en vervolgens de waardes erg lager worden wordt in jou implementatie het gemiddelde teveel aangepast. In dat opzicht is de implementatie van ACM correcter.

[12_0_13]

Dat is waar.. het is eigenlijk meer een soort van lopend gemiddelde op mijn manier.

[FireWood]

Zijn alle getallen standaard vrij hoog met weinig fluctuatie, of zit er heel veel fluctuatie in? Indien er veel fluctuatie in zit kun je de methode gebruiken die ergens hier boven al staat, anders moet je met een zwevende nul gaan werken, dit zorgt voor meer ruimte/nauwkeurigheid. Als er zoms veel fluctuatie is en soms haast niks, dan heb je een probleem, misschien kun je dan deze twee methodes combineren, maar dan wordt het moeilijk voor de PLC.

(Kun je misschien geen soft-PLC gebruiken is het allemaal wat makkelijker )

Wat voor PLC gebruik je? Misschien dat ik dan nog een trucje ken.