mikrocontroller.net

Forum: PC-Programmierung C++: rand() gleichmäßige Verteilung


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
Autor: Felix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

ich habe folgenden Code:
int main()
{
  srand(time(NULL));

  std::array<int, 100> myArray = {};

  for (int i = 0; i < myArray.size(); i++)
  {
    myArray.at(i) = rand() % 2;
  }

  int sum = 0;

  for (int i = 0; i < myArray.size(); i++)
  {
    sum += myArray.at(i);
  }

  std::cout << sum << std::endl;
}

Ich befülle das Array mit einem zufälligen Muster aus 0 und 1. Addiere 
ich nun den Inhalt des Array, lande ich immer zwischen 40 und 60. Es 
findet somit eine fast ausgewogene Verteilung von 0 und 1 statt. Für 
meine Anwendung benötige ich aber auch den Fall, dass ich zwischen 10 
und 90 komme. Wie kann ich das lösen?

Viele Grüße
Felix

Autor: Max M. (jens2001)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Felix schrieb:
> lande ich immer zwischen 40 und 60.

Felix schrieb:
> benötige ich aber auch den Fall, dass ich zwischen 10
> und 90 komme


Die Verteilung folgt im Idealfall einer Gauß-Normalverteilung.
Mach das oft genug dann ist auch 10% und 90% dabei.
Für unendliche Anzahl von Durchläufen sogar 0% und 100%.

: Bearbeitet durch User
Autor: Felix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Max M. schrieb:
> Die Verteilung folgt im Idealfall einer Gauß-Normalverteilung.
> Mach das oft genug dann ist auch 10% und 90% dabei.
> Für unendliche Anzahl von Durchläufen sogar 0% und 100%.

Super, vielen Dank für die Information.

Autor: Theor (Gast)
Datum:

Bewertung
-2 lesenswert
nicht lesenswert
Das mit der Gauß-Verteilung (die typische Glockenkurve) müsste man 
meiner Meinung nach, mal durch eine Quelle belegen. Ich kenne allerdings 
keine.

Eine kurze Suche führt zu dem Ergebnis, dass der C++ Standard (welcher 
genau, habe ich auf die Schnelle nicht feststellen können) nichts über 
die Verteilung sagt. Also haben die Zahlen irgendeine Verteilung. 
(Nichts desto Trotz wird aufgrund des konkreten Verfahrens die 
Verteilung schon eine bestimmbare sein. Das Gegenteil will ich damit 
nicht sagen). Ich würde also mal in dem konkret anwendbaren Standard 
nachschauen.

An anderer Stelle wird darauf hingewiesen, dass POSIX sehr wohl 
vorschreibt, dass die Verteilung eine Gleichverteilung ist. Es wäre also 
die Frage, ob der Compiler bzw. die verwendete Bibliothek den Anspruch 
hat POSIX-konform ist und ob sich das auch auf die rand-Funktionen 
bezieht. Das kann man sicher in der Doku zum Compiler resp. der 
Bibliothek feststellen.

Zu beachten ist auch, dass die modulo-Operation zu einer leichten 
Bevorzugung der kleineren Zahlen innerhalb der Spanne 0 und n (bei 
Anwendung von  rand () % n) führt. Siehe: 
http://www.cplusplus.com/reference/cstdlib/rand/ Leider habe ich die 
math. Begründung dafür auf die Schnelle nicht finden können.

Vorsicht bitte also bei der Annahme, es handele sich hier fraglos um 
eine Gauss-Verteilung. :-)

Autor: Dirk K. (merciless)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich finde die Verwendung des Arrays seltsam:
Benötigst du solch ein Array, dass die Anforderungen
erfüllt (Summe aller Elemente in einem Bereich)
oder benötigst du eine Zahl die in einem Bereich liegt?

https://en.cppreference.com/w/cpp/numeric/random
http://www.cplusplus.com/reference/random/

merciless

Autor: Peter M. (r2d3)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Hallo Theor,

Theor schrieb:
> Vorsicht bitte also bei der Annahme, es handele sich hier fraglos um
> eine Gauss-Verteilung. :-)

so aus dem Kopf:

Dem zentralen Grenzwertsatz von ??? nach, folgt die Summe von 
Zufallswerten aus beliebigen Verteilungen immer einer Gauss'schen 
Verteilung.

