|
|
|
interner Algorithmus rand(1,1) |
|
| Janno |
Gast
|
 |
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 24.08.2012, 13:38
Titel: interner Algorithmus rand(1,1)
|
 |
Hallo,
ich benutze die Funktion rand(1,1) und wollte gerne wissen, wie diese in MATLAB implementiert ist.
Ich weiß zum Beispiel, dass die C++ Random Funktion in der Standard-Bibliothek unter Windows nicht sehr gut ist. Selbst bei 10.000facher Ausführung bei Integer, hat man ein paar Zahlen mindestens doppelt (Wissensstand: 2009). Das kann bei einem 32-Bit Integer eigentlich unmöglich sein.
Wenn man die gleiche Funktion unter Linux ausführt, hat man nicht solche Probleme.
Ist ein ähnliches Problem bei der rand(m,n) Funktion in MATLAB unter Windows bekannt?
cu
Jan
|
|
|
|
|
|
| flashpixx |
Forum-Guru
|
|
Beiträge: 355
|
|
|
|
Anmeldedatum: 19.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 14:06
Titel:
|
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.448
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 15:08
Titel:
|
|
Hallo,
ich habs ein paar Mal ausprobiert, und bekomme mit
einen Vektor gleicher Länge, d.h. [wie erwartet] keine doppelten Zahlen 
Grüße,
Harald
|
|
|
|
| flashpixx |
Forum-Guru
|
|
Beiträge: 355
|
|
|
|
Anmeldedatum: 19.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 15:41
Titel:
|
|
| Harald hat Folgendes geschrieben: |
einen Vektor gleicher Länge, d.h. [wie erwartet] keine doppelten Zahlen
|
recht naiv, nimm mal einen Vektor der doppelten Größe der Periode des Mersenne-Twister, da wirst Du dann definitive doppelte Zahlen drin haben (Stichprobengröße)
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.448
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 16:17
Titel:
|
|
Hallo flashpixx,
die ungefähre Periode von Mersenne-Twister ist laut Doku 2^19937-1.
http://www.mathworks.com/help/relea...../ref/randstream.list.html
So viele Zufallszahlen werde ich in meiner Lebenszeit sicher nicht erzeugen. Für den vorliegenden Fall spielt diese Periode jedoch wohl keine Rolle, da es ja um doppelte Zahlen und nicht doppelte / wiederkehrende Sequenzen geht. Vielleicht meinst du aber auch eine andere Periode?
In meinem Beitrag ging es mir nicht um eine wissenschaftliche Erklärung, sondern nur um einen kleinen Test. Es würde mich nicht überraschen, wenn dieser Test recht oft klappt. Ebensowenig würde mich nicht überraschen, wenn er irgendwann mal nicht klappt.
Grüße,
Harald
P.S. an den Themenstarter: geht es nun um rand (gleichverteilte Doubles) oder um Integers?
|
|
|
|
| flashpixx |
Forum-Guru
|
|
Beiträge: 355
|
|
|
|
Anmeldedatum: 19.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 16:48
Titel:
|
|
| |
 |
 |
