Zufallswert mit Maximum aus 8-Bit Zufallswert ohne Bias

  • Allgemein

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

    @petaod
    Ist deine Ziel-Plattform so unperformant, dass das ein Problem ist?

    In Post #7, Niko Ortner schrieb:

    Die Hardware ist stark limitiert. [...] 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*


    @3daycliff
    berechnet einfach das Größte Vielfache von 126, was kleiner als 256 ist.

    Ahaaa! Jetzt hat's klick gemacht. Und das geht auch relativ einfach zu berechnen.
    Ok, ich bin dann mal am Basteln.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    <p>Es l&auml;sst sich keine Aussage treffen, wurde lange eine derartige Operation effektiv dauern wird, im schlimmsten Fall... Sehr sehr lange.</p>

    <p>Bei meinem Algorithmus ist das Problem, dass ich nicht beachtet habe, dass Additionen die Wahrscheinlichkeit nat&uuml;rlich gen Mitte verschiebt. Vielleicht setze ich mich echt nachher nochmal ran.</p>

    <p>Viele Gr&uuml;&szlig;e</p>

    <p>~blaze~</p>

    Niko Ortner schrieb:

    es gibt keinen Hardware-Multiplizierer
    Ist schon eine komische Prozessor-Architkektur.
    Random liegt in einem Register, aber Multiplikation ist nicht unterstützt.
    Wenn dem so ist, würde ich behaupten, dass Random einfach aus dem Tick-Counter entsteht und das ist bei kurz nacheinander abgesetzten Calls kein echter Zufall mehr.
    --
    If Not Program.isWorking Then Code.Debug Else Code.DoNotTouch
    --

    Ggf., aber es kann auch sein, dass weitere Faktoren einfließen.
    Ich schaffe es ehrlich gesagt im Moment auch nicht auf eine günstigere Verteilung, mit Xor stelle ich mich auch zu blöd an, der Wertebereich bleibt bei 0..63 statt 0..100, weil ich irgendeinen Blödsinn übersehe und gerade nicht wirklich Lust auf Programmierung habe. Du kannst ja mal schauen, dass du den Algorithmus, den du mit Addition geliefert hast, auf eine homogene Verteilung umschreibst. Sollte durch geschickte Operationen möglich sein. Wahrscheinlich müsste man einfach nur eine Abhängigkeit des (i+1). Bits vom i. Bit einführen.

    Viele Grüße
    ~blaze~

    So, jetzt grab ich hier nochmal rum.
    Da ich Multiplikation, Division und Modulo jetzt in Hardware implementiert habe (siehe hier) hab ich mich jetzt nochmal an die Zufallszahlen rangesetzt.
    Im Simulator werden die Zufallszahlen von 0 bis 255 von System.Random generiert. Also die haben kein Bias (das hab ich auch nochmal sicherheitshalber getestet).
    Division und Modulo funktionieren auch.
    Ich hab mich für die Methode von 3daycliff entschieden und die mal testweise implementiert. Den Code hab ich mal angehängt. Ist etwas vereinfacht und ich habe mich bemüht, grob mit Kommentaren zu erklären, was passiert.
    Spoiler anzeigen

    Die Calling Convention ist wie folgt:
    1. Platz für Return-Wert(e) auf dem Stack reservieren (einfach irgendwas pushen)
    2. Argumente auf den Stack legen
    3. Call an Methode
    4. In der Methode kann man dann beginnend bei Frame[0] lokale Variablen auf dem Stack reservieren.
    5. Auf Argumente und Return-Werte kann bei Frame[-5] und abwärts zugegriffen werden, also bei 1 Byte Return-Wert und 4 Bytes an Argumenten liegt der Return-Wert bei Frame[-9] und die Argumente in der Reihenfolgen, in der sie auf den Stack gelegt wurden, bei Frame[-8] bis Frame[-5]. Hinweis: negative Offsets werden ins Zweierkompliment überführt und in 2 Bytes aufgeteilt (das höherwertige zuerst). Also mit Frame[Const] = C; 255; 251 ist Frame[-5] gemeint. @Label fügt die Adresse des Labels in den Code ein. Also nach Call Const folgt die Adresse der Methode, zu der gesprungen wird.
    6. Return
    7. Argumente vom Stack entfernen
    8. Return-Wert(e) vom Stack entfernen und verwenden

    VB.NET-Quellcode

    1. Lab Main
    3. 'Eingang 0 ist MaxExclusive
    4. Push C 'Platz für Return-Wert
    5. C = I0
    6. Push C '1.Argument
    7. Call Const
    8. @System_Random_Byte__Byte
    9. Pop C '1. Argument entfernen
    10. Pop C 'Return-Wert entfernen ...
    11. O0 = C 'und verwenden
    13. Goto Absolute Const
    14. @Main
    16. 'Äquivalent in ~VB
    17. Public Function Random(MaxExclusive As Byte) As Byte
    18. Dim BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256 As UInt16 = 256 - (256 Mod MaxExclusive)
    19. Dim RandomNumber As Byte
    20. Do
    21. RandomNumber = Rnd
    22. Loop Until RandomNumber < BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256
    23. Return RandomNumber Mod MaxExclusive
    24. End Function
    26. ' -5 -6
    27. 'Public Function Random(MaxExclusive As Byte) As Byte
    28. Lab System_Random_Byte__Byte
    30. 'Dim BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256 As UInt16
    31. '2 Bytes @ 0
    32. 'Dim RandomNumber As Byte
    33. '1 Byte @ 2
    34. SP += Const
    35. 3
    37. 'BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256 = 256 - (256 Mod MaxExclusive))
    38. '256 Mod MaxExclusive
    39. 'G-Register sind für Multiplikation, Division und Modulo zuständig.
    40. '256 = (1 << 8) | 0
    41. C = Const
    42. 1
    43. GA1 = C
    44. C = Const
    45. 0
    46. GA0 = C
    47. C = Frame[Const] 'MaxExclusive
    48. 255
    49. 251
    50. GB = C
    51. GD = GA Mod GB
    53. '256 - ...
    54. C = Const
    55. 1
    56. F1 = C
    57. C = Const
    58. 0
    59. F0 = C
    60. '1-er Kompliment von (256 Mod MaxExclusive)
    61. C = GD
    62. A = C
    63. C = Not A
    64. E0 = C
    65. C = Const
    66. 255
    67. E1 = C
    68. 'A - B = A + !B + 1
    69. F += E
    70. F += Const
    71. 0
    72. 1
    73. C = F1
    74. Frame[Const] = C
    75. 0
    76. 0
    77. C = F0
    78. Frame[Const] = C
    79. 0
    80. 1
    82. 'Do
    83. Lab System_Random_Byte__Byte_Do1_Head
    85. 'RandomNumber = Rnd
    86. C = Rnd
    87. Frame[Const] = C
    88. 0
    89. 2
    91. 'Loop Until RandomNumber < BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256
    92. 'Kleiner-Als-Operator ist ein Aufruf, da in Hardware nur 8-Bit Vergleiche implementiert sind.
    93. Push C
    94. C = Const 'RandomNumber mit 0-en auf 16 Bits erweitern.
    95. 0
    96. Push C
    97. C = Frame[Const]
    98. 0
    99. 2
    100. Push C
    101. C = Frame[Const]
    102. 0
    103. 0
    104. Push C
    105. C = Frame[Const]
    106. 0
    107. 1
    108. Push C
    109. Call Const
    110. @System_Word_LessThan_Word_Word__Boolean
    111. SP += Const
    112. 255
    113. 252
    114. Pop C
    115. If C = 0 Then Goto 'Wenn C = 0, dann hat der Operator False zurückgegeben, dann muss wiederholt werden.
    116. @System_Random_Byte__Byte_Do1_Head
    118. 'Return Result Mod MaxExclusive
    119. C = Const
    120. 0
    121. GA1 = C
    122. C = Frame[Const]
    123. 0
    124. 2
    125. GA0 = C
    126. C = Frame[Const] 'MaxExclusive
    127. 255
    128. 251
    129. GB = C
    130. GD = GA Mod GB
    131. C = GD
    132. Frame[Const] = C 'Return-Wert
    133. 255
    134. 250
    135. Return
    136. 'End Function
    138. ' -8 -7 -6 -5 -9
    139. 'Public Operator <(Left As UInt16, Right As UInt16) As Boolean
    140. Lab System_Word_LessThan_Word_Word__Boolean
    141. 'If Left.HighByte < Right.HighByte Then
    142. C = Frame[Const]
    143. 255
    144. 248
    145. A = C
    146. C = Frame[Const]
    147. 255
    148. 250
    149. B = C
    150. C = A < B
    151. If C = 0 Then Goto
    152. @System_Word_LessThan_Word_Word__Boolean_If1_End
    154. 'Return True
    155. C = Const
    156. 255
    157. Frame[Const] = C 'Return-Wert
    158. 255
    159. 247
    160. Return
    162. 'End If
    163. Lab System_Word_LessThan_Word_Word__Boolean_If1_End
    165. 'If Left.HighByte > Right.HighByte Then
    166. C = A > B
    167. If C = 0 Then Goto
    168. @System_Word_LessThan_Word_Word__Boolean_If2_End
    170. 'Return False
    171. C = Const
    172. 0
    173. Frame[Const] = C 'Return-Wert
    174. 255
    175. 247
    176. Return
    178. 'End If
    179. Lab System_Word_LessThan_Word_Word__Boolean_If2_End
    181. 'Return Left.LowByte < Right.LowByte
    182. C = Frame[Const]
    183. 255
    184. 249
    185. A = C
    186. C = Frame[Const]
    187. 255
    188. 251
    189. B = C
    190. C = A < B
    191. Frame[Const] = C ''Return-Wert
    192. 255
    193. 247
    194. Return
    195. 'End Operator
    197. Lab EndOfCode

    Das Problem ist, dass trotzdem ein Bias vorhanden ist:
    MaxExclusive = 192

    MaxExclusive = 165

    MaxExclusive = 96

    Und ich komme einfach nicht drauf, wo das Problem liegt.


    Edit: Ach verdammt, ich hab den Fehler (bzw. einen, aber ich bin mir ziemlich sicher, dass das das Problem lösen wird) gefunden.
    Es war ein blöder Tippfehler. In der Random-Methode ganz am Anfang werden 3 Bytes auf dem Stack reserviert. Dazu wird der StackPointer einfach um 3 erhöht:

    VB.NET-Quellcode

    1. ' -5 -6
    2. 'Public Function Random(MaxExclusive As Byte) As Byte
    3. Lab System_Random_Byte__Byte
    5. 'Dim BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256 As UInt16
    6. '2 Bytes @ 0
    7. 'Dim RandomNumber As Byte
    8. '1 Byte @ 2
    9. SP += Const
    10. 3
    12. 'BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256 = 256 - (256 Mod MaxExclusive))
    13. '256 Mod MaxExclusive
    14. 'G-Register sind für Multiplikation, Division und Modulo zuständig.
    15. '256 = (1 << 8) | 0
    16. C = Const
    17. 1
    18. GA1 = C
    20. '...

    Da der StackPointer ein 16-Bit Wert ist, erwartet SP += Const auch 2 Bytes. Ich hab aber nur eines hingeschrieben. Korrekt müsste es so lauten:

    VB.NET-Quellcode

    1. ' -5 -6
    2. 'Public Function Random(MaxExclusive As Byte) As Byte
    3. Lab System_Random_Byte__Byte
    5. 'Dim BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256 As UInt16
    6. '2 Bytes @ 0
    7. 'Dim RandomNumber As Byte
    8. '1 Byte @ 2
    9. SP += Const
    10. 0 ' <--------------Hier!
    11. 3
    13. 'BiggestMultipleOfMaxExclusiveLessThanOrEqualTo256 = 256 - (256 Mod MaxExclusive))
    14. '256 Mod MaxExclusive
    15. 'G-Register sind für Multiplikation, Division und Modulo zuständig.
    16. '256 = (1 << 8) | 0
    17. C = Const
    18. 1
    19. GA1 = C
    21. '...

    Der StackPointer wurde um (3 << 8) | 36 = 804 statt um (0 << 8) | 3 = 3 erhöht (36 ist der C = Const-OpCode). Und der 1-er wurde ausgeführt (Nop).
    Das Testprogramm läuft noch aber soweit sieht's gut aus.


    Edit 2:
    Jup, läuft:

    Damit hat sich das erledigt.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

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