AVR Zufallszahl

Mathias
Beiträge: 6162
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

AVR Zufallszahl

Beitrag von Mathias »

Ich habe mal versucht einen Zufallsgenerator für einen Würfel zu schreiben. Für einen Würfel scheint dies zu reichen, wen auf Tastendruck gewürfelt wird. So wie der Code jetzt ist, kommt bei jedem Start des Programm die gleiche Zeichenreihenfolge raus, die war auch zu erwarten, das es immer ganz genau gleich abläuft. Bei Tastendruck sind die Abständer der Würfe nicht immer gleich, so wie es bei Delay mit nop der Fall ist.
Ein Randomize(), könnte man mit einem offenen Analog-Eingang machen.

Was auch noch ein Problem ist, bei einem Zahlenbereich von 0-5 ist die Genauigkeit gut genug. Aber ruft man Random zB. 65'000 auf, dann kommen Zahlen vom Bereich 0-536 doppelt so viel.

Gibt es besser Lösungen ?

Code: Alles auswählen

var
  rnd: UInt16;
 
  procedure Timer0_Interrupt; public Name 'TIMER0_OVF_ISR'; interrupt;
  begin
    Inc(rnd);
  end;
 
  function Random(l: byte): byte;
  begin
    Result := rnd mod l;
  end;
 
begin
  // Timer 0
  TCCR0A := %00;               // Normaler Timer
  TCCR0B := %001;              // Clock / CPU
  TIMSK0 := (1 shl TOIE0);     // Enable Timer0 Interrupt.
 
  UARTInit;
  asm  Sei end;                 // Interrupts einschalten.
  repeat
    for i := 0 to 100000 do  asm Nop end;
 
    Str(Random(6) + 1: 4, s);
    UARTSendString(s);
  until 1 = 2;
end.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: AVR Zufallszahl

Beitrag von Timm Thaler »

Richtige Zufallszahlen bekommt man mit einer Rauschquelle - z.B. der Basis-Emitter-Strecke eines Transistors in Sperrrichtung an einem ADC- oder Komparatoreingang. Allerdings braucht man dafür eine Hilfsspannung um die 9V, weil die BE-Strecke bei 5-6V durchbricht. Und es ist sehr schwer nachzuweisen, dass die Zahlen wirklich zufällig sind und nicht doch durch eingestreutes Netzbrummen oder so ein Muster aufweisen. Radioaktive Zerfälle mit Zählrohr messen dürfte auch etwas zu aufwendig sein,

Deswegen bedient man sich üblicherweise aus Pseudozufallszahlen-Generatoren, und da gibt es eine ganze Menge mehr oder weniger gut implementierbare. Bäh sind Generatoren, bei denen Zahlen dividiert, Wurzel gezogen oder gar Logarithmus berechnet werden muss, oder welche die zwingend Float-Operationen benötigen.

Richtig gut kann ein AVR dagegen Bits schubsen und vergleichen, und deswegen lassen sich sogenannte linear rückgekoppelte Schieberegister sehr gut implementieren. Die brauchen dann wieder einen Startwert, den man einmalig durch einen Tastendruch mit Timer, einen ADC-Wert oder irgendwas anderes erzeugt, und liefern dann beim jedem Aufruf eine recht gute Zufallszahl, ohne zwischendurch irgendwelche Timer oder ADC laufen haben zu müssen.

https://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister
https://www.schramm-software.de/tipps/zufallszahlen/
https://madgyver.de/de/2015/02/28/zufallszahlengenerator/

LFSR wiederholen sich nach einiger Zeit, bei langen Zahlen (bei denen man für einen Würfel dann nur einen Teil verwendet) allerdings erst in ein paar hundert Jahren.

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

Re: AVR Zufallszahl

Beitrag von indianer-frank »

Wie können den Werte größer als 254 auftreten :?: (das sind die Reste bei l=255). Weiterhin hat Dein Generator, wie Du selbst festgestellt hast eine Bias (Verzerrung). Hier eine Version ohne diesen Mangel:

Code: Alles auswählen

 
function Random(l: byte): byte;
var
    u: byte;
begin
    u :=  l*($ffff div l);
    repeat
       result := rnd;
    until result < u;
    result := result mod l;
end
Das Bias-Problem mit einem einfachen mod l erkennt man leicht, wenn man sich die Reste eines gleichverteilten Generators für kleine Werte ansieht, zB erhält man für rnd 0..7, l=6 die Reste 0, 1, 2, 3, 4, 5, 0, 1.

Der Vorschlag beruht darauf, daß die letzten Werte in einer unvollständigen Periode mod l verworfen werden (im Beispiel 6,7) und dann das mod l für eine Gleichverteilung sorgt.

Mathias
Beiträge: 6162
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: AVR Zufallszahl

Beitrag von Mathias »

