Algorithmus für AVG

[FireFlow]

Ich hab ein ziemlich komisches Problem:
Ich suche einen Alorithmus um einen Durschnittswert zu berechnen ohne jeden Wert zusammen zu zählen und durch die Anzahl zu teilen.

einfaches Beispiel:

int werte[100];
for(int i=0; i<100; ++i)
{
    werte[i] = rand();
}

// folgendes würde nun nicht gehen wenn die zahlen zu groß sind
int sum = 0, avg;
for(int i=0; i<100; ++i)
{
    sum += werte[i];
}
avg = sum / (sizeof(werte) / sizeof(werte[0]));

Wenn ich nun diese Werte alle zusammen zähl kann es ja sein dass die größer/kleiner werden (-)2.147.483.647 und dann würde gar nichts mehr stimmen.

Hat jemand eine Idee wie das geht?

 

[Kachelator]

Also, bei meinem VC++ eist der Maximalwert, den rand() ergibt, RAND_MAX. Das ist folgendermassen definiert:
The constant RAND_MAX is the maximum value that can be returned by the rand function. RAND_MAX is defined as the value 0x7fff.
0x7fff ist dezimal 32767. Der Wertebereich von int ist wesentlich grösser, so dass du dir keinerlei Sorgen machen musst, mit 100 Ergebnissen einen Overflow zu erzeugen, weil du auf maximal 3276700 kommst.

ohne jeden Wert zusammen zu fählen

Hm? Wie bitte?

 

[FireFlow]

Das war ja nur ein Beispiel. Wie sieht es aus wenn ich 1000 oder 10000 Werte hab. Eigentlich kommen die Werte von einer Schnittstelle. Das Problem ist nicht dass ich sehr hohe Zahlen hab sondern sehr viele. Gibts da keine Lösung?

 

[basd]

also wenn du mit double precission nicht auskommst (hier wäre es dann aber vielleicht besser jedes einzelnen element mit 1/N zu dividieren und diese zu addieren)

Als letzte Lösung wäre es sich eine eigene Klasse zu schreiben die z.B.: ein riesen Integer mit quasi unbegrenztem Wertebereich abbildet

 

[Kachelator]

also wenn du mit double precission nicht auskommst (hier wäre es dann aber vielleicht besser jedes einzelnen element mit 1/N zu dividieren und diese zu addieren)

Den Algorithmus würde ich gerne mal analysiert sehen. Ich bin nicht sicher, aber ich glaube, da steckt ein Denkfehler drin.

Als letzte Lösung wäre es sich eine eigene Klasse zu schreiben die z.B.: ein riesen Integer mit quasi unbegrenztem Wertebereich abbildet

So was findet sich ja fertig auch im Netz.

Alternativ wären auch 64-Bit-Integers einsetzbar. Du könntest dann knapp 562949953421312 Werte summieren, falls du es schaffst, an so viele Daten zu kommen und sie zwischenzuspeichern. Hm, bin gerade zu faul, auszurechen, wieviel Gigabyte an Eingabedaten das wären.

Übrigens könnte man auch immer solange Werte addieren, bis man kurz vor Overflow steht und dann den Mittelwert bilden. Diesen merkt man sich mitsamt der Anzahl von Werten, die zu seiner Bildung beitrugen. Dasselbe macht man mit den restlichen Werten, bis alle Werte verarbeitet sind. Nun kann man die gebildeten Mittelwerte noch einmal gewichtet mitteln.

 

[SilentWarrior]

Ein Ansatz für einen anderen Algorithmus wäre der, dass du jeweils den Durchschnitt einer Zahl n und den Durchschnitt aller Zahlen von 1 bis n - 1 berechnest.

Ok, klingt jetzt verwirrend, Beispiel:

Zahlen: 1, 3, 5
Durchschnitt von 1 und 3: 2
Durchschnitt von [1,3] und 5: (5/2 + 2) / (3/2)

Die beiden /2 Operationen, weil [1,3] zwei Zahlen sind. Da käme dann einfach n rein.

Hm... ich befürchte, das hat niemand verstanden.

 

[basd]

also wenn du mit double precission nicht auskommst (hier wäre es dann aber vielleicht besser jedes einzelnen element mit 1/N zu dividieren und diese zu addieren)

Naja mit 1/N multiplizieren natürlich; Wenn N vorher bekannt ist und alle Zahlen im Speicher sind bzw. einlaufen ... ist das einfach das disrtibutiv gesetzt
(a + b) c = ac + bc
bzw, (1/N) sum(Xn) = sum( Xn / N )

Ich glaub was Silent warrior meinte:

Mn = ((n-1)/n) Mn-1 + Xn
M2 = (X1 + X2)/2

Mn : Mittelwert nach dem n-ten Wert
Xn der neue Wert
Aber hier musst du auf jeden fall mit double rechnen und ich weiß net wie lange des mit (n-1)/n gut geht, weil double ja präzission verliert wenn die Zahlen sehr groß werden aber mit 10000 wirds da noch keinen ärger geben