AVR Zufallszahl

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: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.
Häh? Welcher Startwert sollte das denn sein, wenn alle einen Defekt haben?

Oder meinst Du, daß es auch vernünftige Lineare Kongruenzgeneratoren gibt?

Das ist unbestritten, und wenn wenn man für c die Zweierpotenz der Registerlänge nimmt, spart man sich sogar die von Dir verabscheute mod-Operation (oder man nimmt ein and, wenn man aus welchen Gründen auch immer, nicht die volle Länge haben will). Im Abschnitt Periodenlänge findet man dann die Bedingungen für eine maximal-mögliche Periode.

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:Häh? Welcher Startwert sollte das denn sein, wenn alle einen Defekt haben?


Du musst hier unterscheiden zwischen den Start- oder Seedwerten, und den Faktoren in der Gleichung, beide müssen sinnvoll gewähhlt sein. Und: Es werden nicht alle Werte erzeugt, aber da man - in meinem Beispiel - nur ein Byte des jeweils erzeugten Wertes verwendet, kommen in diesem Byte alle Werte vor, sogar relativ gut verteilt. Im anderen nicht, aber das nimmt man dann nicht.

Btw: Dass alle Zahlen mindestens einmal vorkommen ist nur EINE Aussage zu einem brauchbaren Zufallszahlengenerator. Auf meinem Zollstock kommen auch alle Zahlen bis 200 mindestens einmal vor.

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: Allerdings braucht er wirklich gut ausgesuchte Werte, um brauchbare Zufallszahlen zu liefern.

Danke, das ist eine wirklich interessante und wichtige Erkenntnis.

So kann man sich täuschen ;) ;) ;)

Hast Du eine Berechnungs-Grundlage, wie man passende Werte aussucht ?

-Michael

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:Btw: Dass alle Zahlen mindestens einmal vorkommen ist nur EINE Aussage zu einem brauchbaren Zufallszahlengenerator. Auf meinem Zollstock kommen auch alle Zahlen bis 200 mindestens einmal vor.


Es gibt keine sinnvolle Aussage über einen Zufallszahlen-Generator :). Das ist ja gerade das, was den Zufall ausmacht.

Wenn man aber eine Aussage machen kann (z.B. dass bestimmte Zahlen nicht vorkommen) ist das natürlich ein deutlicher Nachteil.

Aber eine Aussage, die für einen echten Zufallszahlen-Generator zutreffen müsste ist: Die Sequenz 10^10 aufeinander folgende Nullen muss vorkommen.

-Michael

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:Aber eine Aussage, die für einen echten Zufallszahlen-Generator zutreffen müsste ist: Die Sequenz 10^10 aufeinander folgende Nullen muss vorkommen.


Dagegen kommt bei einem linearen Kongruenzgenerator nicht zweimal die gleiche Zahl nacheinander, sonst ist er tot. Wenn man allerdings nur einen Teil des Rechenwertes verwendet, z.B. 16bit aus einem 32bit oder 8 bit aus einem 16bit-Generator, kann durchaus mehrmals die gleiche Zahl rauskommen.

Einfach zu berechnen, aber auch verhängnisvoll sind auf Ganzzahlen skalierte Bifurkationsfunktionen. https://de.wikipedia.org/wiki/Datei:LogisticMap_BifurcationDiagram.png
Nach einer Einlaufzeit sind die zwar schön chaotisch, und es sind alle Werte im Zahlenraum vorhanden, aber wenn man sich die Werte genauer anschaut sieht man, dass die immer zwischen großen und kleinen Werten springen. Wenn man Pech hat treten oszillierende Bereiche auf, die immer die gleichen Zahlenfolgen liefern.

mschnell hat geschrieben:Hast Du eine Berechnungs-Grundlage, wie man passende Werte aussucht?


Es gibt zwar Formeln, wie man auf möglichst große Periodenlängen kommt, aber leider zeigen Punktepaartest und Tripeltest dann häufig, dass Generatoren mit großen Periodenlängen einen miesen Zufall bei aufeinanderfolgenden Zahlen liefern. Da muss man abwägen, was einem wichtiger ist. So ist zum Beispiel der lange Zeit beliebte RANDU-Generator nicht wirklich gut.

Aber für ein paar Würfelwerte oder ein Flackerlicht reichen die allemal.

Mathias
Beiträge: 6160
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 »

Nochmals zum Hauptthema zurück, so wie es scheint, ist ein Random auf einem AVR gar nicht so einfach.

Einen Würfel geht noch, aber will man etwas ernsthaftes machen, dann wird es echt kompliziert.
Wen ich mal Lust habe, werde ich mal im Arduino-Code rumstöbern und gucken, wie es dort gelöst wurde, :wink:
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

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:... einen miesen Zufall ...

Das ist schon ein lustiger Widerspruch in sich. Die Natur des Zufalls ist ja gerade, dass er mies ist :) :) :)

-Michael

Mathias
Beiträge: 6160
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 »

Ich habe meinen Zufallsgenerator für den Würfel optimiert.
Voraussetzung ist, das die Abstände zwischen den Abfragen von Random unregelmässig ist. Dies ist bei einem Tastendruck eigentlich kein Problem.

Code: Alles auswählen

var
  Random: Byte;
 
  procedure Timer0_Interrupt; public Name 'TIMER0_OVF_ISR'; interrupt;
  const
    RandomCount = 6;
  begin
    Inc(Random);
    if Random >= RandomCount then Random := 0;
  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
    UARTReadChar;
    Str(Random + 1: 4, s);
    UARTSendString(s);
  until 1 = 2;
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Mathias
Beiträge: 6160
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 »

Wen man mehr al ein Würfel hat, wird es ein wenig komplizierter, aber ich habe eine Lösung gefunden.
Den Timer musste ich langsamer stellen, als bei nur einem Würfel, ansonsten verschluckt sich der AVR.

Code: Alles auswählen

const
  anzWuerfel = 15;
var
  Random: array[0..anzWuerfel - 1] of byte;
 
  procedure Timer0_Interrupt; public Name 'TIMER0_OVF_ISR'; interrupt;
  const
    RandomCount = 6;
  var
    i: integer;
    rnd: array [0..anzWuerfel - 1] of byte;
  begin
 
    for i := 0 to anzWuerfel - 1 do
    begin
      Inc(rnd[i]);
      if rnd[i] > i then
      begin
        rnd[i] := 0;
        Inc(Random[i]);
        if Random[i] >= RandomCount then
          Random[i] := 0;
      end;
    end;
  end;
 
var
  s: ShortString;
  i: integer;
 
begin
  // Timer 0
  TCCR0A := %00;               // Normaler Timer
  TCCR0B := %011;              // Clock / CPU
  TIMSK0 := (1 shl TOIE0);     // Enable Timer0 Interrupt.
 
  UARTInit;
  asm
           SEI end;                 // Interrupts einschalten.
  repeat
    UARTReadChar;
    for i := 0 to anzWuerfel - 1 do
    begin
      Str(Random[i] + 1: 4, s);
      UARTSendString(s);
    end;
    UARTSendString(#13#10);
  until 1 = 2;
end.   
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Antworten