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
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
@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!
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.
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).
@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
@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
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
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.
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 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
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
> 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.
>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
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
1
// init PRNG, load last seed from EEPROM, calculate next seed and store back to EEPROM, use another polynom as in lfsr()
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
<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>
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.