Pfad: Home => AVR-DE => Anwendungen => Zufall tn13 => Zufallszahlen berechnen   This page in english: Flag EN Logo
Zufallsfarben 250*250 AVR-Anwendungen

Zufallszahlen mit ATtiny13
Anwendung und Software für Zufallszahlen in Assembler

Zufallszahlen mit ATtiny13

Anzeigen Rauschgenerator Analyse

1 Zufallszahlen berechnen

Zum Berechnen von Zufallszahlen braucht man mathematische Operationen, die möglichst viele Bits einer Zahl verändern. Hier werden folgende drei Operationen kombiniert:
  1. Exklusiv-Oder: Diese Operation kehrt alle Bits einer Zahl um, die in einer zweiten Zahl ebenfalls Eins sind. Sie geht in AVR-Assembler so: EOR Register1,Register2. Das Ergebnis steht dann in Register1.
  2. Swap: Diese Operation vertauscht die obersten vier Bit eines Registers (Nibble) mit den untersten vier Bit. Sie geht in AVR-Assembler so: SWAP Register.
  3. Addieren: Diese Operation addiert zwei Zahlen. Dabei ändern sich alle Bits, die in der addierten Zahl nicht Null sind. Zusätzlich werden aber durch Überlauf aus den niedrigeren Bits (wenn beide Eins sind) auch solche Bits verändert. Addieren geht in AVR-Assembler mit ADD Register1,Register2, das Ergebnis landet wieder in Register1.
Damit ist der Assembler-Zufallsgenerator schon fertig:

.def rN1 = R16 ; Die erste Zufallszahl
.def rN2 = R17 ; Die zweite Zufallszahl
  ldi rN1,Anfang1 ; Starte mit der ersten Zahl
  ldi rN2,Anfang2 ; Starte mit der zweiten Zahl
Loop:
  eor rN1,rN2 ; Exklusiv-Oder
  swap rN1 ; Nibble vertauschen
  add rN2,rN1 ; Addieren
  rjmp Loop

Die große Frage ist: Wie fängt man am Besten an (Anfang1, Anfang2) und nach wieviel Zahlen wiederholt sich die Zahlenfolge?

Das Kriterium bei der Auswahl von Anfang1 und Anfang2 sollte sein, dass möglichst alle Zahlen zwischen 0 und 255 in gleicher Anzahl vorkommen, dass die Zahlenreihe also möglichst homogen ist. Um das zu ermitteln, habe ich alle Anfangszahlen Anfang1 und Anfang2 zwischen 0 und 255 variiert, außer 0 und 0, 100.000 mal die obigen Operationen ausgeführt und für jede Ergebniskombination gezählt, wie oft diese vorkommt. Das habe ich natürlich nicht mit einem AVR gemacht, sondern mit einem Lazarus-Pascal-Programm.

Inhomogenitätssummen Bei idealer Homogenität müssten alle Bytes 100.000 / 256 = 390,625 mal vorkommen. Also habe ich für alle 65.535 Kombinationen von Anfang1 und Anfang2 die Abstände zwischen der Anzahl der 256 Zählereignisse von diesem Wert gebildet, diese quadriert und aufsummiert. Das Quadrieren sorgt dafür, dass besonders große Abstände höher gewichtet werden. Aus der Summe habe ich die Wurzel gezogen, was ein Maß für die Inhomogenität ist (je gröer die Summenwurzel, desto inhomogener).

Dabei zeigt sich Erstaunliches: Ein Teil von 17,7% der 65.535 Kombinationen liegt weit über einem Wurzelsummen-Wert von 250, alle anderen darunter. Die Verteilung der inhomgenen Kombinationen ist unregelmößig, es lässt sich jedenfalls kein Muster erkennen.

Das sind die Inhomogenitätswerte für einen ausgewählten Bereich der 65.535 Kombinationen. Die Zahlenwerte für Anfang1 (N1) und Anfang2 (N2) sind in dem Diagramm hexadezimal angegeben.

So oder ähnlich wiederholt sich das über den gesamten Bereich: bestimmte Kombinationen gehen halt nicht besonders gut, dafür sind alle anderen ungefähr gleich homogen. Da fällt es schwer, die optimale Kombination auszuwählen, weil alle ungefähr gleich gut sind. Man muss nur bestimmte Kombinationen dringend meiden. Die geringste Inhomogenitätssumme hat die Kombination 0x02A8 (N1=168, N2=2).

Inhomogenität und Periodizität Die zweite Frage ist, nach wieviel Zahlenwerten immer die gleiche Zahlenreihe wieder auftaucht. Es reicht dafür aus, die ersten vier Zahlen in der weiteren Zahlenreihe zu suchen. Auch dies bringt Erstaunliches zutage.

Das Bild zeigt am gleichen Auszug, dass alle Periodenlängen fast gleich lang sind (grüne Balken, Zahlenwert 53.961), nur diejenigen mit erhöhter Inhomogenität (rote Balken, bei 250 abgeschnitten) haben eine drastisch kürzere Periodizität. Noch ein Grund mehr, diese Kombinationen zu meiden.

Dass sich die Folge nach 53.961 Zahlen wiederholt, dürfte in der Praxis nicht auffallen. Bei sekündlichem Wechsel wird erst nach 15 Stunden wieder die gleiche Zahlenreihe erreicht, bei drei zufällig ausgewählten RGB-Farben nach 5 Stunden. Das dürfte auch dem schärfsten Kritiker dieser Reihe nicht auffallen.

Häufigkeit Zahlen bei 100.000 Würfen Wie sich die 100.000-fach gewürfelten Zahlen auf die 256 Zahlenwerte verteilen, zeigt dieses Diagramm. Wenn das keine schöne Gleichverteilung ist, dann will ich ab jetzt Horst heißen.

Die ersten 256 Zufallszahlen Wer es mit avr_sim simulieren will, findet hier die ersten 256 gewürfelten Zahlen mit 168 und 2 als Anfangswerte in dezimalem und im Hex-Format.

Die 25 besten Ausgangszahlen bei 100k Läufen Die 25 besten Ausgangszahlen bei 1M Läufen Wer noch andere Kombinationen verwenden will, findet hier die 25 Besten. Links die aus 100.000 Läufen, rechts die aus 1 Mio. Läufen. Das ganze Nummernschieben habe ich mit einem Lazarus-Programm erledigt, dessen Quellcode hier zum Download steht.

Seitenanfang Hauptseite Anzeigen Rauschgenerator Analyse


Lob, Tadel, Fehlermeldungen, Genöle und Geschimpfe oder Spam bitte über das Kommentarformular an mich.

©2020 by http://www.avr-asm-tutorial.net