einfacher, kleiner(!) Pseudo Zufallsgenerator gesucht

[HansenPansen (Gast)]

Hallo Forum,

ich benötige einen  kleinen (der in der stdlib ist zu groß) 
Pseudo-Zufallgenerator der einen 8-Bit Wert auswirft. Die 
Gleichverteilung ist nicht so wichtig, als seed nehme ich einen Wert, 
den ich mir im EEPROM abspeichere.

Hat jemand  so etwas schon mal gemacht??

Viele Grüße,

HansenPansen

[einer (Gast)]

Sprache?

Versuchs mal mit Primzahlenaddition.

bye

[HansenPansen (Gast)]

Danke,

wir sind im GCC Forum ;-)

ich suche halt was fertiges, getestetes......

Grüße

[avion23 (Gast)]

Eine Liste von Methoden: 
http://en.wikipedia.org/wiki/List_of_random_number_generators


Besonders einfach ist dieser hier: 
http://en.wikipedia.org/wiki/List_of_random_number_generators . Dort ist 
er allerdings nicht besonders gut erklärt. Ich meine, man shiftet die 
ganze Zahl nach links und füllt das LSB mit zwei ge-XOR-ten Bits der 
Zahl wieder auf.

Das hier dürfte dir zumindest genug Keywords für deine Google Suche 
liefern.

[Stefan E. (sternst)]

HansenPansen wrote:

> wir sind im GCC Forum ;-)

Und? Das bedeutet nicht automatisch, dass du was in C suchst, 
schließlich kann der auch noch diverse andere Sprachen.
GCC = GNU Compiler Collection

[HansenPansen (Gast)]

@sternst

oh - du hast recht..... wusste ich noch nicht.

Ich habe die Abkürzung mit C assoziiert, was ja im Kontext dieses Forums 
auch praktisch richtig ist (die Fortran Fragen halten sich hier ja auch 
stark in Grenzen ;-))

Ok, ich möchte mit WINAVR in C einen kleinen Pseudo Zufallsgenerator auf 
einem ATTINY 25 implementieren, 8 Bit Rückgabewert (die rand und srand 
sind mir vom Flashbedarf zu groß), seed möchte ich aus dem EEPROM lesen.
Meine Ansprüche an die Gleichverteilung sind gering, alle Zahlen sollten 
halt auch mal vorkommen.

Hat jemand da was (so um die 50 Byte rum wäre toll) schon mal 
implementiert?

Vielen Dank für eure künftigen Antworten!

[einer (Gast)]

Bin über Neue Beiträge reingekommen.
Das winzige Forum:GCC hab ich erst jetzt gesehen.

sorry

[HansenPansen (Gast)]

Ist doch auch kein Problem!

[risu (Gast)]

Beitrag "Quellcode für Pseudozufallsgenerator"

[HansenPansen (Gast)]

sieht gut aus, werde ich mal testen!

Danke

[HansenPansen (Gast)]

was mach ich eigentlich mit den ganzen long Typen - tut das für 8 Bit 
Ergebnis not?

Oder kann man das runterbrechen auf uint16 ?

Grüße,

HansenPansen

[Peter Diener (Gast)]

Hallo,

also wenn du was ganz einfaches willst, nimm eine Taste, die der 
Benutzer drückt und zähl währenddessen mit sehr hoher Geschwindigkeit 
eine 8-Bit Variable hoch und stoppe, wenn die Taste losgelassen wird.
Der Zähler muss schnell sein und von 255 auf 0 überlaufen.
Der Wert beim Stop ist das Ergebnis.

Geht natürlich nur, wenn es einen Benutzer gibt, der eine Taste drücken 
mag  kann  darf.


Eventuell noch die Taste entprellen.

unsigned char random8(void)
{
unsigned char count;

count = 0;
while (~(PINA & 0x01)) {}   //Warte auf Tastendruck
while (PINA & 0x01)         //Solange Taste gedrückt, loop
{
  count++;
}

return count;
}

Viele Grüße,

Peter

[Simon K. (simon)]

einer wrote:
> Sprache?
>
> Versuchs mal mit Primzahlenaddition.
>
> bye

Das ist das Stichwort. Einfacher geht es eigentlich nicht mehr.

#define MYRAND_MULTIPLIER  19
#define MYRAND_CONSTANT    37
#define MYRAND_MODULO    256

uint8_t g_nLastRandom = 1;

void MyRandSeed(uint8_t nSeed)
{
  g_nLastRandom = nSeed;
}