Felix schrieb:
> Ich befülle das Array mit einem zufälligen Muster aus 0 und 1. Addiere
> ich nun den Inhalt des Array, lande ich immer zwischen 40 und 60. Es
> findet somit eine fast ausgewogene Verteilung von 0 und 1 statt. Für
> meine Anwendung benötige ich aber auch den Fall, dass ich zwischen 10
> und 90 komme. Wie kann ich das lösen?

Deiner Frage fehlt die Angabe der von Dir gewünschten Zielverteilung.
Sind 10 und 90 harte Grenzen?

Dann solltest Du mit der Formel 10 + 80*zufall() gleichverteilte 
Zufallszahlen erzeugen können unter der Voraussetzung, dass zufall() 
gleichverteilt im Intervall [0;1[ ist.
Ob bei Deiner Zufallsfunktion die obere Intervallgrenze dazugehört, 
müsstest Du mal überprüfen.

Sollen die Zahlen Gauss-verteilt sein, gibt es eine Formel, mit der Du 
gleichverteilte Zufallszahlen in standardnormalverteilte (µ=0, sigma=1) 
überführen kannst.

Autor: Franko S. (frank_s866)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
<random> hat verschiedene Generatoren auch gleichverteilte,
da stellst du die oberen und untern grenzen ein, dann tauchen die Werte 
innerhalb der Grenzen auch öfters auf. So wie du das oben machst 
erreichst du bei array-size=100 praktisch nie diese Werte die du 
anvisierst.
Ich weiss auch nicht was du genau vor hast, wenn es nur um Werte 
innerhalb eines Intervals geht, also deine "sum" dann geht das ohne 
Array.


http://www.cplusplus.com/reference/random/

Autor: Felix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dirk K. schrieb:
> Ich finde die Verwendung des Arrays seltsam:
> Benötigst du solch ein Array, dass die Anforderungen
> erfüllt (Summe aller Elemente in einem Bereich)
> oder benötigst du eine Zahl die in einem Bereich liegt?

Franko S. schrieb:
> Ich weiss auch nicht was du genau vor hast, wenn es nur um Werte
> innerhalb eines Intervals geht, also deine "sum" dann geht das ohne
> Array.

Es geht darum, dass ich mehrere Arrays benötige, die jeweils eine 
unterschiedliche Anzahl an 0 und 1 haben (Reihenfolge egal). Damit meine 
ich, dass z.B. ein Array mit nur 1en genau so wahrscheinlich ist wie ein 
Array mit nur 0en und natürlich alles dazwischen.

Viele Grüße

Autor: Theor (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter M. schrieb:
> Hallo Theor,
>
> Theor schrieb:
>> Vorsicht bitte also bei der Annahme, es handele sich hier fraglos um
>> eine Gauss-Verteilung. :-)
>
> so aus dem Kopf:
>
> Dem zentralen Grenzwertsatz von ??? nach, folgt die Summe von
> Zufallswerten aus beliebigen Verteilungen immer einer Gauss'schen
> Verteilung.
> [...]

Ich vermute, Du willst einwenden, dass die wiederholte Ausführung des 
Programmes oben, zu Summen führt, die Normalverteilt sind, richtig?

Ich vermute weiter Du willst damit sagen, dass es für den Zweck des TOs 
unwichtig ist, welche konkrete Verteilung vorliegt. Dem stimme ich unter 
dem Vorbehalt zu, dass die restlichen Voraussetzungen der endlichen 
und positiven Varianz zutreffen.

Mein Einwand richtet sich im Kern aber auf die Aussage, rand liefere 
definitiv eine Normalverteilung. Das eben ist im Standard nicht 
beschrieben, aber in POSIX. Darum ging es mir. Falls nämlich die Lib 
nicht POSIS konform ist (falls zugegeben eher unwahrscheinlich ist), 
dann ist auch die Varianz nicht zwingend positiv und endlich.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Theor schrieb:
> Das mit der Gauß-Verteilung (die typische Glockenkurve) müsste man
> meiner Meinung nach, mal durch eine Quelle belegen. Ich kenne allerdings
> keine.

Die Anzahl der 1-Bits folgt einer Binomialverteilung

  https://de.wikipedia.org/wiki/Binomialverteilung

Die Wahrscheinlichkeit, dass 90 von 100 Bits den Wert 1 haben, ist nur
1.37E-17, so dass man ziemlich viele Versuche starten muss, um einmal
diesen Fall zu erhalten. Lange vorher wird man schon an die Grenzen des
Zufallsgenerators aus der Standardbibliothek stoßen.

Felix schrieb:
> Es geht darum, dass ich mehrere Arrays benötige, die jeweils eine
> unterschiedliche Anzahl an 0 und 1 haben (Reihenfolge egal).

Dann erzeuge einfach eine gleichverteilte Zufallszahl n mit 0≤n≤100 und
fülle die ersten n Elemente des Arrays mit 1, den Rest mit 0.

Autor: Theor (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Theor schrieb:
>> Das mit der Gauß-Verteilung (die typische Glockenkurve) müsste man
>> meiner Meinung nach, mal durch eine Quelle belegen. Ich kenne allerdings
>> keine.
>
> Die Anzahl der 1-Bits folgt einer Binomialverteilung
>
>   https://de.wikipedia.org/wiki/Binomialverteilung
>
> [...]

Und wo steht, dass der Compiler resp. die verwendete Lib Zufallszahlen 
mit Binomialverteilung erzeugt?

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Theor schrieb:
> Und wo steht, dass der Compiler resp. die verwendete Lib Zufallszahlen
> mit Binomialverteilung erzeugt?

Ja, die Verteilung bzw. der Algorithmus der rand-Funktion ist nicht
spezifiziert. Üblicherweise sind die von rand() erzeugten Zufallszahlen
aber gleichverteilt, und mir ist auch keine C-Bibliothek bekannt, die
sich diesbezüglich anders verhält.

Die Binomialverteilung bezog sich auf die Anzahl der 1-Bits im Array
unter der Annahme, dass rand() gleichverteilte Zufallszahlen liefert.

Wenn man aber sowieso C++ verwendet, sollte man die mit C++11
eingeführten Zufallszahlenklassen/-templates verwenden, für
gleichverteilte Zahlen also std::uniform_int_distribution.

  https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution

Autor: Peter M. (r2d3)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Felix schrieb:
> Es geht darum, dass ich mehrere Arrays benötige, die jeweils eine
> unterschiedliche Anzahl an 0 und 1 haben (Reihenfolge egal). Damit meine
> ich, dass z.B. ein Array mit nur 1en genau so wahrscheinlich ist wie ein
> Array mit nur 0en und natürlich alles dazwischen.

Lösungsvorschlag:

n ist Deine Array-Länge
m (m<n) ist die Anzahl der Einsen

Die bestimmst mit einer Ziehung aus dem Zufallsgenerator die Zahl Deiner 
Einsen.

p ist dann die Anzahl der Nullen. (p=n-m)

Nun richtest Du Dir gedanklich einen Puffer der Länge n ein, in dem die 
erst die Nullen und Einsen stehen.

Den verwaltest Du mit zwei Variablen r und s
r ist die Restpufferlänge (Ausgangswert n)
s ist die letzte Stelle, an der 0 steht: s=n-m

Nun ziehst Du ein Element per Zufallsgenerator aus Deinem Puffer.
Nun ziehst Du einen zufälligen Indexwert i zum Puffer.
Steht dort eine Null, wird die Null entnommen und die Anzahl der Nullen 
verringert und die Pufferlänge verkürzt:
s=s-1 und r=r-1.
Steht dort eine Eins, wird die Eins entnommen und die Anzahl der Einsen 
verringert und die Pufferlänge verkürzt:
r=r-1
Das geht solange bis der Puffer leer ist, bzw. das letzte Element, das 
ja bekannt ist, gezogen werden muss.

Beispiel:
n=5 (Array ist 5 Elemente lang)
p=3 (3 Nullen).

Dann ist r=5 und s=3.
Gedanklich bilden wir den Puffer 00011.
Wir indexieren von 1 bis n, bzw. 1 bis r.

Erster Zufallswert aus dem Intervall [1;r=5] ist der Index 2.
Da 2 <=s=3 ist, haben wir die zweite Null gezogen.
Das Ergebnisarray hat als erstes Element also die Null.
Nun schrumpfen wir den Puffer um eine Null:
r=r-1 also ist r=4 und s=s-1=2
Der Puffer sieht jetzt so aus:
0 011, also 0011.

Wir ziehen jetzt den Index 4 aus dem Intervall [1;r=4]
4>s=2 also haben wir eine 1 gezogen.
Ergebnisarray: 01

Wir schrumpfen den Puffer:
001_ = 001
r=3 und s hat sich nicht verändert.

Wir ziehen jetzt den Index 2 aus dem Intervall [1;r=3]
2<=s=2 also haben wir eine 0 gezogen.
Ergebnisarray: 010

Wir schrumpfen den Puffer:
0_1 = 01

Wir ziehen jetzt den Index 2 aus dem Intervall [1;r=2]
2<=s=2 also haben wir eine 1 gezogen.
Ergebnisarray: 0101

Wir schrumpfen den Puffer:
0_ = 0

Der letzte Wert ist eine Null, wir brauchen dafür keine Zufallszahl zu 
berechnen.

Ist es das, was Du brauchst?

: Bearbeitet durch User
Autor: Theor (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> [...]

Danke für Deine Antwort.

Wenn ich Dich recht verstehe, sind wir wohl im wesentlichen einer 
Meinung.

Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die rand-Funktion hat einen miesen Ruf, da sie in vielen 
Implementationen in den unteren Bits nur sehr wenig Zufall hat (kurze 
Periode).  Aus der Linux-Man-Page von rand(3):
       The versions of rand() and srand() in the Linux C  Library
       use  the  same  random  number  generator as random(3) and
       srandom(3), so the lower-order bits should be as random as
       the higher-order bits.  However, on older rand() implemen‐
       tations, and on current implementations on different  sys‐
       tems,  the  lower-order bits are much less random than the
       higher-order bits.  Do not use this function  in  applica‐
       tions  intended  to  be  portable  when good randomness is
       needed.  (Use random(3) instead.)

Ich brauchte auch mal Zufallbits für "graue" Bilder und war erschrocken, 
wie regelmäßig die Bits waren (mod 2, wie oben), die aus rand(3) 
rauskamen - als Rauschmuster vollkommen ungeeignet.  (Das war zu nem 
Zeitpunkt, wo der Hinweis, dass jetzt random(3) benutzt wird, noch nicht 
drin war ;-) )

Was hängengeblieben ist: Finger weg von rand(3), wenn's gar nicht anders 
geht, dann die höchsten Bits nehmen.  Besser ist aber immer random(3).

Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ja, die Verteilung bzw. der Algorithmus der rand-Funktion ist nicht
> spezifiziert.

Posix liefert eine Beispielimplementation, die leider den Weg in 
genügend Libraries gefunden hat:
           static unsigned long next = 1;

           /* RAND_MAX assumed to be 32767 */
           int rand(void) {
               next = next * 1103515245 + 12345;
               return((unsigned)(next/65536) % 32768);
           }

           void srand(unsigned seed) {
               next = seed;
           }

Das ist der Algorithmus, von dem man bei rand(3) ausgehen muß.  Wenn ein 
spezielles System nen besseren hat - Glück gehabt ;-)

Autor: Hannes J. (pnuebergang)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Oh je, geht das hier alles ein bisschen durcheinander.

Zuerst mal zu rand(). Wie jemand schon schrieb gibt es klassische 
Implementierungen die das Problem haben, dass das LSB (das letzte Bit, 
das man mit % 2 oder & 1 erhält) nicht so gleichmäßig verteilt ist, wie 
man es gerne hätte. Das ist altbekannt.

Der Workaround, wenn man wirklich nichts besseres als rand() hat, ist 
ebenso alt. Statt dem LSB das MSB nehmen. Dabei gibt es eine Bedingung. 
Das MSB nehmen setzt voraus das RAND_MAX eine Zahl (2^N - 1) ist, d.h. 
RAND_MAX | (RAND_MAX >> 1) == RAND_MAX.

Dann das MSB nehmen bedeutet, man unterteilt den Wertebereich [0, 
RAND_MAX] in zwei Bereiche [0, int(RAND_MAX >> 1)] und [int(RAND_MAX >> 
1) + 1, RAND_MAX]. Jedes Intervall hat gleich viel Werte, da RAND_MAX 
ungerade ist plus die 0, und man schaut über das MSB nach, in welchem 
Bereich man liegt.

Die Maske zum Testen des MSB ist RAND_MAX ^ (RAND_MAX >> 1), und damit 
erhält man die gewünschten Werte als !!(rand() & (RAND_MAX ^ (RAND_MAX 
>> 1)))

Wenn RAND_MAX nicht 2^N - 1 ist, dann ist ein anderer Workaround rand() 
/ ((RAND_MAX >> 1) + 1). ABER, der Workaround funktioniert nur, wenn 
RAND_MAX wenigstens ungerade ist. Ist RAND_MAX gerade, lässt sich der 
Wertebereich nicht in zwei gleich große Intervalle teilen.

Daher sollte man rand() wirklich nur nehmen wenn man nichts Besseres hat 
oder wenn es nicht so genau drauf an kommt.

Zur Erzeugung anderer Verteilungen als Gleichverteilungen mittels 
gleichverteilter Zufallszahlen:

Das Verfahren nennt sich Inversionsmethode. Leider haben sich beim 
entsprechenden Wikipedia-Artikel 
https://de.wikipedia.org/wiki/Inversionsmethode mal wieder Mathematiker 
ausgetobt um das  allgemeine Verfahren so unverständlich wie möglich zu 
beschreiben.

Das konkrete Beispiel 
(https://de.wikipedia.org/wiki/Inversionsmethode#Beispiel_einer_Verteilung_mit_zwei_Werten) 
einer 75%:25% Verteilung ist allerdings noch lesbar. Es zeigt das 
Prinzip, das man ebenso zur Erzeugung der hier gesuchten 90%:10% 
Verteilung anwenden kann. Im Beispiel werden allerdings keine 
Integer-Zahlen verwendet. Das dortige Intervall [0, 1] enthält unendlich 
viele Werte.

Autor: Theor (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hannes J. schrieb:
> Oh je, geht das hier alles ein bisschen durcheinander.
>
> [...]

Ja. Es ist noch schlimmer, als ich dachte.

Ich kann nicht einmal eine Bestätigung dafür finden, dass POSIX eine 
bestimmte Verteilung für rand() vorschreibt. 
https://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html

Ich ziehe diese, meine obige Behauptung also, - mit Bedauern -, zurück. 
Ich habe nicht genügend recherchiert.


Aber in C++ gibts ja nun <std::...> Das hilft schonmal weiter. :-)

Autor: Operator S. (smkr)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Felix schrieb:
> Damit meine
> ich, dass z.B. ein Array mit nur 1en genau so wahrscheinlich ist wie ein
> Array mit nur 0en und natürlich alles dazwischen.

Bei rand() wird ein Array von nur 1en genauso wahrscheinlich sein, wie 
das von nur 0en. Die Wahrscheinlichkeit, dass das passiert ist aber sehr 
klein.

Kleines Rechenbeispiel:
Annahme, dass eine 1 kommt ist 50%
Bei einem Array der Länge 10, hätte man damit bereits eine 
Wahrscheinlichkeit von nur 0.1%, dass das gesamte Array eine 1 
beinhaltet.
Nun, ich kenne deine Arraylänge nicht, aber besser werden die Chancen 
nicht.

https://www.wolframalpha.com/input/?i=binomial+distribution+10+0.5

Hier kannst du einmal etwas mit deinen Zahlen spielen. Wie du in der 
untersten Tabelle siehst, liegt die Wahrscheinlichkeit, dass mindestens 
eine Zahl anders ist, bei 99.9%.

Hast du aber nicht 10 sondern 100 oder 1000 Zahlen in deinem Array, ist 
die Wahrscheinlichkeit, dass du irgendwo zwischen 40 und 60 landest 
immer grösser.

Autor: Oliver S. (oliverso)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Wenn du zum testen ein „zufälliges“ Array mit 10% 1 oder 0 brauchst, 
dann füll dein Array komplett mit 1/0, und wähle dann 10 zufällige 
Positionen für 0/1.

Oliver

Autor: ecm (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
#include <algorithm>
#include <array>
#include <iostream>
#include <random>

int main() {
  std::random_device rd;
  std::mt19937 gen(rd());
  std::array<int, 100> result;
  std::uniform_int_distribution<> dis(0, result.size());

  int ones = dis(gen);
  result.fill(0);
  std::fill_n(result.begin(), ones, 1);
  std::shuffle(result.begin(), result.end(), gen);

  for (const auto &x : result)
    std::cout << " " << x;
  std::cout << std::endl;
}

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.