Verbesserter Zufallsgenerator
von Günther Zivny
Elektronik-Labor
Projekte
Mikrocontroller PicoBasic
Ich habe mich etwas mit dem Zufallsgenerator
beschäftigt. Dazu habe ich die PicoBasic-Programme und ein paar andere
für den PC in Small Basic umgesetzt und die Ergebnisse dokumentiert:
Kainka Version 1
Die Zahlen wiederholen sich nach 32 Schritten (Startzahl 59), es kommen also nicht alle möglichen 256 Zahlen vor.
Die ursprüngliche Startzahl 59 kommt später nicht mehr vor! Durch die
anfängliche Shift-Operation fällt die vorderste Stelle weg, egal, ob es
eine 1 oder 0 ist. Somit folgt sowohl auf 59 als auch auf 187 jeweils
120.
Auffällige Muster konnte ich nicht erkennen, die Verteilung der Zahlen ist aber nicht ganz gleichmäßig.
Die Zykluslänge hängt von der Startzahl ab:
Startzahl 1 bzw. 129 -> Zykluslänge 69 Schritte
Startzahl 2 bzw. 130 -> Zykluslänge 69 Schritte
Startzahl 126 bzw. 254 -> Zykluslänge 10 Schritte
Generell tritt in einem Zyklus keine Zahl zweimal auf, weil beim
zweiten Auftreten der Zahl der Zyklus neu startet. Bei einem Würfel
kann dagegen die 6 mehrmals auftreten, ohne dass die folgenden Würfe
dadurch beeinflusst werden.
Kainka Version 2
Hier ist die Zykluslänge größer, aber bedingt durch die oben
beschriebene Eigenschaft (shift) nicht größer als 127. Die Zahlen sind
gut verteilt und zeigen kein Muster.
Eine sehr gute Lösung!
Linearer Kongruenzgenerator (Wikipedia/Zufallsgenerator)
Zum Beispiel:
L1:
A = 3*A +161
Goto L1
Die Zahlen wiederholen sich, siehe Diagramm. Die hinteren 4 Bits zeigen ein auffälliges Muster.
Oder noch einfacher:
L1:
A = A +161
Goto L1
Bei einem 8-Bit Rechner kommt jede Zahl zwischen 0 und 255 vor, weil
die vorderen Bits abgeschnitten werden. Die Zahlen sind gut verteilt,
zeigen aber ein auffälliges Muster, was je nach Anwendung nicht negativ
sein muss.
Doppelter Kongruenzgenerator
L1:
A = A +131
X = A*X + A
Goto L1
Hier kommen gleiche Zahlen mehrmals vor, ohne dass sich der Zyklus
wiederholt, die obige Aussage trifft also nicht zu (ein und dieselbe
Summe kann sich aus verschiedenen Summanden zusammensetzen). Die
hinteren Bits zeigen ein auffälliges Muster.
Doppelter Kongruenzgenerator, vereinfacht
L1:
A = A +131
X = X + A
Goto L1
Hier kommen alle Zahlen 0…255 einmal vor.
Umsetzung in PicoBasic (B.K.)
Herzlichen Dank, das ist die Lösung! Die vereinfachte
Version des doppelten Kongruenzgenerators ließ sich leicht in PicoBasic
umsetzen.
Statt X habe ich die Variable D verwendet. Und weil zweimal addiert
wird, mussten A und B mehrfach umkopiert werden. Aber jetzt
funktioniert es perfekt. Die LEDs blinken quasi zufällig, und man kann
keine Regelmäßigkeit erkennen.
REM Zufall3
REM G. Zivny
0x09FF Pdir = 255
L1:
0x0283 B = 131
0x2A00 A = A + B
0x3400 B = A
0x3900 A = D
0x2A00 A = A + B
0x4500 Pout = A
0x4200 Print A
0x3800 D = A
0x3500 A = B
0x1964 Delay ms = 100
0x2001 Goto L1:
Über Zufallsgeneratoren von Günther Zivny
Zufallsgeneratoren
haben die Aufgabe, eine Zahlenreihe zu erzeugen, wobei die jeweils folgende
Zahl nicht vorhersehbar sein soll. Etwas, was nicht vorhersehbar ist, nennen
wir Zufall. Bei einem Würfel ist jeder Wurf unabhängig von den vorhergehenden
Würfen, es handelt sich also um einen echten Zufallsgenerator.
Bei den auf
einem Schieberegister basierenden Zufallsgeneratoren ist dies nicht der Fall.
Auf jede Zahl folgt immer die gleiche nächste Zahl. Zudem wiederholt sich die
Zahlenreihe nach einer bestimmten Anzahl von Schritten und jede Zahl kommt
innerhalb eines solchen Zyklus nur einmal vor. Gegen Ende des Zyklus wird also
der Vorrat an möglichen Zahlen immer kleiner.
In der
Kryptographie hat das den Vorteil, dass der Empfänger in Kenntnis des Aufbaus
und der Startposition des Generators die Zahlen reproduzieren kann, die der
Sender zur Verschlüsselung der Nachricht verwendet hat und er somit die
Verschlüsselung rückgängig machen kann.
Die maximal
mögliche Zykluslänge hängt von der Länge des Schieberegisters ab. Bei einem
Schieberegister mit 8 Positionen erhält man eine maximale Zykluslänge von 2 hoch 8 - 1
= 255 Schritten, es werden also die Zahlen von 1 bis 255 (im Binärsystem)
hintereinander angeordnet, allerdings ohne eine sofort erkennbare Ordnung. Die
tatsächliche Länge hängt von der Art des Rückkopplungsnetzwerks ab.
Gescheite
Menschen haben auch herausgefunden, wie das Rückkopplungsnetzwerk beschaffen
sein muss, damit sich die maximale Zykluslänge ergibt.
Bild 1: Der
Zustand mit lauter Nullen ist nicht zulässig und wird ein Blockieren bewirken.
Die kapazitive Kopplung löst das Problem, weil dann dem Eingang eine „1“
zugeführt wird. Eine andere Möglichkeit ist, das Register mit einer von Null
verschiedenen Startsequenz vorzuladen.
Entnommen aus:
Don Lancaster, Das CMOS-Kochbuch, IWT-Verlag, ISBN 3-88322-002-7
Permutation
Eine
Zykluslänge von 256 Schritten ist eine ganze Menge, aber geht da noch mehr? Die
Frage ist, auf wie viele Arten man 256 verschiedene Zahlen hintereinander
schreiben kann, ohne dass sie sich wiederholen. Die Antwort ist überraschend.
Es gibt so viele Möglichkeiten, dass man diese Anzahl gar nicht mehr
aufschreiben kann! Wie man das
weiß? Nun, man nimmt erst mal eine ganz kleine Anzahl von Elementen und wenn
sich ein Schema erkennen lässt, kann man das hochrechnen.
Ein leicht
verständliches Schema ist folgendes:
Man nimmt 2
Elemente a und b. Diese kann man auf 2 verschiedene Arten anordnen:
ab und ba.
Nun nimmt man
ein drittes Element hinzu:
abc
Die hinteren 2
Elemente lassen sich auf die bekannte Art umdrehen. Nun ersetzt man b durch a
und erhält wieder 2 Permutationen. Schließlich ersetzt man c durch a und erhält
weitere 2 Permutationen, insgesamt also 3*2 = 6 Permutationen
abc -> acb
bac -> bca
cba -> cab
Das lässt sich
mit 4 Elementen fortsetzen:
abcd
Die hinteren 3
Elemente kann man auf 6 verschiedene Arten vertauschen und dann kann man noch
bcd jeweils durch a ersetzen, also insgesamt 4*3*2 = 24 Permutationen.
Viele Taschenrechner
haben für diese Rechnung eine eigene Taste: n! (lies: n Fakultät).
Damit kann man
nun sehr bequem ausrechnen, wie viele Permutationen es je nach Länge der
Zeichenkette gibt:
2! = 2
3! = 6
4! = 24
5! = 120 usw.
Die Fakultät
startet zunächst langsam, gibt dann aber Gas und schlägt jede Potenz.
Programm
Das schreit
natürlich nach einer Automatisierung. Ich habe versucht, das obige Schema in
der Programmiersprache Small Basic zu programmieren, habe es aber nicht
geschafft. Mit einem etwas anderen Schema ist es mir dann doch gelungen. Ich
möchte dieses Programm aber hier nicht präsentieren, weil es etwas Besseres
gibt. Die Internetsuche ergab verschiedene Programme in „C“, die ich aber nicht
in Small Basic umsetzen konnte. Schließlich fand ich eine Schritt-für-Schritt-Anleitung,
die ich mit etwas Mühe umsetzen konnte. Der Startstring beliebiger Länge muss
hier aus den geordneten Zahlen 1-2-3-4…. bestehen, weil Größenvergleiche
durchgeführt werden müssen.
Möchte man
andere Elemente verwenden, muss das vor dem Ausdrucken umgeschlüsselt werden,
z.B.: 1 ist identisch mit a usw. Das Programm
arbeitet rekursiv, d.h. ein Startstring wird nach einer bestimmten Vorschrift
permutiert und das Ergebnis ist dann der neue String, der wieder nach derselben
Vorschrift permutiert wird. Eine
Erklärung, warum das funktioniert, kann ich leider nicht anbieten. Immerhin
soll das Verfahren schon im 14. Jahrhundert bekannt gewesen sein (man höre und
staune).
Hier die
originale Anleitung:
https://www.computerix.info/dhge-prog-c/perm.pdf
1. Suche von
hinten die erste Zahl, die kleiner als die Zahl dahinter ist. Wenn du keine
findest, dann enthält das Array schon die letzte Permutation, und du kannst sofort
erfolglos zurückkehren.
2. Merk dir
die Position (Index) dieser Zahl als „links”.
3. Suche von
hinten die erste Zahl, die größer als die Zahl an der Stelle „links” ist. Eine
solche Zahl findest du immer. Merk dir die Position dieser Zahl als „rechts”.
4. Vertausche
die Zahlen an den Positionen „links” und „rechts”.
5. Drehe die
Reihenfolge aller Zahlen zwischen der Position „links + 1” und dem Ende des
Arrays um.
6. Kehre
erfolgreich zurück: Das Array enthält die nächste Permutation.
Beispiel:
Zusgangsstring:
a0 = 1, a1 = 3, a2 = 2 also: 132
Die
vollständige Reihe wäre: 123, 132, 213, 231, 312, 321
Listing:
'Erzeugen
aller Permutationen einer Zeichenkette mit n Elementen 1-2-3-4-...
TextWindow.Write("Gib
die Länge der Zeichenkette ein: ")
n = TextWindow.ReadNumber()
TextWindow.WriteLine("")
nn= 1
For i = 1 To n 'n! berechnen (Fakultät)
nn = i*nn
EndFor
TextWindow.WriteLine("n! = " + nn)
For i = 0 To n-1 'Startstring erzeugen
a[i] = i+1
EndFor
For i = 0 To n-1 'Startstring schreiben
TextWindow.Write(a[i])
EndFor
TextWindow.WriteLine("")
zz = 0
Marke: ':::::::::::::::::::::::::Rekursion
For i = n-1 To 0 Step -1
If a[i-1]<a[i]
Then
links = i-1
i = 0 'FOR Ende
Endif
EndFor
For i = n-1 To 0 step-1
If
a[i]>a[links] Then
rechts = i
i = 0 'FOR Ende
Endif
EndFor
xx = a[links] 'vertauschen
yy = a[rechts]
a[links] = yy
a[rechts] = xx
For i = 0 To n-1 'string kopieren
aa[i] = a[i]
EndFor
x = n-1 'Reihenfolge drehen
For i = links+1 To n-1
a[i] = aa[x]
x = x-1
EndFor
For i = 0 To n-1 'string schreiben
TextWindow.Write(a[i])
EndFor
TextWindow.WriteLine("")
zz = zz+1
If zz = nn-1 Then
TextWindow.WriteLine("Ende")
Else
Goto Marke
EndIf
Zum Schluss
Ich habe auch
die KI gefragt und erhielt zu meiner maßlosen Überraschung nahezu
verzögerungsfrei ein fix und fertiges Programm präsentiert. Das ist der game
changer, der die Entwicklung der Menschheit in eine neue Richtung lenken wird.
Fragt sich nur, in welche …
Das Programm
hat aber nicht funktioniert. Es enthielt auch Anweisungen, die es in Small
Basic gar nicht gibt, es konnte also nicht irgendwo abgeschrieben sein. Ich
habe dann die KI gefragt, ob sie das Programm selbst erstellt habe. Das wurde
verneint. Auf zwei
weitere Anfragen erhielt ich jeweils andere Programme, die aber auch nicht
funktioniert haben. Vorerst bleibt also der Mensch doch noch die Krone der
Schöpfung, aber sicher nicht mehr lange.
Elektronik-Labor
Projekte
Mikrocontroller
PicoBasic