Zufallswert mit Maximum aus 8-Bit Zufallswert ohne Bias

  • Allgemein

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

    Zufallswert mit Maximum aus 8-Bit Zufallswert ohne Bias

    Ich suche nach einer möglichst simplen Möglichkeit, aus einem 8-Bit Zufallswert (Normalverteilung zwischen inklusive 0 und 255) einen anderen (auch 8-Bit) Zufallswert zwischen inklusive 0 und einem (inklusiven oder exklusiven) Maximum zu errechnen.
    In .NET hat man typischerweise die Random-Klasse. Die kann das natürlich schon. Bzw. wenn man es selber machen will, kann die Random-Klasse auch einen Gleitkommawert zwischen inklusive 0 und exklusive 1 generieren:

    VB.NET-Quellcode

    1. Function Random(MaxExclusive As Byte) As Byte
    2. 'Rnd = Instanz von Random
    3. Return CByte(Rnd.NextDouble * MaxExclusive)
    4. End Function

    Aber ich habe keine Random-Klasse und auch keine Gleitkommazahlen.
    Ich habe nur ein Byte zwischen inklusive 0 und 255.

    Der Triviale Ansatz wäre, Modulo zu verwenden:

    VB.NET-Quellcode

    1. Function Random(MaxExclusive As Byte) As Byte
    2. 'Rnd = Byte zwischen 0 und 255
    3. Return Rnd Mod MaxExclusive
    4. End Function

    Aber im Fall, dass 256 nicht restlos durch MaxExclusive teilbar ist, haben manche Zahlen eine größere Chance (und das nennt sich Bias).
    Wie hier gezeigt mit Mod 126:

    Die Zahlen 0 bis 3 können durch je 3 verschiedene Zahlen errechnet werden (0 bis 3, 126 bis 129 und 252 bis 255), die übrigen Zahlen 4 bis 125 können jedoch nur durch je 2 verschiedene Zahlen errechnet werden.

    Ich suche deshalb nach einer möglichst einfachen Methode, die vorzugsweise ohne Modulo-Operator und mit generell möglichst wenig Operationen.

    PS:
    Klarheitshalbe möchte ich erklären: Es geht nicht um VB. Ich verwende den VB-Code nur, um zu erklären, was ich meine.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Kannst du dann nicht einfach MaxExclusive runter rechnen bis es ein vielfaches von 256 ist ?
    Im Sinne vonr ​maxE = floor(256/maxE) * maxE
    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

    @Plexian
    Ich bin mir nicht 100%-ig sicher, wie mir das hilft.

    @~blaze~
    Eine zweite Zufallszahl (ebenfalls zwischen inklusive 0 und 255) zu erhalten ist kein Problem.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    @3daycliff
    Das funktioniert fast. Ich hab mir mal angesehen, was da raus kommt:

    Bei Max = 0 oder 1 kommt immer 0 raus.
    OK so.

    Bei Max = 2:
    Rnd = 0 bis 127 ergibt 0 (128 Möglichkeiten)
    Rnd = 128 bis 255 ergibt 1 (128 Möglichkeiten)
    Auch OK so.

    Aber bei Max = 3:
    Rnd = 0 bis 85 ergibt 0 (86 Möglichkeiten)
    Rnd = 86 bis 170 ergibt 1 (85 Möglichkeiten)
    Rnd = 171 bis 255 ergibt 2 (85 Möglichkeiten)
    0 hat also eine etwas höhere Wahrscheinlichkeit. Nicht viel höher, aber doch höher.

    Das gleiche für Max = 255:
    Rnd = 0 ergibt 0
    Alle anderen Rnd > 0 ergeben Rnd - 1
    D.h. alle Zahlen von 1 bis 254 haben die gleiche Wahrscheinlichkeit, aber 0 hat eine doppelt so hohe.


    Edit:
    @~blaze~
    Die Hardware ist stark limitiert. In einem 8-Bit Register wird eine Zufallszahl generiert. Und es gibt keinen Hardware-Multiplizierer, das heißt ich muss einen Faktor so oft mit sich selbst addieren, wie vom zweiten Faktor angegeben. Ähnlich beim Dividieren und Modulo. *hust* Relay Computer *hust*
    "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“ ()

    Du wolltest eine einfache Lösung.
    Der erste Code im Startpost hat ja das gleiche Problem, falls 256 % max != 0. Fraglich ist ja auch, ob sich das bemerkbar macht bzw. die random-Funktion überhaupt "gute" Werte liefert.

    Dann kann ich nur noch eine nicht mehr ganz so einfache Funktion anbieten; wie immer ungetestet:

    C-Quellcode

    1. u = 256 - (256 % max);
    2. do { r = rand(); } while(r >= u);
    3. return r % max;


    PS: Wieso ist 0 bei max = 0 "OK"? Wenn das Maximum exklusive ist, dann ist die Menge des ganzzahligen halboffenen Intervalls [0,0) leer. Da ist das Ergebnis doch gar nicht definiert, oder?

    Edit: Das mit der Schleife funktioniert natürlich nur, wenn deine Zufallszahlen (rand()) gleichverteilt sind. Nur weil du was wegen Normalverteilung geschrieben hattest...

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „3daycliff“ ()

    Meine Lösung wäre jetzt Folgendes gewesen:
    Gehe alle Bits i beginnend beim höchsten (das niedrigste Bit ist i = 0) von max durch (wenn max > 255, erzeuge jeweils Zufallszahlen, die zumindest i Bits haben). Ist das Bit gesetzt, erzeuge eine neue Zufallszahl, deren Wertebereich von 0 bis 2^i - 1 (= (1 << i) - 1) geht (siehe unten) und addiere dies dem Resultat auf.
    Zufallszahlen mit n Bits kannst du wie folgt erzeugen: Erzeuge n/8 Zufallszahlen mit 8 Bit und eine Zufallszahl mit 8 Bits und shifte diese um 8 - n mod 8 nach rechts.

    Edit: Jetzt bin ich mir grad nicht mehr ganz sicher, ob das stimmt. Wenn du aber den Wertebereich der Zufallszahl auf 2^i oder 0 einschränkst (d.h. (result |= Zufallszahl >> 7) << i)), solltest du auf ein gutes Resultat kommen. Das lässt sich auch nochmal optimieren, indem du einfach 4 Zufallszahlen erzeugst und jeweils das i-te Bit rausziehst, wenn es sowohl im ursprünglichen Wert gesetzt ist, als auch in der Zufallszahl, also ggf. max & zufallszahl. Jetzt bin ich total verunsichert, ob der Algorithmus so passt... :P Vielleicht sollte ich die nächsten Tage mehr schlafen und danach nochmal drüberschauen.

    @ErfinderDesRades : Das Problem ist, dass er eine Zufallszahl mit Werten von 0 bis n erzeugen will. Wenn er jetzt zufallszahl % max wählt, ist der Wertebereich zwar auf max beschränkt, aber es ergibt sich folgendes Problem:
    Wenn max = 50 und das Maximum der Zufallszahl 255, dann wäre 255 mod 50 = 5. D.h. aber, dass die Werte von 0 bis 5 häufiger auftreten, als die restlichen Werte.

    Viele Grüße
    ~blaze~

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „~blaze~“ ()

    Niko Ortner schrieb:

    einen anderen (auch 8-Bit) Zufallswert
    Falls Du eien andere Verteilung brauchst, kannst Du das über einen Tabellenzugriff machen.
    Input: Gleichverteilung, Output: z.B. Exponentialverteilung.
    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!

    @3daycliff
    Einfach, aber korrekt soll die Lösung sein. Deshalb möchte ich den im Startpost gezeigten Code nicht verwenden.
    Dass bei Random(0) 0 raus kommt, ist egal. Es ist kein sinnvoller Wert, aber es ist egal. Denn als Verwender der Funktion muss man selbst wissen, dass 0 als MaxExclusive ungültig ist. Und dann darf man auch nicht erwarten, dass die Funktion gültige Werte zurückgibt, wenn man ungültige Parameter angibt. Ich könnte auch "einen Fehler auslösen". Ist nur eine Abfrage, ob MaxExclusive 0 ist.
    Den Code schau ich mir später an.

    @~blaze~
    Da Du geschrieben hast "wenn max > 255" möchte ich nochmal erklären: Es geht nur um Bytes. Das heißt, MaxExclusive kann nur 0 bis 255 sein (um eine Zufallszahl von 0 bis 255 zu bekommen, kann man direkt vom Register lesen).
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Jo, ist ja klar. Ich habe nur von einem verallgemeinerten Prinzip geredet. Ich glaube übrigens, dass das erste Verfahren richtig ist:

    ~blaze~ schrieb:

    Gehe alle Bits i beginnend beim höchsten (das niedrigste Bit ist i = 0) von max durch (wenn max > 255, erzeuge jeweils Zufallszahlen, die zumindest i Bits haben). Ist das Bit gesetzt, erzeuge eine neue Zufallszahl, deren Wertebereich von 0 bis 2^i - 1 (= (1 << i) - 1) geht (siehe unten) und addiere dies dem Resultat auf.
    Zufallszahlen mit n Bits kannst du wie folgt erzeugen: Erzeuge n/8 Zufallszahlen mit 8 Bit und eine Zufallszahl mit 8 Bits und shifte diese um 8 - n mod 8 nach rechts.

    Nur würde ich statt Addition ein Exklusives Oder verwenden.

    Viele Grüße
    ~blaze~

    Kannst du nicht einen zufalls-float mit beliebig vielen Nachkommastellen generieren und dann (via IEEE754) aus der Mantisse mit einer &-Verknüpfung deine Zufallszahlen schneiden? Geht dann natürlich nur für Zahlen mit 2er-Exponent-Grenzen. Baut darauf auf, dass die Mantisse komplett random ist (was ich nicht genau weiß, aber ich denke mal es ist so).

    Edit: Oh, sehe gerade, dass du keine floats hast. nvm..
    Von meinem iPhone gesendet

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

    Bei 2er-Potenzen das sowieso trivial: Gesetztes Bit ermitteln, 1 abziehen und mit einer Zufallszahl verunden. Bei Nicht-2er-Potenzen müsste man das halt nicht nur für das eine gesetzte Bit durchführen, sondern für die restlichen gesetzten Bits auch. Addition passt glaub ich doch... -.- Weißt was, probier's einfach aus.

    Viele Grüße
    ~blaze~

    @~blaze~
    So wie ich das verstanden habe (VB-Code zum Testen):

    VB.NET-Quellcode

    1. Dim Rnd As New Random
    2. Private Function FooRandom(MaxInclusive As Byte) As Byte
    3. Dim Result As Byte = 0
    4. For i = 7 To 0 Step -1
    5. If ((MaxInclusive >> i) And 1) <> 0 Then
    6. 'Result += CByte(Rnd.Next(0, 256) And ((1 << i) - 1))
    7. 'Kommt aufs gleiche:
    8. Result += CByte(Rnd.Next(0, 1 << i))
    9. End If
    10. Next
    11. Return Result
    12. End Function

    Nun... da kommen überwiegend Normalverteilungen heraus (bzw. annähernd):

    Ganz links ist 0, ganz rechts 255. Als MaxExclusive habe ich hier 255 angegeben (und es wurden 2^19 Zufallszahlen berechnet), aber auch bei anderen Zahlen sieht es so aus.
    Noch ein Beispiel mit 87 als Maximum:

    Normalverteilungen kommen nur dann raus, wenn MaxInclusive 2^x ist, denn dann ist nur ein Bit gesetzt und es wird auch nur eine (normalverteilte) Zufallszahl generiert.

    @3daycliff
    Der von Dir gezeigte Code funktioniert, verwendet aber gleich 2 Mal Modulo.
    Und ich habe das Problem, dass ich nicht verstehe, was der Code macht. Ich verstehe, welche Befehle ausgeführt werden und so, aber ich verstehe nicht was es bewirkt.
    Deshalb wäre es toll, wenn Du er mir erklären könntest.

    @Mono
    Das Problem dabe ist: Wenn das Maximum recht klein ist, werden sehr viele Zahlen generiert, die größer als das Maximum ist. Das kann dann eine Weile dauern.
    Extremfall:

    VB.NET-Quellcode

    1. MaxExclusive = 2 '0 oder 1 kann raus kommen
    2. Do
    3. Result = Rnd.Next(0, 256) 'Die meisten Zahlen sind größer als MaxExclusive
    4. Loop Until Result < MaxExclusive
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Niko Ortner schrieb:

    ich habe das Problem, dass ich nicht verstehe, was der Code macht.
    Ich bin zwar nicht 3daycliff, aber ich hoffe, ich das richtig interpretiert:
    Er erzeugt so lange eine Zufallszahl, bis der Wert in einem Non-Bias-Bereich liegt.
    Wenn dein Max bei 50 liegt, ignoriert er alle Zahlen, die oberhalb 250 liegen.

    Niko Ortner schrieb:

    verwendet aber gleich 2 Mal Modulo
    Ist deine Ziel-Plattform so unperformant, dass das ein Problem ist?
    --
    If Not Program.isWorking Then Code.Debug Else Code.DoNotTouch
    --

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

    Die Idee ist einfach, dass ich das, was deinen Bias erzeugen könnte, vorher entferne.
    Das funktioniert aber, nur wenn In- und Output jeweils gleichverteilt sind.

    Beispiel aus dem Startpost: Deine obere Grenze ist 126.
    u = 256 - (256 % max); berechnet das Größte Vielfache von 126, was aber noch kleiner als 256 ist.
    Mit do { r = rand(); } while(r >= u); wird dann eine Zufallszahl gesucht, die kleiner als das eben ermittelt Vielfache ist und damit dann keine Artefakte bei der einfachen Modulo-Operation return r % max; erzeugt.
    Zurück zum Beispiel: Der Algorithmus zieht also eine neue Zufallszahl, falls die vorherige 252, 253, ... oder 255 war. Hoffnung ist, dass die Übrigen gleichverteilt sind und so das Ergebnis auch wieder gleichverteilt ist.
    Im Prinzip also das was Mono vorgeschlagen hat, nur dass ich Vielfache ausnutze um dein im letzten Post erwähntes Problem zu umgehen.

    Edit: @Mono jo

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „3daycliff“ ()

Facebook
Telefonspende