Wie können den Werte größer als 254 auftreten :?: (das sind die Reste bei l=255).

Da hat du natürlich recht, bei Zahlen > 255 muss man die Funktion ein wenig ändern.

Code: Alles auswählen

 repeat
       result := rnd;
    until result < u;

Da diese Schleife schneller läuft als der Timer, kommt man sobald Result 0 ist aus der Schleife raus. 0 mod x gibt 0.

@Timm Thaler
Das habe ich fast gedacht, das es nichts einfaches gibt, das perfekt ist.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

Re: AVR Zufallszahl

Beitrag von indianer-frank »

Mathias hat geschrieben:Da diese Schleife schneller läuft als der Timer, kommt man sobald Result 0 ist aus der Schleife raus. 0 mod x gibt 0.
Richtig, aber was ist an 0 auszusetzen? Ist doch bei Deiner Funktion genauso!

Vielleicht noch etwas mehr: Wenn l=6 ist hat man u = ($ffff div 6)*6 = 65532. Solange rnd im Bereich 0 .. 65531
wird die Schleife genau einmal durchlaufen und das Ergebnis das gleiche wie bei Dir.

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: AVR Zufallszahl

Beitrag von Timm Thaler »

Was heißt einfach? Für eine LED-Lampe hab ich mal einen Generator gebaut, der besteht aus ein paar Zeilen Assembler:

Code: Alles auswählen

   .EQU   Crndmul      = 80      ;Mulwert für RND
.EQU   Crndseed   = 7954      ;Seedwert für RND, 16 bit
...
   ldi   TEMP1, high(Crndseed)
   sts   Arndval, TEMP1
   ldi   TEMP1, low(Crndseed)
   sts   Arndval + 1, TEMP1   ;Seedwert RND
...
   rcall   rnd_calc      ;Zufallszahl berechnen
   lds   TEMP1, Arndval + 1   ;Zufallszahl low-Byte holen
...
...
...
   ;**** Zufallszahl berechnen ****
 
rnd_calc:
               ;x = a * (x & $FF) + (x >> 8)
   ldi   TEMP1, Crndmul      ;Multiplikator
   lds   TEMP3, Arndval + 1   ;Wert x low holen
   rcall   mpy8u         ;xneu = a * (x & FF)
   lds   TEMP1, Arndval      ;Wert x high holen
   add   TEMP3, TEMP1
   clr   TEMP1
   adc   TEMP4, TEMP1      ;xneu = xneu + (x >> 8)
 
   sts   Arndval, TEMP4
   sts   Arndval + 1, TEMP3   ;Wert speichern
 
   ret


Hab vergessen wie das Verfahren heißt, aber die Werte sind gar nicht so schlecht. Man muss aber die richtigen Seedwerte nehmen, sonst rennt es sich fest.

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: AVR Zufallszahl

Beitrag von Timm Thaler »

indianer-frank hat geschrieben:Vielleicht noch etwas mehr: Wenn l=6 ist hat man...


... ein ganz anderes Problem: Bei x mod 8, oder x mod 4 ist der Compiler so schlau, das mit AND zu erledigen, und bekommt den Rest mit wenigen Taktzyklen. Bei einem mod, welches nicht durch 2^n geht wird allerdings eine Software-Division aufgerufen, die richtig heftig Rechenzeit kostet.

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

Re: AVR Zufallszahl

Beitrag von indianer-frank »

Timm Thaler hat geschrieben:
indianer-frank hat geschrieben:Vielleicht noch etwas mehr: Wenn l=6 ist hat man...


... ein ganz anderes Problem: Bei x mod 8, oder x mod 4 ist der Compiler so schlau, das mit AND zu erledigen, und bekommt den Rest mit wenigen Taktzyklen. Bei einem mod, welches nicht durch 2^n geht wird allerdings eine Software-Division aufgerufen, die richtig heftig Rechenzeit kostet.
Kann ja sein, daß das Rechenzeit kostet, aber das ist doch vernachlässigbar im Vergleich zu 100000 nops (so langsam kann keine CPU sein) oder wenn man die Routine erst nach/bei User-Eingabe aufruft. Ich sage ja nicht, daß man keine bessere Generatoren schreiben kann oder mein Vorschlag optimal ist; er ist dafür da, die Bias bei Zufallszahlen in Teilbereichen zu entfernen (oder zumindest sehr stark zu reduzieren). rnd sollte dabei natürlich schon OK sein, nicht wie zB der hier https://xkcd.com/221.

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: AVR Zufallszahl

Beitrag von Timm Thaler »

indianer-frank hat geschrieben:... Kann ja sein, daß das Rechenzeit kostet, aber das ist doch vernachlässigbar im Vergleich zu 100000 nop...


