AVR Zufallszahl

Für alles, was in den übrigen Lazarusthemen keinen Platz, aber mit Lazarus zutun hat.

AVR Zufallszahl

Beitragvon Mathias » 19. Dez 2017, 18:12 AVR Zufallszahl

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 gün
Mit Java und C/C++ sehe ich rot
Mathias
 
Beiträge: 4263
Registriert: 2. Jan 2014, 17:21
Wohnort: Schweiz
OS, Lazarus, FPC: Linux (die neusten Trunc) | 
CPU-Target: 64Bit
Nach oben

Beitragvon Timm Thaler » 19. Dez 2017, 19:43 Re: AVR Zufallszahl

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.
Timm Thaler
 
Beiträge: 670
Registriert: 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
Nach oben

Beitragvon indianer-frank » 19. Dez 2017, 19:44 Re: AVR Zufallszahl

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.
indianer-frank
 
Beiträge: 132
Registriert: 30. Nov 2008, 21:53

Beitragvon Mathias » 19. Dez 2017, 20:14 Re: AVR Zufallszahl

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 gün
Mit Java und C/C++ sehe ich rot
Mathias
 
Beiträge: 4263
Registriert: 2. Jan 2014, 17:21
Wohnort: Schweiz
OS, Lazarus, FPC: Linux (die neusten Trunc) | 
CPU-Target: 64Bit
Nach oben

Beitragvon indianer-frank » 19. Dez 2017, 20:19 Re: AVR Zufallszahl

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.
indianer-frank
 
Beiträge: 132
Registriert: 30. Nov 2008, 21:53

Beitragvon Timm Thaler » 19. Dez 2017, 21:07 Re: AVR Zufallszahl

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: 670
Registriert: 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
Nach oben

Beitragvon Timm Thaler » 19. Dez 2017, 21:17 Re: AVR Zufallszahl

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.
Timm Thaler
 
Beiträge: 670
Registriert: 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
Nach oben

Beitragvon indianer-frank » 19. Dez 2017, 21:39 Re: AVR Zufallszahl

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.
indianer-frank
 
Beiträge: 132
Registriert: 30. Nov 2008, 21:53

Beitragvon Timm Thaler » 19. Dez 2017, 22:00 Re: AVR Zufallszahl

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.
Timm Thaler
 
Beiträge: 670
Registriert: 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
Nach oben

Beitragvon mschnell » 20. Dez 2017, 10:22 Re: AVR Zufallszahl

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 20. Dez 2017, 14:12, insgesamt 3-mal geändert.
mschnell
 
Beiträge: 3221
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon mse » 20. Dez 2017, 11:31 Re: AVR Zufallszahl

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
mse
 
Beiträge: 1967
Registriert: 16. Okt 2008, 09: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
Nach oben

Beitragvon Timm Thaler » 20. Dez 2017, 16:19 Re: AVR Zufallszahl

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.
Timm Thaler
 
Beiträge: 670
Registriert: 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
Nach oben

Beitragvon mschnell » 20. Dez 2017, 17:25 Re: AVR Zufallszahl

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
mschnell
 
Beiträge: 3221
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon indianer-frank » 20. Dez 2017, 18:00 Re: AVR Zufallszahl

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!
indianer-frank
 
Beiträge: 132
Registriert: 30. Nov 2008, 21:53

Beitragvon Timm Thaler » 20. Dez 2017, 20:51 Re: AVR Zufallszahl

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.
Timm Thaler
 
Beiträge: 670
Registriert: 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
Nach oben

» Weitere Beiträge siehe nächste Seite »
Nächste

Zurück zu Sonstiges



Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 3 Gäste

porpoises-institution
accuracy-worried