Hallo Leute, Will in meinen Geräten (zwecks Softwarezuordnung) eine 4 Byte Zufallszahl integrieren. Wie hoch ist die Wahrscheindlichkeit, das sich diese zufällig wiederholt? Festgelegt wird die Zahl über die RND Funktion von VB2008.
Man muss hinsichtlich der Kollionswahrscheinlichkeit zwei Fälle unterscheiden: 1. Wie wahrscheinlich ist es, dass eine bestimmte Zahl mehrfach auftritt? 2. Wie wahrscheinlich ist es, dass eine beliebige Zahl mehrfach auftritt? Die schon gegebene Antwort behandelt nur Fall 1, wohingegen bei Fall 2 das Geburtstagsparadoxon gilt. Zwar hat der Ursprungsautor seine Aufgabenstellung nicht hinreichend präzise formuliert, aber von der typischen Art dieser Aufgabe nehme ich an, dass eher Fall 2 anzuwenden ist.
Maximum: 1 zu 2^4 Minimum: 1 zu 1 Da es auf einem PC kein Größe gibt, die wirklich Zufällig ist, wird die Zeit, die der PC läuft, als Startwert der Zufallsfunktion genutzt. (es sei den du gibst was anderes an). Wenn Du Pech hast und genau die Gleiche Zeit erwischt erhältst Du den gleichen Wert. http://msdn.microsoft.com/de-de/library/f7s023d2%28v=vs.90%29.aspx#Y729 Nimm lieber eine fortlaufende Seriennummer. Volker
@Volker : 4 BYTE und nicht 4 BIT ! ausserdem macht man zu programmstart ein Randomize() / Randomize(timer) dass ein programm 2 mal zur selben zeit gestartet wird ist eher unwahrscheinlich.. @Andreas: für fall 2 bräuchte man eine zusätzliche angabe (z.b. die anzahl an zufallszahlen die man braucht..)
Sepp der Grosse schrieb: > Will in meinen Geräten (zwecks Softwarezuordnung) eine 4 Byte > Zufallszahl integrieren. Nimm doch einen Hash-Wert von der Seriennummer. Das ist übersichtlicher als wilde Zufallszahlen.
Sepp der Grosse schrieb: > Wie hoch ist die Wahrscheindlichkeit, das sich diese zufällig wiederholt? Eine 32-Bit Zufallszahl wiederholt sich, wenn sie mit einem LFSR ermittelt wird, bei einem brauchbaren Polynom nach genau 2^32-1 Abfragen. Eine 0 kommt nicht vor: http://www.lothar-miller.de/s9y/categories/38-LFSR Die Reihenfolge ist zwischen diesen Wiederholungen exakt gleich. Allerdings gibt es auch noch andere Verfahren, Zufallszahlen auszurechnen. Wie gut oder schlecht die VB Funktion ist, kann ich nicht sagen.
lrlr schrieb: > 4 BYTE und nicht 4 BIT ! Tschuldigung, war ein Tippfehler, sollte 64 heißen. Ansonsten ist es ein typischer Fall der Risikobewertung. Nicht nur die Häufigkeit eines Fehlers, auch die möglichen Folgen sind zu Betrachten, ob eine Sache akzeptable ist. Sollten durch den Fehler zwei Modelbahnampeln gleichzeitig Grün zeigen, ist das nur optische Unschön. Fliegen zwei A380 auf dem gleichen Kurs(weil gleiche ID) ist es alles andere als Unschön. http://de.wikipedia.org/wiki/Risikomatrix volker
> sollte 64 heißen.
ist ja wie am türkischen basar..
treffen wir uns in der mitte, dann passt es..
Hallo, ich habe mich zwar mit irgendwelchen Formeln da nie rumgeschlagen, aber wenn ich den (Pseudo-)-Zufallszahl-Generator einmal mit einer Seed gestartet ist, kann die gleiche Zahl doch auch direkt hintereinander kommen? Gruß aus Berlin Michael
Michael U. schrieb: > kann die gleiche Zahl doch auch direkt hintereinander kommen? Nicht bei den üblichen Algorithmen.
Sepp der Grosse schrieb: > Wie hoch ist die Wahrscheindlichkeit, das sich > diese zufällig wiederholt? Festgelegt wird die Zahl über die RND > Funktion von VB2008. 100% RND liefert immer die gleiche Folge von Zufallszahlen. Deshalb heißt es auch nur Pseudo-Zufall. Du brauchst einen echten Zufallswert, welcher den Startwert von RND festlegt. Aber dann kannst Du ihn ja gleich nehmen. Einen echten Zufall zu erzeugen, ist sehr schwer. Man könnte einen Timer mit hoher Frequenz laufen lassen und den Nutzer per Tastendruck einen Interrupt ausführen lassen. Der Nutzer ist mit ziemlicher Sicherheit asynchron zum CPU-Takt. Allerdings können Interrupts auch nicht zu jedem CPU-Zyklus ausgeführt werden, sondern Befehle und andere Interrupts müssen beendet sein. Dieser Zufall ist also auch nicht wirklich gleichverteilt. Am besten ist daher ein Input-Capture-Interrupt, der zyklusgenau den Zeitstempel des Tastendrucks speichert. Windows selber kann keinen Zufall erzeugen, alles ist ja mit dem CPU-Takt synchron. Man braucht 2 voneinander unabhängige Takte. Man könnte mit Google nach einem Begriff suchen und dann die Zeitdauer und die (hohe) Trefferanzahl verarbeiten. Das dürfte recht zufällig sein, wenn man das einen Tag später wiederholt. Peter
Nimm doch nen Maxim Seriennummer-IC, die haben ne weltweit einmalige 6Byte-ID. Peter
Lothar Miller schrieb: > Michael U. schrieb: >> kann die gleiche Zahl doch auch direkt hintereinander kommen? > Nicht bei den üblichen Algorithmen. Dann sind diese Algorithmen aber schlecht. Die Wahrscheinlichkeit sollte für jede beliebige Zahl identisch sein, unabhängig davon, wann sie schon mal erwürfelt wurde oder nicht.
Sepp der Grosse schrieb: > Will in meinen Geräten (zwecks Softwarezuordnung) eine 4 Byte > Zufallszahl integrieren. Da du die Zufallszahlen als Identifikationsnummern nutzen möchtest, wirst du sie wahrscheinlich in einer Datenbank o.ä. zusammen mit anderen Infromationen zum Produkt registrieren. Um zu vermeiden, dass zweimal die gleiche Zahl auftritt, brauchst du ja nur in der Datenbank nachzuschauen (oder durch ein Tool nachschauen lassen), ob die Zahl schon verwendet wird und ggf. eine neue Zufallszahl generieren. Aber viel besser ist doch das: Volker Zabe schrieb: > Nimm lieber eine fortlaufende Seriennummer. Wenn der Endanwender aus der Nummer die Seriennummer nicht rekonstruieren können soll, kannst ja noch dies tun: Tip schrieb: > Nimm doch einen Hash-Wert von der Seriennummer. Das ist übersichtlicher > als wilde Zufallszahlen. Lothar Miller schrieb: > Michael U. schrieb: >> kann die gleiche Zahl doch auch direkt hintereinander kommen? > Nicht bei den üblichen Algorithmen. Doch, gerade bei den üblichen Algorithmen. Diese verwenden für die interne Berechnung meist die doppelte Bitzahl. Auf PCs wird also intern mit 64 Bit gerechnet, um eine 32-Bit-Pseudozufallszahl zu generieren. Ein Zufallsgenerator, der zwei gleiche aufeinanderfolgende Zahlen grundsätzlich ausschließt, taugt allenfalls als Rauschgenerator für Soundeffekte.
Lothar Miller schrieb: > Michael U. schrieb: >> kann die gleiche Zahl doch auch direkt hintereinander kommen? > Nicht bei den üblichen Algorithmen. Wieso nicht? Falls das nicht möglich wäre, hätte der Zufallszahlengenerator eine massive Schwäche. Nur relativ unwahrscheinlich ist es bei 2^32 verschiedenen Zahlen. Gruß, Alex
Pragmatische Lösung: Teil die 64 bit auf, füll 32 Bit mit nem Unix-Timestamp o.Ä., die anderen 32 mit irgendwas, z.B. einer Pseudozufallszahl. So kannst du bis 2037 jede Sekunde ein Gerät bauen und verkaufen, und es wird sich nie eine Seriennnummer wiederholen.
Peter Dannegger schrieb: > Windows selber kann keinen Zufall erzeugen, alles ist ja mit dem > CPU-Takt synchron. Man braucht 2 voneinander unabhängige Takte. In einem PC gibt es eine Menge Dinge die zufällig (im Sinne von nicht vom CPU-Takt ableitbar) sind: - Festplattenzugriffe - Benutzereingaben - Netzwerkereignisse Jedes aktuelle Betriebssystem enthält einen Zufallszahlengenerator der diese Entropie einsammelt und so verwurstet dass hinten zuverlässige, gleichverteilte Zufallszahlen herauskommen. Unter Unix/Linux kommt man da über /dev/random ran, unter Windows z.B. so: http://msdn.microsoft.com/en-us/library/system.security.cryptography.rngcryptoserviceprovider.aspx
> Nimm doch nen Maxim Seriennummer-IC, die haben ne weltweit einmalige > 6Byte-ID. Wie groß ist die Wahrscheinlichkeit, dass du für Maxim arbeitest?
Alexander v. Grafenstein schrieb: > Wieso nicht? Falls das nicht möglich wäre, hätte der > Zufallszahlengenerator eine massive Schwäche. J.-u. G. schrieb: > Dann sind diese Algorithmen aber schlecht. Es ist so, dass ein 32-Bit Zufallsgenerator bis zu 2^32 Zahlen in zufälliger Reihenfolge hintereinander bringt, und dann von vorn in der selben Reihenfolge wieder anfängt. Keine der 2^32 Zahlen kommt doppelt vor, und schon gar nicht hintereinander. WENN jetzt aber statt der 32 Bit einfach 64 Bits für den Generator verwendet werden, und aus diesen 64 Bit dann nur 32 Bits nach aussen dringen, DANN kannund wird durchaus auch eine mehrfache Wiederholung von Zahlen drin sein.
Lothar Miller schrieb: > Es ist so, dass ein 32-Bit Zufallsgenerator bis zu 2^32 Zahlen in > zufälliger Reihenfolge hintereinander bringt, und dann von vorn in der > selben Reihenfolge wieder anfängt. Keine der 2^32 Zahlen kommt doppelt > vor, und schon gar nicht hintereinander. Mit Verlaub, das is Quatsch. Hier werden wild Äpfel mit Birnen verglichen. Als erstes kann man deterministisch keinen Zufall erzeugen, allenfalls eine Sequenz von Zahlen, die einige Kriterien von Zufallsfolgen aufweisen (daher "Pseudo-Zufallszahlen"). Da der verwendete Algorithmus deterministisch ist und die Länge der Zahlen (Bits zur Darstellung) beschränkt ist wiederholt sich die Zahlenfolge irgendwann. Die Länge der Sequenz ist dann die Periode des Generators. Je nach verwendetem Algorithmus kann die von bis gehen, je länger desto besser. Ein (sehr schlechter) 32 Bit Generator kann durchaus eine Periode von 1 haben ;-) Die "Zufälligkeit" oder Qualität der erzeugten Zahlen ist ein ganz anderes Kriterium. So ist die Sequenz "1,2,3,4,5,6,7" eine perfekte, absolut gültige Sequenz, genauso wie "1,1,1,1,1,1,1" oder "2,4,7,1,6,3,5". Im allgemeinen geht sollte die Häufigkeit der einzelnen Bits(!) gleichverteilt sein (wenn man von gleichverteiten Zufallszahlen ausgeht). Je nach Algorithmus funktioniert das mehr oder weniger gut und ohne den zu kennen erübrigt sich jeder Spekulation.
Andreas Schwarz schrieb: > In einem PC gibt es eine Menge Dinge die zufällig (im Sinne von nicht > vom CPU-Takt ableitbar) sind: > - Festplattenzugriffe > - Benutzereingaben > - Netzwerkereignisse Es ist aber nicht trivial, diese so zu verwursten, daß kein Einfluß des CPU-Taktes mehr besteht. Man muß dazu schon über die Internas gut Bescheid wissen, wie und wann die CPU diese Ereignisse auswertet. Tasten- und Mauseingaben werden z.B. über den USB-Takt synchronisiert (alle 10ms). Mal ein einfaches Beispiel: AVR-Mikrokontroller: Mainloop = Endlosschleife (RJMP = 2 Zyklen). Taste an Interruptpin und oh Wunder, man kriegt nur gerade Zahlen vom Timer geliefert. Die Erklärung: der 2-Zyklen-Befehl RJMP kann nicht unterbrochen werden. Aber: Taste an Pin-Change Interrupt: echter Zufall, da der Timestamp jeden CPU-Zyklus von der Hardware gelatcht werden kann. Meistens braucht man aber keinen sehr guten Zufall und daher reichen die PC-Funktionen. Ich hab z.B. zweimal hintereinander das gleiche Sudoku gelöst und es erst danach gemerkt. Peter
micha schrieb: > Lothar Miller schrieb: >> Es ist so, dass ein 32-Bit Zufallsgenerator bis zu 2^32 Zahlen in >> zufälliger Reihenfolge hintereinander bringt, und dann von vorn in der >> selben Reihenfolge wieder anfängt. Keine der 2^32 Zahlen kommt doppelt >> vor, und schon gar nicht hintereinander. > Mit Verlaub, das is Quatsch. Was davon denn? Ich sehe eigentlich nur, dass deine ganze Argumentation im Grunde das selbe sagt, nur eben mit anderen Worten...
Lothar Miller schrieb: > micha schrieb: >> Lothar Miller schrieb: >>> Es ist so, dass ein 32-Bit Zufallsgenerator bis zu 2^32 Zahlen in >>> zufälliger Reihenfolge hintereinander bringt, und dann von vorn in der >>> selben Reihenfolge wieder anfängt. Keine der 2^32 Zahlen kommt doppelt >>> vor, und schon gar nicht hintereinander. >> Mit Verlaub, das is Quatsch. > Was davon denn? > Ich sehe eigentlich nur, dass deine ganze Argumentation im Grunde das > selbe sagt, nur eben mit anderen Worten... nein, bildlich gesprochen propagierst du einen Zufallsgenerator ohne zurücklegen. und wenn keine Kugeln mehr da sind, ziehst du sie in der selben reihenfolge erneut. Das entsprcht aber keinem Zufallsgernator, weil sich hier die Wahrscheinlichkeit, eine bestimmte Kugel zu ziehen erhöht, je mehr andere ich gezogen hab und somit die Zahlen nicht mehr gleichverteilt sind. edit: Ein gleichverteilter Zufallsgernator ist ein Zufallsexperiment mit zurücklegen.
Vlad Tepesch schrieb: > nein, bildlich gesprochen propagierst du einen Zufallsgenerator ohne > zurücklegen. Naja, ich habe lediglich Hardware beschrieben. In der Realität wird das (unter strenger Missachtung der Zufallstheorie) einfach so einfach gemacht. Das nennt sich dann z.B. LFSR und reicht in gut 99% der Fälle für einen Zufall aus...
Es hängt halt vom Generator ab. Für einen "linear feedback shift register" trifft Deine Beschreibung sicher zu, ich komme mehr von der Software-Seite und hatte einen "linear congruential generator" im Sinn. Und schon streiten wir uns ;-) Aber daraus sieht man, dass ohne den Generator zu kennen gar keine Aussage möglich ist. Ob die Qualität/ Zufälligkeit für einen Anwendungsfall reicht, muss man selber herausfinden. Allerdings hast Du sicher Recht, dass in 99% aller Fälle ein einfaches, schnelles Verfahren völlig ausreicht. Nichts für Ungut + gute WE Michael
Lothar Miller schrieb: > Naja, ich habe lediglich Hardware beschrieben. In der Realität wird das > (unter strenger Missachtung der Zufallstheorie) einfach so einfach > gemacht. Das nennt sich dann z.B. LFSR und reicht in gut 99% der Fälle > für einen Zufall aus... Dann lies deinen Beitrag nochmal: der redet von etwas völlig anderem. du hast behautpted, dass der Zufallsgerator für n-bittige Zahlen eine Periode von genau 2^n hat und jede Zahl genau einmal vorkommt. vom prinzip her also: alle 2^n Kugeln in einen Sack schmeißen, kräftig schütteln und in einem Kreis hinlegen und nun der reihe nach die Zahlen vorlesen. Tatsächlich kommt in einer Periode eines (halbwegs brauchbaren) Generators jede Zahl merhfach vor. Quasi: x*2^n Kugeln in einen Sack schmeißen ... je größer x, desto besser natürlich. die c-standard rand() methode erzeugt 2^16 Zufallszahlen und arbeitet intern meist mit 32-Bit Variablen. Hier ist x quasi 2^16 Damit können nämlich tatsächlich die gleiche Zahl mehrmals hintereinander auftreten. das ein LFSR natürlich kein allzuguter RNG ist, kann man an vielen stellen nachlesen, aber auf jden Fall um Längen besser, als der von dir erklärte Generator
Peter Dannegger schrieb: > Andreas Schwarz schrieb: >> In einem PC gibt es eine Menge Dinge die zufällig (im Sinne von nicht >> vom CPU-Takt ableitbar) sind: >> - Festplattenzugriffe >> - Benutzereingaben >> - Netzwerkereignisse > > Es ist aber nicht trivial, diese so zu verwursten, daß kein Einfluß des > CPU-Taktes mehr besteht. Aber auch nicht sehr schwierig: > Mainloop = Endlosschleife (RJMP = 2 Zyklen). > Taste an Interruptpin und oh Wunder, man kriegt nur gerade Zahlen vom > Timer geliefert. Mach das 10 Mal, berechne über die Zahlen einen Hash (z.B. MD5) und verwende 8 Bit davon; da wirst du mit normalen Mitteln keine Systematik mehr finden können. > Meistens braucht man aber keinen sehr guten Zufall und daher reichen die > PC-Funktionen. Für Kryptographie ist guter Zufall sehr wichtig, deshalb bringt jedes halbwegs aktuelle Betriebssystem einen sehr gut funktionierenden Zufallsgenerator mit. > Ich hab z.B. zweimal hintereinander das gleiche Sudoku gelöst und es > erst danach gemerkt. Da wurde wahrscheinlich der triviale rand()-Pseudozufallszahlengenerator verwendet.
Irgent wie haben wir den TO verloren. Er meldet sich gar nicht mehr. Praktikable Lösung: Speichere alle erzeugten IDs und vergleiche, ob du sie schon mal vergeben hast. Hängt aber von deiner Anwendung ab, ob das eine gute Lösung ist. Von der wir allerdings nicht viel Wissen. Nur das sie mit Geräten zusammen hängt. volker
Vlad Tepesch schrieb: > du hast behautpted, dass der Zufallsgerator für n-bittige Zahlen eine > Periode von genau 2^n hat und jede Zahl genau einmal vorkommt. Und dabei implizit vorausgesetzt, dass die Generatorbreite gleich der Ausgangsbreite ist. Das mag für ein direkt druchverdrahtetes LFSR stimmen, aber Yalu hat es ja schon angemerkt: Yalu X. schrieb: > bei den üblichen Algorithmen. Diese verwenden für die > interne Berechnung meist die doppelte Bitzahl. Auf PCs wird also intern > mit 64 Bit gerechnet, um eine 32-Bit-Pseudozufallszahl zu generieren.
Angehängte Dateien:
-
zufall1.png
12 KB -
zufall2.png
11 KB
Ungeachtet des Sinns oder Unsinns, (Pseudeo-)Zufallszahlen zur Identifi- zierung von Produktexemplaren zu verwenden, ist hier noch eine Antwort auf die ursprüngliche Frage: Die Diagramme zeigen für eine gegebene Anzahl von 32-Bit-Zufallszahlen die Wahrscheinlichkeit, dass sich darunter mindestens zwei gleiche befinden. Man sieht, dass bei 10000 Zahlen die Wahrscheinlichkeit schon über 1%, für 77000 etwa 50% und für 200000 sogar über 99% beträgt. Für Großserienprodukte ist das Verfahren mit den Zufallszahlen ohne spezielle Vorkehrungen zur Vermeidung von Dubletten also nicht geeignet. Das ist eigentlich erstaunlich, weil die 200000 Zahlen gerade einmal einen Anteil von 0,047 Promille der Gesamtanzahl (2³²) ausmachen. Das Erstaunen legt sich aber wieder, wenn man das Geburtstagsparadoxon kennt: http://de.wikipedia.org/wiki/Geburtstagsparadoxon
Warum muss das ne Zufallszahl und keine fortlaufende Seriennummer sein?
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.