Hallo zusammen,
weiss einer wie ein Zufallsprinzip bei einem Computer oder MP3 Player genau funktioniert? Ich meine solche Geräte besonders Computer arbeiten streng nach Berechnungen und ich frag mich wie das gehen soll oder wie das Programm für Zufälle genau aussieht. Interessiert mich irgendwie voll. Hab schon gegooglet und alles. Wär nett wenn ihr mir einen Link schicken könntet oder wenn ihr es selbst nicht wisst mich weiterleiten könnt. (ne einfache Erklärung wär toll^^)
Vielen Dank im Voraus
Uhr
Hallo Jamna,
beim PC ist es einfach. Einen Teil der Uhrzeit auslesen, die sich häufig ändert und je nach gewünschter Ziffernanzahl der Zufallszahl umrechnen, fertig. Der Zufall ist hier also die Zeit.
Bei den meisten MP3-Playern dürfte oft keine Uhr drin laufen, dann nimmt man halt mehrere Dinge, die sich öfters ändern können, z.B. ein paar Speicherinhalte aus Dateien * Batteriestandsanzeige * Einschaltzeit * Stromspar-Automatik-Ausschalttimer. Dürfte zufällig genug sein.
Gruß
Stefan
hi
ein computer kann von sich aus keine „echte“ zufallszahl erzeugen. statt dessen nimmt man eine spezielle funktion, die pseudozufallszahlen erzeugt.
funktioniert so: man nimmt einen startwert (eine sogenannte seed) und füttert damit die funktion. man erhält dabei einen wert retour. holt man sich die nächste „zufallszahl“, ruft man die funktion nochmal auf, diesmal mit dem zuletzt errechneten wert als parameter. du bekommst damit den nächsten wert.
die funktion zeichnet sich dadurch aus, dass die ergebnisse normal verteilt sind, d.h. alle möglichen werte gleich oft zurückgeliefert werden und dass die ergebnisse auf den ersten blick zufällig erscheinen (natürlich nur, solange man den code der funktion nicht kennt).
beispiel für eine normale verteilung: die funktion liefert üblicherweise einen wert zwischen 0 und 1 zurück. du willst nun einen würfel simulieren und nimmst daher das ergebis, multiplizierst mit 6, rundest ab und addierst eins. nun hast du einen wert von 1 bis 6. rufst du diese funktion nun 6000x auf, muss jeder deiner möglchen werte genau 6000mal gekommen sein. hast du z.b. mehr einsen als sechsen, war deine zufallszahl nicht normal verteilt und damit unbrauchbar.
konsequenz aus dem ganzen: rufst du zweimal hintereinander den zufallszahlengenerator mit genau der selben seed auf, erhältst du genau den selben wert retour. gehst du die kette weiter (d.h. zweite zufallszahl bekommt als parameter den ersten wert), erhältst du genau die selbe zahlenkette.
desshalb heisst das ganze auch pseudozufallszahl: auf den ersten blick erscheint es zufällig, die werte sind auch normal verteilt, wenn man den code aber kennt, dann sind die werte nicht zufällig sondern vorherberechenbar.
um wenigstens ein bischen zufall reinzubekommen, sind die meisten programme so geschrieben, dass sie die seed bei jedem programmaufruf variieren. meist wird die aktuelle uhrzeit genommen und mit zusätzlichen werten kombiniert (also mit rechnerid, datum, benutzerkennung oder ähnliches).
natürlich könnte man auf die idee kommen, bei jedem erzeugen einer zufallszahl eine neue seed zu nehmen. damit ist aber nicht mehr garantiert, das die werte normal verteilt sind - ein würfelprogramm, dass pro wurf eine neue seed nimmt, liefert möglicherweise mehr einsen als sechsen, was ja nicht erwünscht ist.
soviel mal zur grauen theorie.
in der praxis: wie genau dein spezielles programm funktioniert (ich nehme an, es geht um die zufällige playlist bei einem mp3-player), kann ich natürlich nicht sagen. es liegt aber im wesen einer guten zufallszahl, dass bei einer auswahl von 2 beliebigen titeln aus 1000 durchaus zweimal das selbe lied kommen kann. oder halt bei einer auswahl von fünf titeln fünf stücke des selben albums.
itunes von apple hat deshalb eine art „intelligenten“ zufallsgenerator. er stellt sicher, dass man niemals zweimal das selbe lied hintereinander hört. zusätzlich kann es sicherstellen, dass man niemals zwei lieder des selben albums hintereinander zu hören bekommt. sowas muss aber extra ausprogrammiert werden und ist unabhängig vom zufallsgeneratur dahinter.
technisch lässt sich das z.b. so lösen: du willst eine zufällige playlist deiner 1000 stücke erzeugen. zuerst erzeugst du eine temporäre liste deiner stücke. dann wählst du einen zufälligen titel aus dieser liste aus und stellst ihn an die erste stelle der playlist. der titel wird dann aus der temporären liste entfernt. dann wählst du den nächsten zufälligen titel aus der nur mehr 999 stücke langen liste aus usw. bis alle stücke aus der temporären liste entfernt wurden und die playlist 1000 stücke lang ist. der ipod geht ziemlich sicher so vor, da er im shuffle-modus die stücknummer „x von y“ anzeigt, also die stückliste vorgeneriert. weiteres indiz ist, dass man zurückblättern kann.
beantwortet das deine frage?
lg
erwin
ps: zufallszahlen spielen auch bei der verschlüsselung eine wichtige rolle. einige hersteller haben das prinzipielle problem mit den pseudozufallszahlen erkannt und bieten „echte“ zufallszahlen an. funktioniert in etwa so: ein stück draht mit einer bestimmten temperatur hat einen bestimmten widerstand - allerdings ist dieser widerstand nicht fix sondern variiert immer um einen mittelwert herum. wenn man nun den genauen widerstand misst, erhält man sowas wie zufallszahlen: werte, die normal verteilt sind, allerdings mit dem vorteil, dass der dahinterliegende berechnungsalgorythmus nicht bekannt ist (nicht mal dem hersteller selbst, da es ja ein physikalischer effekt ist). man erhält damit „echte“ zufallszahlen.
neuere prozessoren bzw. motherboards, die das drm unterstützen (stichwort paladium) beinhalten meist auch einen speziellen chip, der aufgrund physikalischer effekte echte zufallszahlen erzeugen kann.
Ja ich bin begeistert^^ ,das beantwortet meine Frage (ich habe mir diese Frage zufällig auch gestellt weil ich früher bei meinem MP3 Player auch das Phänomen beobachtet habe das 2x das geliche Lied hintereinander kam, und ich nun einen iPod besitze und das noch niemals vorgekommen ist, das da irgendwas anders ist und es verschiedene Zufallsprinzipien geben muss).
Ich hatte schon ein paar Vermutungen angestellt, aber diese Erklärungen mit Uhrzeiten und so klingen natürlich logisch.
Und das mit den Widerständen kann ich auch nachvollziehen, ich besuche nämlich das technische Gymnasium mit Schwerpunkt Elektrotechnik.
Könnte man nun auch solche Zufallsfunktionen berechnen wenn man die Werte hat die rauskommen? (wenn man nun die neue technick mit den widerständen rauslässt) Dann könnte man ja quasi bei z.B. Pokerspielen oder ähnlichem wo die karten ja auch zufällig gegeben werden berechnen welche karten die anderen halten? (rein theoretisch, ich bin auch nicht in poker interessiert aber nur vom prinzip her)
Jo danke werd mich mal durchlesen, aber so wies aussieht viel Mathematik, aber in der Mathematik gibt es ja eigentlich keine Zufälle.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hi Malte,
Ja ich bin begeistert^^ ,das beantwortet meine Frage (ich habe
mir diese Frage zufällig auch gestellt weil ich früher bei
meinem MP3 Player auch das Phänomen beobachtet habe das 2x das
geliche Lied hintereinander kam, und ich nun einen iPod
besitze und das noch niemals vorgekommen ist, das da irgendwas
anders ist und es verschiedene Zufallsprinzipien geben muss).
Ich bin da Laie, aber wenn ich aus 1000 Titeln einen auswähle und ihn dann aus der nächsten Auswahl streiche so hat das m.E. nix mit dem Zufallsprinzip zu tun.
Zufallsprinzip bedeutet für mich, jeder beliebige Titel kann nacheinander kommen, zur Not auch der Gleiche 10mal nacheinander.
Egal mit welcher Programmsprache, wenn du die einzelnen Pixel eines Bildschirm per Zufallsprinzip, also mit RNd() o.ä, farbig erscheinen läßt und du erkennst optisch ein Muster darin, so taugt die Software des RND-Befehls nicht um echte „zufällige“ Zahlen zu erzeugen, d.h. völlig unbrauchbar z.B. für Banken um damit Kunden ihre Geheimzahl zuzuweisen.
Ich bräuchte da alle vorhanden Scheckkarten samt Geheimzahl und auch dann würde ich nie auf das benutzte Zufallsprinzip kommen *schätz*
Aber Leuten, die sich damit auskennen, oder Geld haben um sich Leute zu leisten, zu fördern, auszubilden, die Ahnung haben (nicht nur die Mafia), denen langen relativ wenige geklaute Kreditkarten samt Geheimzahl um auf den „Schlüssel“ zu kommen.
Und da in den letzten Jahren einige tausend Geldautomaten Europaweit komplett geklaut wurden, sicher, die Masse wollten nur den Geldinhalt, aber auch einige interessierten sich auch sehr für die Software des Geldautomatens, grad bei denen die nicht online zur Hauptfiliale waren sondern selbst entschieden ob die Geheimnummer zur Karte passt.
Naja, jetzt habe ich mich verzettelt, jedenfalls, den Datumsstempel auszulesen, Anzahl der Dateien zu zählen, den Usernamen miteinzubeziehen, sonstwas miteinzubeziehen, für Normalsterbliche völlig Zufälliges, reicht als völlig zufällige Zahl anscheinend nicht aus.
Genaueres wissen Sicherheitsexperten, ich never:smile:
Ich habe jetzt nur „beiläufig Mitgelesenes“ präsentiert und wollte es diesem Thread beisteuern.
Gruß
Reinhard
Ich hatte schon ein paar Vermutungen angestellt, aber diese
Erklärungen mit Uhrzeiten und so klingen natürlich logisch.
Und das mit den Widerständen kann ich auch nachvollziehen, ich
besuche nämlich das technische Gymnasium mit Schwerpunkt
Elektrotechnik.Könnte man nun auch solche Zufallsfunktionen berechnen wenn
man die Werte hat die rauskommen? (wenn man nun die neue
technick mit den widerständen rauslässt) Dann könnte man ja
quasi bei z.B. Pokerspielen oder ähnlichem wo die karten ja
auch zufällig gegeben werden berechnen welche karten die
anderen halten? (rein theoretisch, ich bin auch nicht in poker
interessiert aber nur vom prinzip her)
ps: zufallszahlen spielen auch bei der verschlüsselung eine
wichtige rolle. einige hersteller haben das prinzipielle
problem mit den pseudozufallszahlen erkannt und bieten „echte“
zufallszahlen an. funktioniert in etwa so: ein stück draht mit
einer bestimmten temperatur hat einen bestimmten widerstand -
allerdings ist dieser widerstand nicht fix sondern variiert
immer um einen mittelwert herum. wenn man nun den genauen
widerstand misst, erhält man sowas wie zufallszahlen: werte,
die normal verteilt sind, allerdings mit dem vorteil, dass der
dahinterliegende berechnungsalgorythmus nicht bekannt ist
(nicht mal dem hersteller selbst, da es ja ein physikalischer
effekt ist). man erhält damit „echte“ zufallszahlen.
Auf dem C64 hatte ich das Problem, dass die dort erzeugten Zufallszahlen immer identische Ketten lieferten und auch eine Manipulation mit der Uhrzeit das Problem nicht prinzipiell gelöst hat. Ich habe mir damit beholfen, dass ich zusätzlich die Position des gerade durchlaufenen Bildpunktes im Grafikchip ausgewertet und in die Ermittlung der Zufallszahl einbezogen habe. Ob Grafikchip und Prozessor wirklich hinreichend unabhängig gelaufen sind, ‚echten‘ Zufall zu produzieren, weiss ich nicht, für meine Zwecke jedenfalls war das Ergebnis hinreichend.
Gruss
Schorsch
hallo nochmal
wie schon erklärt: wenn ich weiss, welche algorythmus ein programm verwendet um pseudozufallszahlen zu erzeugen und ich zusätzlich den startwert (also die seed) kenne, kann ich alle werte, die das programm generieren wird, eindeutig vorhersagen.
grundsätzlich ist es auch möglich, von den ersten paar werten auf die seed zurückzuschließen. das problem dabei ist aber wieder der zufall (wenn auch nur pseudomässig): nur weil die ersten 10 werte, die das programm liefert meinen ersten 10 vorhergesagten werden entspricht, heisst das noch lange nicht, dass ich die richtige seed gewählt habe. es kann lediglich sein, dass mit meiner seed halt die ersten 10 zeichen identisch mit einer anderen seed sind, danach aber plötzlich die werte total abweichen.
natürlich kann man die anzahl der werte, die verglichen werden, erhöhen - nur wie lange? irgendwann muss schluss sein, da man nicht unendlich lange zahlenfolgen vergleichen kann.
habe ich ausreichend werte und einen schnellen rechner, kann ich eine menge an wahrscheinlichen seeds ermitteln, die je nach ausgewerteter menge unterschiedlich lange ist. mit diesem wissen kann ich quasi vorhersagen, wie mein programm als nächstes reagieren wird, obwohl es zufallszahlen verwendet.
vereinfacht wird die sache, wenn man weiss, wie das programm seine seed berechnet. vor zig-jahren gab es mal den urvater aller tetris-programme: das vom russischen erfinder erstellte und an westliche computer angepasste programm hat offenbar für die seed nur den sekundenteil der aktuellen uhrzeit oder was ähnlich unspäktakuläres verwendet. jedenfalls gab es einige spiele, in denen immer wieder die selben steine in genau der selben reihenfolge kamen. wenn man so wie ich eine zeit lang tetris-süchtig war, konnte man diese reihenfolge bald auswendig und daher bei so einem spiel die ersten paar minuten schon fast blind spielen.
aufgrund der leistungsfähigkeit moderner pcs (übersteigt teilweise die leistung von supercomputern vor 10 jahren) kann man bei schlecht gewählten seeds relativ schnell die zahlenfolge vorhersagen. v.a. bei verschlüsselungen, wo massiv gebrauch von zufallszahlen gemacht wird, ist das natürlich der tod der verschlüsselung, da man das ganze relativ schnell knacken kann. nicht umsonst wird in den modernen crypto-chips eben ein hardware-zufallsgenerator verbaut, der nur desshalb nicht vorhergesagt werden kann, weil die dahinterliegenden physikalischen prinzipien derart komplex sind, dass sie uns als zufällig erscheinen (ok - ist definitionssache. waschechte physiker behaupten natürlich, das prinzip genau zu kennen und behaupten, dass einige vorgänge vom zufall abhängig sind. es kommt halt immer darauf an, wie man zufall definiert).
beim poker kommen noch ein paar andere faktoren dazu. wesentlich ist ja, dass man meist solange vom selben stapel abhebt, bis alle karten weg sind und erst dann neu mischt (es gibt aber ca. eine million verschiedener pokerregeln und ich habe nur sehr wenig ahnung davon). zum zufallseffekt kommt also noch eine statistik-rechnung, risikoanalyse und ausschluss-verfahren (karten, die schon mal gekommen sind, kann ich nicht neu bekommen) dazu. und mit dem richtigen poker-face kann man schon etwas nachhelfen…
lg
erwin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Auf dem C64 hatte ich das Problem, dass die dort erzeugten
Zufallszahlen immer identische Ketten lieferten und auch eine
Manipulation mit der Uhrzeit das Problem nicht prinzipiell
gelöst hat. Ich habe mir damit beholfen, dass ich zusätzlich
die Position des gerade durchlaufenen Bildpunktes im
Grafikchip ausgewertet und in die Ermittlung der Zufallszahl
einbezogen habe. Ob Grafikchip und Prozessor wirklich
hinreichend unabhängig gelaufen sind, ‚echten‘ Zufall zu
produzieren, weiss ich nicht, für meine Zwecke jedenfalls war
das Ergebnis hinreichend.
immer brav mit randomize gearbeitet? ansonsten verwendest du immer die selbe seed, was natürlich in identischen ketten resultiert.
lg
erwin
immer brav mit randomize gearbeitet? ansonsten verwendest du
immer die selbe seed, was natürlich in identischen ketten
resultiert.
C64-Basic kannte, wenn ich mich recht erinnere (und wenn das gerade heruntergeladene Handbuch nicht lügt), ausschliesslich die RND(x)-Funktion mit -1
Hallo,
Das Erzeugen von guten Pseudozufallszahlen ist eine Kunst und eine Wissenschaft. Es gibt viele verschiedene Algorithmen, Folgen von Pseudo-Zufallszahlen zu generieren. Hier sind einige:
„Wichmann-Hill“, „Marsaglia-Multicarry“, „Super-Duper“, „Mersenne-Twister“, „Knuth-TAOCP“, „Knuth-TAOCP-2002“, …
Jeder hat seine eigenen Vor- und Nachteile.
Hier noch ein paar Quellenangaben, zum nachlesen:
Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988) The New S Language. Wadsworth & Brooks/Cole.
Wichmann, B. A. and Hill, I. D. (1982) Algorithm AS 183: An Efficient and Portable Pseudo-random Number Generator, Applied Statistics, 31, 188–190; Remarks: 34, 198 and 35, 89.
De Matteis, A. and Pagnutti, S. (1993) Long-range Correlation Analysis of the Wichmann-Hill Random Number Generator, Statist. Comput., 3, 67–70.
Marsaglia, G. (1997) A random number generator for C. Discussion paper, posting on Usenet newsgroup sci.stat.math on September 29, 1997.
Reeds, J., Hubert, S. and Abrahams, M. (1982–4) C implementation of SuperDuper, University of California at Berkeley.
Marsaglia, G. and Zaman, A. (1994) Some portable very-long-period random number generators. Computers in Physics, 8, 117–121.
Matsumoto, M. and Nishimura, T. (1998) Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation, 8, 3–30. Source code unter http://www.math.keio.ac.jp/~matumoto/emt.html.
Knuth, D. E. (1997) The Art of Computer Programming. Volume 2, third edition. Source code unter http://www-cs-faculty.stanford.edu/~knuth/taocp.html.
Knuth, D. E. (2002) The Art of Computer Programming. Volume 2, third edition, ninth printing. Siehe http://Sunburn.Stanford.EDU/~knuth/news02.html.
Kinderman, A. J. and Ramage, J. G. (1976) Computer generation of normal random variables. Journal of the American Statistical Association 71, 893-896.
Ahrens, J.H. and Dieter, U. (1973) Extensions of Forsythe’s method for random sampling from the normal distribution. Mathematics of Computation 27, 927-937.
Box, G.E.P. and Muller, M.E. (1958) A note on the generation of normal random deviates. Annals of Mathmatical Statistics 29, 610–611.
Viel Spaß,
Jochen