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
D
ie 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