Random Int ohne duplicates

  • C#
  • .NET (FX) 1.0–2.0

Es gibt 28 Antworten in diesem Thema. Der letzte Beitrag () ist von Niko Ortner.

    Wenn die Bedingungen im obigen Quelltext erfüllt sind, dann ja: Siehe Hull-Dobell Theorem.
    Die Werte für Modulo, Inkrement und Faktor habe ich jetzt von Wikipedia kopiert, die wohl in der C++ Spezifikation stehen. Sollten eigentlich passen, wenn ich keinen Zahlendreher drin habe.
    Da m eine 2er-Potenz ist, lassen sich die Aussagen ja leicht überprüfen...

    Siehe auch deutsche Wikipedia:
    de.wikipedia.org/w/index.php?t…390293#Periodenl.C3.A4nge

    Also, wir haben: $m = 2^{31}, a = 1103515245, b = 12345$.

    1) $m$ ist eine 2er-Potenz und $b$ ist ungerade, also sind die beiden offensichtlich teilerfremd

    2) da $m$ eine 2er-Potenz ist, hat es nur einen Primfaktor: 2. $a-1$ ist gerade, insbesondere also auch durch 2 teilbar und damit stimmt die zweite Aussage ("Jeder Primfaktor von $m$ teil $a-1$")

    3) $m = 2^{31} = 4 * 2^{29}$, also ist $m$ durch vier teilbar, wie auch auch $a-1 = 1103515244$.


    Laut Theroem erreicht der LCG damit volle Periodenlänge
    $m$
    und:
    In diesem Fall erzeugt der Generator jede Zahl von 0 bis $m-1$ genau einmal und beginnt dann wieder von vorn. Er liefert also eine pseudozufällige Permutation dieser Zahlen. Der Startwert $y_1$ kann dann jede Zahl aus dieser Menge sein.
    "

    Es sei dann ich habe etwas übersehen, was ich natürlich nicht ausschließen möchte.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „3daycliff“ () aus folgendem Grund: Typo bei 1)

    Sm? SmS? Wird bei dir der LaTeX-Code nicht richtig angezeigt?

    Hier noch mal ohne:
    Siehe auch deutsche Wikipedia:
    de.wikipedia.org/w/index.php?t…390293#Periodenl.C3.A4nge

    Also, wir haben: m = 2^31, a = 1103515245, b = 12345.
    1) m ist eine 2er-Potenz und b ist ungerade, also sind die beiden offensichtlich teilerfremd
    2) da m eine 2er-Potenz ist, hat es nur einen Primfaktor: 2. a-1 ist gerade, insbesondere also auch durch 2 teilbar und damit stimmt die zweite Aussage ("Jeder Primfaktor von m teil a-1")
    3) m = 2^31 = 4 * 2^29, also ist m durch vier teilbar, wie auch auch a-1 = 1103515244.

    Laut Theroem erreicht der LCG damit volle Periodenlänge m und:
    In diesem Fall erzeugt der Generator jede Zahl von 0 bis m-1 genau einmal und beginnt dann wieder von vorn. Er liefert also eine pseudozufällige Permutation dieser Zahlen. Der Startwert y_1 kann dann jede Zahl aus dieser Menge sein."

    Es sei dann ich habe etwas übersehen, was ich natürlich nicht ausschließen möchte.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „3daycliff“ () aus folgendem Grund: Typo bei 1)

    @blaze
    Das hatte ich ja auch nicht geschrieben.
    Aber da 2^31 nun mal nur den Primfaktor 2 hat und die andere Zahl ungerade ist, sind sie definitiv teilerfremd.
    Die Skeptiker können ja bei WolframAlpha einfach gcd(2^31, 12345) eingeben und sich die Definition von Teilerfremd anschauen...

    Ich weiß nicht genau, wie sich die Wahl von a b auf die Qualität der Zufallszahlen auswirkt, daher sollte man vielleicht nicht unbedingt irgendeine (Prim-)Zahl nehmen. Keine Ahnung ob b=12345 die perfekte Wahl ist, da sie aber von der glibc verwendet wird, ist sie vermutlich wohl nicht die schlechteste.

    3daycliff schrieb:

    auf die Qualität der Zufallszahlen
    wirkt sich b nicht aus, aber auf die Reihenfolge der generierten Zahlen, und das würde ich nicht "Qualität" nennen wollen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich hab mir nie angesehen, wie zufällig die Zahlen verteilt sind, wenn man das hier macht:
    ericlippert.com/2013/11/14/a-p…-multiplicative-inverses/
    Zufällig genug? Denn das wäre eine äußerst effiziente Möglichkeit, bis zu einem Maximum an Zahlen, nicht-wiederholende Werte zu generieren.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Niko Ortner“ ()