| Harald hat Folgendes geschrieben: |
In meinem Beitrag ging es mir nicht um eine wissenschaftliche Erklärung, sondern nur um einen kleinen Test. Es würde mich nicht überraschen, wenn dieser Test recht oft klappt. Ebensowenig würde mich nicht überraschen, wenn er irgendwann mal nicht klappt.
|
Das stimmt schon, rein vom theoretischen Aspekt ist die Wahrscheinlichkeit nicht 0, dass wenn ich jetzt n verschiedene Zahlen erzeuge keine doppelten drin sind. Es ist eben nur recht unwahrscheinlich. Das wollte ich auch sagen, also sprich einen Test, der einfach zählt wie oft gleiche Zahlen in einer erzeugten Stichprobe vorkommen, ist sicherlich nicht aussagekräftig. Zusätzlich entsteht ja der Effekt, da der Pseudogenerator letztendlich nur Bitsequenzen erzeugt, dass man hier gerade wenn man mit Fließkommazahlen arbeitet die Maschinenungenauigkeit beachten muss.
Gerade für sicherheitskritische Anwendungen würde ich keinen Pseudogenerator verwenden
Aber bezüglich Zufallszahlen, da es ja hier auch um die entsprechende C-Funktion ging. Ich würde ggf überlegen, auch wenn der Mersenne-Twister sehr gute Zahlen liefert, ob man nicht einen "echten physikalischen Zufallsgenerator" verwendet wie z.B. http://de.wikipedia.org/wiki/Rauschgenerator
In Software kann man das z.B. via http://www.boost.org/doc/libs/1_51_.....m_random_number_generator direkt abgreifen und dann entsprechende Zahlen erzeugen.
|
|
|
|
| Janno |
Gast
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 17:52
Titel: Danke
|
|
Danke für die zahlreichen Antworten.
Ich werde dann garnichts an den Einstellung rumspielen und 1e6 mal rand(1,1) nacheinander für mein Zufallsexperiement ausführen 
Danke
Jan
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.448
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 18:05
Titel:
|
|
Hallo,
@ flashpixx:
Mir ist bis jetzt noch keine Anwendung vorgekommen, in der Mersenne-Twister nicht ausgereicht hätte. Bei sicherheitskritischen Anwendungen sehe ich Zufallszahlen eher im Bereich des Testens; der Ablauf an sich sollte wohl nicht dem Zufall überlassen sein. Für das Testen würde ich persönlich allerdings sorgfältig gewählte Testszenarios von Extremfällen bevorzugen.
@ janno:
Wenn möglich solltest du 1 Mio. Zufallszahlen am Stück erzeugen und diese vektorisiert verarbeiten. Das kann das ganze deutlich beschleunigen.
Grüße,
Harald
|
|
|
|
| flashpixx |
Forum-Guru
|
|
Beiträge: 355
|
|
|
|
Anmeldedatum: 19.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 18:35
Titel:
|
|
| |
|
|
| Harald hat Folgendes geschrieben: |
Mir ist bis jetzt noch keine Anwendung vorgekommen, in der Mersenne-Twister nicht ausgereicht hätte. Bei sicherheitskritischen Anwendungen sehe ich Zufallszahlen eher im Bereich des Testens |
Bei einem Pseudozufallsgenerator wird anhand der Initialisierung die Zufallsfolge erzeugt. Da hinter dem Generator eine Funktion steht, ist die Zufallsfolge deterministisch.
Initialisiere ich den Generator mit einem Wert, dann kann ich mir immer wieder die gleiche Zahlenfolge erzeugen, sofern mir dieser Wert (Seed) bekannt ist.
In den meisten Fällen nutzt man die Uhrzeit (Unixtimestamp) als Initialisierung.
Gerade aus eigenerer Erfahrung kann ich sagen, dass man z.B. dabei sehr aufpassen muss, denn wenn ich den Generator z.B. in mehreren Threads verwende, dann kann ich, wenn ich in jedem Thread den initialisiere durchaus der Fall auftreten, dass zwei Generatoren die gleiche Folge erzeugen, denn der Seed wird in beiden Threads auf den gleichen Startwert gesetzt. Analog verhält es sich in Cluster-Umgebungen, denn die Systeme werden meist via NTP zeitlich synchronisiert, so dass ich überall den gleichen Seed habe.
In diesen Fällen muss man eben sicherstellen, dass der Seed überall unterschiedlich ist oder eben mit einem physikalischen Generator arbeiten.
Die Problematik mit dem Seed kann man aber auch weiter gehen, denn viele Algorithmen im Sicherheitsbereich arbeiten mit Zufallsfolgen, d.h. wenn mir als Angreifer der Seed und der Algorithmus (diese sind ja meist offen zugänglich) bekannt sind, dann kann ich mir die gleichen Zahlenfolgen erzeugen und so Schlüssel kompromittieren. Ich arbeite eben mit einem nicht-determinisitschen Algorithmus (jedenfalls außerhalb von Matlab)
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.448
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 21:07
Titel:
|
|
| |
|
|
Hallo,
| Zitat: |
Bei einem Pseudozufallsgenerator wird anhand der Initialisierung die Zufallsfolge erzeugt. Da hinter dem Generator eine Funktion steht, ist die Zufallsfolge deterministisch.
Initialisiere ich den Generator mit einem Wert, dann kann ich mir immer wieder die gleiche Zahlenfolge erzeugen, sofern mir dieser Wert (Seed) bekannt ist.
In den meisten Fällen nutzt man die Uhrzeit (Unixtimestamp) als Initialisierung. |
Ist mir bekannt, und ich sehe es nicht als Problem an.
| Zitat: |
Gerade aus eigenerer Erfahrung kann ich sagen, dass man z.B. dabei sehr aufpassen muss, denn wenn ich den Generator z.B. in mehreren Threads verwende, dann kann ich, wenn ich in jedem Thread den initialisiere durchaus der Fall auftreten, dass zwei Generatoren die gleiche Folge erzeugen, denn der Seed wird in beiden Threads auf den gleichen Startwert gesetzt. Analog verhält es sich in Cluster-Umgebungen, denn die Systeme werden meist via NTP zeitlich synchronisiert, so dass ich überall den gleichen Seed habe.
In diesen Fällen muss man eben sicherstellen, dass der Seed überall unterschiedlich ist oder eben mit einem physikalischen Generator arbeiten. |
Das zumindest sollte kein Problem sein, da man ja in Abhängigkeit von Systemzeit und Threadnummer initialisieren kann. Beispielsweise
| Zitat: |
| Die Problematik mit dem Seed kann man aber auch weiter gehen, denn viele Algorithmen im Sicherheitsbereich arbeiten mit Zufallsfolgen, d.h. wenn mir als Angreifer der Seed und der Algorithmus (diese sind ja meist offen zugänglich) bekannt sind, dann kann ich mir die gleichen Zahlenfolgen erzeugen und so Schlüssel kompromittieren. |
Unter "sicherheitskritisch" verstand ich nun eher Flugzeuge o.ä. Ja, der Zufallszahlengenerator ist deterministisch, und es sollte jedem klar sein, dass eine Folge von Zufallszahlen in dem Fall nur so sicher wie der Seed ist. Ich wage aber zu behaupten, dass das sehr spezielle Anwendungen sind und 99,9% der Anwender sich darum keine Sorge machen müssen - inkl. des Fragestellers, der von Experimenten spricht.
Grüße,
Harald
|
|
|
|
| flashpixx |
Forum-Guru
|
|
Beiträge: 355
|
|
|
|
Anmeldedatum: 19.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 21:41
Titel:
|
|
| |
|
|
| Harald hat Folgendes geschrieben: |
Unter "sicherheitskritisch" verstand ich nun eher Flugzeuge o.ä. Ja, der Zufallszahlengenerator ist deterministisch, und es sollte jedem klar sein, dass eine Folge von Zufallszahlen in dem Fall nur so sicher wie der Seed ist. Ich wage aber zu behaupten, dass das sehr spezielle Anwendungen sind und 99,9% der Anwender sich darum keine Sorge machen müssen |
Man benutzt es durchaus jeden Tag selbst, sobald man eine SSL (HTTPS) Verschlüsselung verwendet, also ist die Aussage, dass er "nur sehr spezielle Anwendungen sind" durchaus falsch, denn es sind keine sehr speziellen Anwendungen, es sind durchaus Anwendungen, die jeden Tag sehr oft verwendet werden.
Ob man sich nun im Detail mit der Erzeugung von solchen Zahlen beschäftigen muss, ist eine andere Frage. Aber sobald man zufallsbasierte Algorithmen verwendet, sollte man durchaus die Schwächen dieser Pseudozufallsgeneratoren kennen, damit man eben nicht leichtfertig die Zahlen verwendet. Gerade im C/C++ Bereich kann man damit sich durchaus Probleme einhandeln. In Matlab sofern man den Seed nicht selbst setzt, eher weniger.
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.448
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 24.08.2012, 23:09
Titel:
|
|
Hallo flashpixx,
mit "Anwendern" meine ich logischerweise die MATLAB-Nutzer, insbesondere die in diesem Forum. Also nicht die Leute, die etwas verwenden, sondern die, die es programmieren, und das in MATLAB.
Grüße,
Harald
|
|
|
|
| Jan S |
Moderator
|
|
Beiträge: 11.057
|
|
|
|
Anmeldedatum: 08.07.10
|
|
|
|
Wohnort: Heidelberg
|
|
|
|
Version: 2009a, 2016b
|
|
|
|
|
|
|
Verfasst am: 25.08.2012, 23:45
Titel:
|
|
| |
|
|
Hallo Harald, hallo flashpixx,
Ohne Zweifel wird der Mesenne-Twister (MT) in den allermeisten Fällen hinreichend zufällig sein. Dazu findet man hinreichend viele Veröffentlichungen. Der Algorithmus wird auch für Monte-Carlo-Simulationen im Flugzeugbau verwendet.
Weiterhin ist es auch klar, dass die Wahl eines triviales Seeds wie der Uhrzeit nicht ausreicht, um unabhängige Simulationen in einen Cluster zu starten. Die Thread-Nummer ist zwar eine sinnvolle Idee. Mehr Entropie erhält man, indem man die Seeds zunächst in einem Thread produziert, wobei natürlich flashpixx' Vorschlag eine nicht-Pseudo-Random-Quelle zu wählen. Siehe hierzu z.B. die FileExchange Beiträge, die auf z.B. auf www.random.org zugreifen. Der verwendete Web-Service limitiert allerdings die Menge an Bits, die man pro Tag und TCP/IP herunterladen darf. Also wäre dies für einen Seed hinreichend, aber nicht um 1e6 Zufallszahlen zu erhalten.
Eine vom Betriebssystem erzeugte GUID wäre eine Alternative.
Ein billiger 32-Bit Seed ist für viele Aufgaben zu schwach: Wenn man z.B. zufälliger Permutationen eines Vektors mit mehr 12 Elementen erhalten möchte, limitiert ein 32-Bit-Seed die Menge der möglichen Lösungen bereits deutlich. Ab einer Vektorlänge von 1830 sind auch die 625*32 Bits des internen Zustands des MT nicht mehr ausreichen für eine Permutation ohne Bias. Es ist allerdings nicht einfach, diesen Bias zu bemerken.
Natürlich muss ein guter Zufallszahlen-Generator auch Zahlen doppelt ausgeben bevor die Perioden-Länge erreicht ist. Andernfalls würde die Zufälligkeit gegen Ende der Periode messbar abnehmen. Die meisten Generatoren, wie z.B. auch der MT, erzeugen 32-Bit Integers. Es ist offensichtlich, dass sich hier Werte wiederholen müssen, bevor die Periodenlänge erreicht wird.
Für kryptographische Probleme ist der MT ungeeignet, siehe WikiPedia: Mersenne_Twister und die Original-FAQ. Da nützt auch ein guter Seed nichts. SSL-Implementierungen sollten deshalb unbedingt andere Generatoren verwenden.
| flashpixx hat Folgendes geschrieben: |
| Gerade im C/C++ Bereich kann man damit sich durchaus Probleme einhandeln. In Matlab sofern man den Seed nicht selbst setzt, eher weniger. |
Das kann ich nicht nachvollziehen. Matlab nutzt eine C++-Bibliothek für den MT, so dass es da keine Unterschiedlichen Probleme geben kann.
Aber ich klann nur zustimmen, dass man die Spezifikationen und vor allem auch die Schwächen der Zufallszahlengeneratoren kennen sollte, wenn man sie wissenschaftlich benutzt. Das trifft auf ODE-Integratoren ebenfalls zu. Und wenn ich an die immer wieder gestellten Fragen zum Thema 0.1+0.2-0.3 ~= 0 denke, sollte man sich bereits über die numerische Implementierung von Addition und Subtraktion von Fließkommazahlen umfassend informieren.
@Janno: RAND ist hinreichend zuverlässig. Für Kryptographie jedoch nicht. Die Details dazu findest Du mit "doc randstream".
Gruß, Jan
Zuletzt bearbeitet von Jan S am 26.08.2012, 00:14, insgesamt einmal bearbeitet
|
|
|
|
| flashpixx |
Forum-Guru
|
|
Beiträge: 355
|
|
|
|
Anmeldedatum: 19.04.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 26.08.2012, 00:11
Titel:
|
|
| |
|
|
| Jan S hat Folgendes geschrieben: |
Das kann ich nicht nachvollziehen. Matlab nutzt eine C++-Bibliothek für den MT, so dass es da keine Unterschiedlichen Probleme geben kann.
|
Matlab nutzt die Boost Random Bibliothek, die ich verlinkt habe. Ich habe mich bei der Aussage auf den Seed bezogen, wenn ich in Matlab nichts weiter vorgebe, dann setzt ihn Matlab für mich. Wenn ich einen Pseudozufallsgenerator z.B. in C/C++ verwende, dann muss natürlich selbst für den Seed sorgen, wobei eben die Probleme mit dem Thread o.ä. auftreten. Das Problem bezüglich der Seed Initialisierung ist, dass z.B. die GUID Implementierung OS abhängig ist, d.h. bei crossplattformen Codes muss dies dann entsprechend für jedes OS codiert werden.
Ich habe mit der C rand Funktion bei genetischen Algorithmen das Problem gehabt, dass diese nicht konvergiert sind. Ich nutzt primär eigentlich den in der Boost vorhandenen nicht-deterministischen Generator. Der Vorteil der dort besteht ist, dass man sich eben um die eigentliche OS Anbindung nicht kümmern muss, sondern ihn direkt so verwenden kann. Falls ich einen Pseudozufallsgenerator setze, dann initialisiere ich den Seed mit Hilfe einer statischen Variablen, also einmalig beim Start des Programms, so dass hier keine Threadabhängigkeit besteht.
Falls man in Matlab einen nicht-deterministischen Generator braucht, sollte es ja kein Problem sein, diesen aus der Boost mit Hilfe von Mex sich in Matlab verfügbar zu machen.
|
|
|
|
|
|
|
Einstellungen und Berechtigungen
|
|
Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
|
|