Eine sehr schnelle Routine und durchaus ernstgemeint: Der Atmega328 (Arduino) hat eine Menge Flash und so ein Würfel ist ja nicht viel Programm. Einfach ein paar tausend Zufallswerte (1..6) am PC berechnen lassen und als Tabelle im Flash ablegen, pro Byte lassen sich 2 Werte (low-Nibble und high-Nibble) speichern, über einen durchlaufenden Pointer abrufen und schon sind die nächsten Runden Mensch-ärgere-dich-nicht gesichert.

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: AVR Zufallszahl

Beitrag von mschnell »

Für Pseudo-Zufallszahlen reicht fast immer ein Formel wie

z(n) = (z(n-1) * a + b) modulo c

mit a, b und c am besten ziemlich große Primzahlen.

Die Zahlenfolge hat (offensichtlich) eine Periode von c, innerhalb der Periode kommt jede Zahl genau einmal vor, und (wenn c eine Primzahl ist) es gibt keine keine erkennbaren "Sub-Zyklen.

Wenn sehr viel Zufallszahlen gebraucht werden, kann man entweder c mit entsprechend viele Bitstellen vorsehen oder Algorithmus wie bei fpc implementiert verwenden.

Ein davon unabhängiges Problem ist natürlich die Wahl von z(0) ("Seed", "Randomize()").

Da muss man irgendwelche Hardware-Eigenschaften verwenden.

Es gibt CPUs speziell für WLAN Router etc, die für die Verschlüsselung sehr unvorhersehbare Zufallszahlen brauchen, die entsprechende Hardware integriert haben.

-Michael
Zuletzt geändert von mschnell am Mi 20. Dez 2017, 14:12, insgesamt 3-mal geändert.

mse
Beiträge: 2013
Registriert: Do 16. Okt 2008, 10:22
OS, Lazarus, FPC: Linux,Windows,FreeBSD,(MSEide+MSEgui 4.6,git master FPC 3.0.4,fixes_3_0)
CPU-Target: x86,x64,ARM

Re: AVR Zufallszahl

Beitrag von mse »

Weitere Algorithmen sind hier:
http://wiki.freepascal.org/Marsaglia%27 ... generators
MWC hat eine recht lange Periode und ist effizient zu Implementieren, eine Pascal Implementation ist hier:
https://gitlab.com/mseide-msegui/mseide ... enoise.pas

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: AVR Zufallszahl

Beitrag von Timm Thaler »

mschnell hat geschrieben:z(n) = (z(n-1) * a + b) modulo c
mit a, b und c am besten ziemlich große Primzahlen.


Was hatten wir grad nochmal über die Ganzzahl-Division von großen Zahlen auf dem AVR gesagt?

Das sind dann die Leute, die rumheulen: Ah, mein Atmega reicht nicht für ein Blinklicht, ich brauch mindestens einen 32-Bitter.

Und mit einfach mal "ziemlich große Primzahlen" kannst Du auch in die Kacke fassen, dann kann es nämlich passieren, dass diese Funktion irgendwann nur noch zwischen 2 Werten springt.

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: AVR Zufallszahl

Beitrag von mschnell »

Timm Thaler hat geschrieben: dass diese Funktion irgendwann nur noch zwischen 2 Werten springt.

Ich bin ziemlich sicher. dass die beschriebene Funktion in c Schritten jede Zahl zwischen 0 und c-1 genau einmal liefert.

Und man braucht natürlich für jede Anwendung die passende Hardware. Zum würfeln dürfte es ziemlich wurscht sein, wie lange die Berechnung der nächsten Zufalls-Zahl dauert.

-Michael

indianer-frank
Beiträge: 134
Registriert: So 30. Nov 2008, 21:53

Re: AVR Zufallszahl

Beitrag von indianer-frank »

mschnell hat geschrieben:Ich bin ziemlich sicher. dass die beschriebene Funktion in c Schritten jede Zahl zwischen 0 und c-1 genau einmal liefert.
'Ziemlich sicher' reicht nicht. Nimm als Beispiel a = 3, b = 5, c = 7. Dann erhältst Du mit seed=0 die Werte 0, 5, 6, 2, 4, 3, 0 ... Also keine 1! Für seed=1 gibt es dafür als Ausgleich nur Einser. Also ist dieser Generator für jedes seed defekt!

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: AVR Zufallszahl

Beitrag von Timm Thaler »

indianer-frank hat geschrieben:Also ist dieser Generator für jedes seed defekt!


Nee, der Generator funktioniert schon, der ist nämlich ziemlich ähnlich dem, was ich oben als Assemblercode gepostet habe. Allerdings braucht er wirklich gut ausgesuchte Werte, um brauchbare Zufallszahlen zu liefern. Sonst passiert nämlich genau das: Er springt zwischen einigen Werten hin und her oder fährt sich fest.

Antworten