Math « C++Guns – RoboBlog

07.01.2019

C++ Guns: PRNG

Filed under: Allgemein — Tags: Cpp, Math — Thomas @ 20:01

Parallel mit mehreren Zufallsgeneratoren zu arbeiten ist echt nicht einfach. Die Details verstecken sich im Verständnis.

Mit welchen Seed werden sie erstellt? Einfach die Zeit in Sekunden plus 1, 2 3, 4? Wir können das ja einfach mal ausprobieren.
Die ersten drei Zahlen von vier Generatoren:

int main() {
  for(int j=1; j < 5; ++j) {  
    cout << "\nseed " << j << "\n";
    std::minstd_rand gen(j);

    for(int i=0; i < 3; i++) {
      cout << gen() << "\n";
    }
  }
}

seed 1
48271
182605794
1291394886

seed 2
96542
365211588
435306125

seed 3
144813
547817382
1726701011

seed 4
193084
730423176
870612250

Setzt man die Zahlen ins Verhältnis zueinander und plottet sie, kommt der AHA Effekt:

Ach was. Zumindest die zuerst gezogenen Zahlen stehen ja in einem festen Verhältnis. Das Verhältnis der dritten gezogene Zufallszahl ist zwar nicht mehr gleich, aber immer noch bei allen eine kleine Zahl. Na, wenn diese vier Generatoren nicht "parallel" laufen ;)

Der C++ Standard antwortet uns mit std::seed_seq

std::seed_seq consumes a sequence of integer-valued data and produces a requested number of unsigned integer values i, 0 ? i < 232 , based on the consumed data. The produced values are distributed over the entire 32-bit range even if the consumed values are close.
...
The following algorithm is used (adapted from the initialization sequence of the Mersenne Twister generator by Makoto Matsumoto and Takuji Nishimura, incorporating the improvements made by Mutsuo Saito in 2007)

Weiterführende Quellen
Sehr interessant: Finding the Best 64-bit Simulation PRNG
Multiple independent random number streams
Dynamic Creation (DC) of Mersenne Twister generators.
Scalable Parallel Random Number Generators Library
Tina’s Random Number Generator Library

Comments Off

25.06.2015

Warum wird bei der Varianz durch n-1 geteilt?

Filed under: Allgemein — Tags: Math — Thomas @ 19:06

Warum wird bei der Varianz durch n-1 geteilt?
Google bietet bestimmt eine fülle an Antworten. Hier ist noch eine:

1/(n-1) * SUM_i=1,n(xi-xavg)^2
Man teilt durch die Anzahl der Freiheitsgerade. Lässt man das Quadrat in der Summe weg, so ergibt die Summe 0. Der n-te Term ist gleich minus der Summe der vorherigen Terme. Dadurch ist der n-te Term eindeutig festgelegt. Der Freiheitsgrad beträgt nur noch n-1

Update 12.2018
Das nennt sich wohl Bessel's correction

In statistics, Bessel's correction is the use of n ? 1 instead of n in the formula for the sample variance and sample standard deviation, where n is the number of observations in a sample. This method corrects the bias in the estimation of the population variance. It also partially corrects the bias in the estimation of the population standard deviation. However, the correction often increases the mean squared error in these estimations. This technique is named after Friedrich Bessel.

Comments Off

26.03.2013

2^168605209-1 not prime

Filed under: Allgemein — Tags: Math — Thomas @ 10:03

Ich dacht mir, gibt das doch mal in den Taschenrechner ein und überprüfe, ob diese Mersenne Zahl wirklich keine Primzahl ist.
Normale Taschenrechner können so große Zahlen nicht handeln, aber zum Glück gibt es ja die Konsolentools. Z.B. das Programm bc.

echo 2^168605209 | bc -l > zahl
wc -ml zahl
746401 52248027 zahl

Das Ergebnis hat also 51501626 Ziffern (Man muss das Zeilenfortsetzungszeichen "\" abziehen).
Die Zahl 40695358776195832999 soll angeblich ein Faktor sein. Wenn man bc damit füttert, bekommt man eine halbe Stunde später das Ergebnis. Hier die letzten paar Ziffern der Zahl: 432489.0
Wie man sieht ist die Nachkommastelle 0 und damit die Zahl ein ganzer Teiler.

wc -ml ergebnis
746401 52248009 ergebnis

Das Ergebnis hat also 51501608 Ziffern. Halt! Der Dezimalpunkt und die Nachkomma Null zählen nicht mit, also 51501606 Ziffern.
Das macht ein Unterschied von 18 Ziffern gegenüber der Mersenne Zahl. Und der Faktor hat 20 Stellen. Na wo könnten denn die andern 2 Stellen geblieben sein? ;)

Comments (0)

C++Guns – RoboBlog blogging the bot