uint8_t MyRandGet()
{
  //copy into local variables to avoid 16-bit integer expansion
  uint8_t Multiplier = MYRAND_MULTIPLIER;
  uint8_t Constant = MYRAND_CONSTANT;

  //implicit %256 by 8-bit datatype overflow
  g_nLastRandom = (g_nLastRandom * Multiplier + Constant)/* % MYRAND_MODULO*/;
  
  return g_nLastRandom;
}

So etwas hab ich mal für meine GeekClock gebraucht. Beachte aber, dass 
du immer noch einen Startwert brauchst (oder dich damit abfinden kannst, 
dass die Zufallsreihe immer gleich beginnt). (Ich hatte halt eine 
Uhr-Anwendung, was sich der Startwert im Prinzip schon anbietet).

[einer (Gast)]

@Simon
Sehr gut!

Genauso hab ich das gemeint.

Als Seed kann man ja die besagte Tasten Timingmethode nehmen
oder den letzten Seed eepromen.

[Simon K. (simon)]

Hier noch weiterführende Infos zur Funktionsweise:
http://en.wikipedia.org/wiki/Linear_congruential_generator

[Tishima (Gast)]

Hallo!

Hier in der GLCD Lib ist ein 72 Byte großer lsfr Zufallsgenerator drinn.

Beitrag "Nokia 6100 Grafiklibrary die Zweite"

Den finde ich recht brauchbar.

gruß,
Bjoern

[HansenPansen (Gast)]

@Peter

gute Idee - ich habe aber keinen Timer mehr übrig...

Merke ich mir für nächstes mal!

Vielen Dank.

@Simon,einer

Danke, ich glaube, das passt genau.

Werde ich morgen mal probieren.

Viele Grüße,

Hansen Pansen

[HansenPansen (Gast)]

@Björn

der benutzt doch aber auch die normale rand() funktion und zieht die 
ganze lib rein - oder ist die rand() funktion neu implementiert und ich 
hab sie übersehen?

Viele Grüße,

HansenPansen

[HansenPansen (Gast)]

So,

die Lösung von Simon scheint zu funktionieren - über 400 Byte gegenüber 
srand() und rand() gespart!!

