[Tiptoi] Random Generator

Di Jan 18 19:26:12 CET 2022

Hi,

Der im tttool-Buch vorgeschlagene Zufallsgenerator (T($r,65535) $rnd+=$r $rnd*=25173 $rnd+=13849) is doch auch ein LCG (scheinbar aus "Programming in Pascal" von Peter Grogono). Ok, hier wird in jedem Schritt zusätzlich noch ein Timer-Wert addiert, aber das kann man auch weglassen

Allerdings sollte wohl angemerkt sein, was auch im Wikipedia-Artikel zu "Mängeln" steht (https://de.wikipedia.org/wiki/Kongruenzgenerator#Mängel_der_erzeugten_Zahlen <https://de.wikipedia.org/wiki/Kongruenzgenerator#M%C3%A4ngel_der_erzeugten_Zahlen>), insb. "...ist es ungünstig, Zufallszahlen r_i in [0, k-1] durch r_i = y_i mod k zu gewinnen, wenn k und m [hier 2^16] nicht teilerfremd sind.". Genau dies wird im tttool-Buch aktuell ohne Warnung empfohlen.

Für Zufallszahlen r in [0, 255] funktioniert

seed:
 - T($r,65535) $rnd_state+=$r $rnd_state*=25173 $rnd_state+=13849

random:
  - $rnd_state*=25173 $rnd_state+=13849 $rnd=$rnd_state/256

wahrscheinlich deutlich besser (dies kann dann wieder mit $rnd_state % k auf den gewünschten Wertebereich [0, k-1] eingeschränkt werden). Ich kenn mich mit Pseudozufallszahlen aber auch nicht wirklich gut aus.

Gruß,
Michael

P.S., die von Dir gewählten Faktor-und Inkrement-Werte a=75 und b=1 widersprechen der Eigenschaft, die oft genannt wird, dass 4 ein Teiler von a-1 sein soll (da 4 ein Teiler vom Modul 2^16 ist), oder? Es wird so also nicht die volle Periodenlänge erzielt.

> On 18. Jan 2022, at 13:41, T. Kuhn via tiptoi <tiptoi at lists.nomeata.de> wrote:
> 
> Geschätzte Community
> 
> Ich arbeite seit kurzem mit eigenen TipToi Projekten. Danke für all die Vorarbeit, welche von Anderen geleistet wurde.
> In diesem Kontext brauchte ich Zufallszahlen. Mit der Variante aus dem tttool-Buch (S.38) war ich nicht sehr glücklich, da mathematisch die Analyse des Generators sehr schwierig ist, da das Timerverhalten für mich schwierig nachzuvollziehen war. Zudem konnte ich die Timerwerte reproduzieren, je nachdem wie schnell ich den Timer abrief. Die monoton steigenden Werte finde ich auch nicht optimal für einen Pseudo-Random-Generator, bin mir aber nicht sicher, wie tragisch die sind.
> 
> Ich habe nun einen eigenen pseudo-Zufallsgenerator gebaut. Es ist ein "Linear congruential generator" (siehe wikipedia: https://en.wikipedia.org/wiki/Linear_congruential_generator <https://en.wikipedia.org/wiki/Linear_congruential_generator>). Weil die Datenstruktur des Stiftes scheinbar nur unsigned 16bit Variablen zum rechnen benutzt, habe ich die Parameter dafür optimiert und über ein Programm, welches Millionen von Zahlen "Würfelt", getestet, ob über 10000 "Würfe" eine Periodizität sichtbar wird, und ob die Zahlen gleich häufig entstehen. 
> Als Seed-Wert habe ich über eine First-Call Struktur den Timer verwendet (wird nur beim ersten Wurf verwendet). Da diese Variante nur beim ersten Aufruf vom Timer abhängt, konnte ich die Funktionsweise und die Qualität auf einer externen Recheneinheit (also nicht auf dem Stift) überprüft werden.
> 
> Beispiel:
> 100'000 Würfe, 10 Zufallszahlen (0..9), Seed = 1658 (beliebig), a=75, c=1, m=65535 (Bezeichnungen gemäss Wikipedia Artikel zu Linear congruential generator).
> ergibt:
> Zufallszahl: Anzahl Erscheinungen über 100'000 Würfe
> 0: 9992 
> 1: 10015 
> 2: 9989 
> 3: 10012 
> 4: 10001 
> 5: 9998 
> 6: 9995 
> 7: 9984 (Minimal-Wert)
> 8: 10023 (Maximal-Wert)
> 9: 9991
> -> Maximaler Unterschied für diese Seed: 39 Werte (=0.039%)
> 
> Seed (Startwerrt) habe ich von 0 bis 1000 (realistische Timer Werte innerhalb 30'' nach Start des Stiftes) variiert. Max - Min von allen 1000 Seeds, nach 100'000 Würfen ist maximal 51 Werte. Das heisst, im ungünstigsten Fall erscheint eine Zufallszahl auf lange Sicht um 0.051% mehr als die anderen. Damit kann ich sehr gut leben :-).
> 
> Ergebnis:
> - Über 10'000 Würfe ist keine Periodizität ersichtlich.
> 
> - Über 100'000 Würfe für 3,5,6,7,9,10,11,13,14,15,17,18 und 19 Zufallszahlen ist der aufgetretene Unterschied in der Erscheinung der Zufallszahlen maximal 50 (<0.05%).
> 
> - Der Zufallsgenerator funktioniert nicht für eine Anzahl Zufallszahlen von (2,) 4,8,12,16,20,24,... (4er Reihe). Er liefert zwar schon Ergebnisse, aber diese sind sehr periodisch, uns gewisse Zufallszahlen treten gar nicht auf.
> Beispiel für 8 Zufallszahlen über 100'000 Würfe, Seed = 1658:
> 0: 0 
> 1: 0 
> 2: 25000 
> 3: 25000 
> 4: 0 
> 5: 0 
> 6: 25000 
> 7: 25000 
> Die Periode lautet: 7, 6, 3, 2 -> Die Zahlen kommen also immer in dieser Reihenfolge.
> 
> - Wenn man also 3,5,6,7,9,10,11,.. Zufallszahlen braucht, ist dieser Code hier meiner Meinung nach besser geeignet, da die Qualität des Pseudo-Random-Generators bewiesen ist.
> 
> Falls jemand diesen verwenden möchte, liegt das YAML File im Anhang
> 
> Freundliche Grüsse
> 
> Tom
> 
> <RandomTest.yaml>-- 
> tiptoi mailing list
> tiptoi at lists.nomeata.de
> https://lists.nomeata.de/mailman/listinfo/tiptoi

-------------- nächster Teil --------------
Ein Dateianhang mit HTML-Daten wurde abgetrennt...
URL: <https://lists.nomeata.de/pipermail/tiptoi/attachments/20220118/d7f368b8/attachment.htm>