Wenn ich allerdings die auskommentierte % MYRAND_MODULO Geschichte (nat. 
mit meinem Modulo (111) aktiviere, kommen nur noch 3 versch Zahlen an 
(0,37,74).

Mach ich das Modulo außerhalb der Funktion, ist alles ok.

Warum?

Viele Grüße,

HansenPansen

[einer (Gast)]

Les mal den Kommentar darüber.

Die Funktion Baut immer auf dem Letztem Wert von g_nLastRandom auf und 
den versaust du damit.

[HansenPansen (Gast)]

recht du hast .....

Dann sollte ich die auskommentierte % MYRAND_MODULO Versuchung 
schnellstens löschen (oder ist das zu was gut?).

Vielen Dank!

[einer (Gast)]

Ach ja.
Mit dem Zähler von Peter ist kein timer gemeint sondern was in der art.

while(keypressed){i++}

ciao

[einer (Gast)]

Durch den Byte überlauf entspricht die anweisung dem %MYRAND_MODULO

Das was du willst geht so.

return g_nLastRandom % 111;


Und das wo ich immer sage ich kann gar kein C.

[HansenPansen (Gast)]

Ich glaube, ich mache das mit dem gespeicherten seed im EEPROM - dann 
kann ich den uC (wenn nix passiert) besser schlafen legen...aber mal 
sehen.

Vielen Dank!

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

> 0,37,74
 0, 37, 74, 111 , 148

> die Lösung von Simon scheint zu funktionieren...
So richtig zufällig scheint aber die Verteilung nicht zu sein :-(
Hier das Ergebnis nach 256000 Durchläufen:
 Wert  Treffer
  [0]  2000
  [1]  2000
  [2]  0
  [3]  0
  [4]  2000
  [5]  2000
  [6]  0
  [7]  0
  [8]  2000
  [9]  2000
  [10]  0
  [11]  0
  [12]  2000
  [13]  2000
  [14]  0
  [15]  0
  [16]  2000
  [17]  2000
  [18]  0
  [19]  0
        :
        :

Der Grund: mit

#define MYRAND_MULTIPLIER  19

ist die Bedingung 3 aus 
http://en.wikipedia.org/wiki/Linear_congruential_generator verletzt.
Mit

#define MYRAND_MULTIPLIER  17

sieht es besser aus:
 Wert  Treffer
  [0]  1000
  [1]  1000
  [2]  1000
  [3]  1000
  [4]  1000
  [5]  1000
  [6]  1000
  [7]  1000
  [8]  1000
  [9]  1000
  [10]  1000
  [11]  1000
  [12]  1000
  [13]  1000
  [14]  1000
  [15]  1000
  [16]  1000
        :
        :
        :

[rene (Gast)]

http://www.ibrtses.com/simulations/lfsr.html

Die Hardwareloesungen kann man auch mit wenigen Zeilen programmieren.
Ein paar Shift & XOR

[HansenPansen (Gast)]

@Lothar Miller

stimmt! Vielen Dank für den Tip!

@rene

Danke für die Anregung,

in Assembler habe ich das bei meiner Suche öfter gesehen, was fertiges 
in C habe ich aber nicht gefunden.

HansenPansen

[Jörg (Gast)]

Habe zuletzt auch einen LFSR in VHDL programmiert, der Aufwand ist
mehr oder weniger nur 1-2 Zeilen:

Beitrag "Zufalls-Bits in VHDL"

Der Code ist sehr einfach in C/C++ umsetzbar, im Kopf findest du auch
Tabellen für unterschiedlich lange Shiftregister.
Eine ausführliche Anleitung inkl. Tabellen kann auch im Buch Numerical
Recipies nachgeschaut werden.

Gruss,

Jörg

[Simon K. (simon)]

Lothar Miller wrote:
> Der Grund: mit
>

> #define MYRAND_MULTIPLIER  19
>

> ist die Bedingung 3 aus
> http://en.wikipedia.org/wiki/Linear_congruential_generator verletzt.
> Mit
>

> #define MYRAND_MULTIPLIER  17
>

> sieht es besser aus:

Danke! Das werde ich sofort mal ändern. Ist schon etwas länger her, dass 
ich den mal benutzt habe. Und mit meinen Schul-Mathematik-(u.a. auch 
Symbolik-) Kenntnissen konnte ich nicht alle Bedingungen vernünftig 
interpretieren ;) Auf der Geek Clock (die jetzt an meiner alten Schule 
vor sich herumsteht) sieht man das Zum Glück nicht, da durch die 
Funktionsweise der Uhr der Zufallswert auch noch in einer bestimmten Art 
und Weise mit der Uhrzeit verrechnet wird. Da ist die Periodizität 
(falls das das richtige Wort ist und falls es überhaupt eine gibt) so 
groß...

Achja: Nur am Rande. das MODULO in der MyRandGet Funktion gehört nach 
der Formel des Linear Congruential Generators da hin. Es ist aber NICHT 
dafür da, den Zufallswert zu begrenzen. Das Begrenzen muss nach dem 
Holen eines Zufallswertes passieren, da (wie schon gesagt) ansonsten der 
Bereich in welchem der Generator die Zahlen generiert (eventuell sogar 
zu stark) eingeschränkt wird.

PS: Das ist der besagte Nachbau der "Geek Clock" 
Beitrag "Re: Die Geek-Clock (Uhr fuer Geeks) mit LED-Matrix"
Leider ist zur Zeit keine Beschreibung auf meiner Site vorhanden.

[Hagen R. (hagen)]

>Hier in der GLCD Lib ist ein 72 Byte großer lsfr Zufallsgenerator drinn.
>Beitrag "Nokia 6100 Grafiklibrary die Zweite"

Dateien lfsr.* im 2. ZIP des Threads. Es ist ein Shrinking Generator, 
dh. im Grunde laufen zwei LFSRs in parallel. So hat man eine Periode von 
2^63-2. Das ist weit mehr als ein 32Bit LCG. Davon abgesehen benötigt 
dieses SG-LFSR nur 72 Bytes an Code egal ob der AVR die 
HW-Multiplikation unterstützt oder nicht. Für einen LCG ist es besser 
wenn man HW-Multiplikation hat da ansonsten diese Multipikationen per 
Software durchgeführt werden müssen. Desweiteren benötigen die meisten 
LCGs auch noch die Division, eg. modulare Reduktion.
Über die beiden Polynome, Polynom_S und Polynom_A und den 1000 
mitgelieferten Polynomen in lfsr.inc kann man den PRNG, eg. die LFSRs 
individuell konfigurieren. Es gibt also 1000*1000 verschiendene SG-LFSRs 
die man so konfigurieren kann, und jede Konfiguration erzeugt eine 
andere eindeutige Sequenz von 2^63-2 Bits. Für 72 Bytes Code, ohne 
irgendwelche zusätzliche Libs der StdLib benutzen zu müssen und dafür 
das es auf jeden AVR gleichschnell läuft, ist das schon ziemlich 
leistungsfähig. Davon abgesehen sind die statistischen Eigenschaften des 
so produzierten Pseudozufalls der LFSRs weitaus besser als die der LCGs. 
Die LFSR Sourcen können direkt mit WinAVR GCC benutzt werden.

Gruß Hagen

[Hagen R. (hagen)]

Der LFSR im Attachment ist aus meinem FireFly Projekt extrahiert, siehe 
Beitrag "Glühwürmchen in Rotkohlglas gefangen"

Es ist ein 32Bit LFSR mit 2^32-1 Bits Periode. Er benötigt 52 Bytes an 
Code und läuft ebenfalls auf allen AVRs gleich effizient. Als Polynome 
können die aus lfsr.inc im vorherigen Zip benutzt werden, die unter 
Polynom_S 1000 gelisteten Polynome.

Vorteil dieses LFSRs ist es das er mit dynamisch zur Laufzeit 
veränderlichen Polynomen arbeiten kann, man hat also wenn man zb. mit 5 
Polynomen zur Laufzeit arbeitet gleich 5 verschiedene LFSRs in seiner 
Applikation.

Nutzen kann man dies um den LFSR beim Powerup des AVRs jedesmal mit 
anderen Seeds zu starten. Dh. der erzeugte Zufallsstrom an Bits ist 
immer unterschiedlich und man hat so das Problem des 
"zufälligen"Startwertes des PRNGs erschlagen. Gehen tut dies indem man 
einen Superseed im EEPROM speichert. Beim RESET des AVRs lädt man aus 
dem EEPROM dieses Superseed und benutzt

  // init PRNG, load last seed from EEPROM, calculate next seed and store back to EEPROM, use another polynom as in lfsr()
    eeprom_read_block((uint8_t *)&seed, (uint8_t *)(0), 4);
    lfsr_poly(32, 0x8140C9D5);
    eeprom_write_block((uint8_t *)&seed, (uint8_t *)(0), 4);

in Main(). Damit wird bei jedem RESET ein neuer Superseed durch ein LFSR 
mit Polynom 0x8140C9D5 erzeugt und gleich wieder im EEPROM 
abgespeichert. Bei jedem RESET des AVRs prositioniert man also den 
Superseed um 32Bit weiter. Dieser Superseed wird dann als Seed für den 
zweiten LFSR mit Polynom 0xC3A8AD09 benutzt und erzeugt dann die 
eigentlichen Zufallsbits für die Applikation beim Aufruf der Funktion 
lfsr().

Wollte man vergleichbares mit einem LCG machen so benötigt man statt der 
verschiedenen Polynome der LFSR für jeden LCG eine eigene 
Implementierung, sprich Formel mit anderen Parametern.

Gruß Hagen

[Artur Funk (Gast)]

<ironie an>
Mit einem 15 Cent Fotowiderstand und dem ADC des Atmegas. Dazu eine 
Multiplikation mit dem Low-Nibble des vorher gemessenen Wertes und 
fertig ist die Zufallszahl. Aber Achtung, funktioniert in der Dunkelheit 
leider nicht, da braucht man schon eine LED vor dem Fotowiderstand, die 
man per  PWM ansteuert, damit der Fotowiderstand nicht immer den 
gleichen Wert erhält.
<ironie aus>

[Simon K. (simon)]

Ah, super, dass Hagen sich mal meldet. Der ist ja der Krypto-Män ;) 
Interessant der LFSR, werde ich mir mal im hinterkopf behalten.

Artur Funk wrote:
> <ironie an>
> Aber Achtung, funktioniert in der Dunkelheit
> leider nicht, da braucht man schon eine LED vor dem Fotowiderstand, die
> man per  PWM ansteuert, damit der Fotowiderstand nicht immer den
> gleichen Wert erhält.
> <ironie aus>

Na super, ist doch wieder komplizierter als die Vorgeschlagenen 
Varianten. Außerdem ist der Zufallswert so sicher nicht gleich verteilt 
(so wie bei meiner ersten LCG Variante). Das ist Mist.

Höchstens als Seed könnte man den Wert gebrauchen. Aber bei Dunkelheit 
bringts halt auch nix.