Unterschied bei der Generierung von Zufallszahlen.
-
Hallo Leute!
Ich haber mal tief in meiner CD-Kiste gekramt und verschiedene Arten von
Zufallszahlengeneratoren gefunden. Der eine ist eine geänderte Fibonacci sequence. Siehe Kommentar in den Quellcodes
Der andere benützt die Ziggurat-Methode.Welche Methode ist nun besser?
Hier die Quellcodes dafür:
/************************************************************************ This random number generator originally appeared in "Toward a Universal Random Number Generator" by George Marsaglia and Arif Zaman. Florida State University Report: FSU-SCRI-87-50 (1987) It was later modified by F. James and published in "A Review of Pseudo- random Number Generators" Converted from FORTRAN to C by Phil Linttell, James F. Hickling Management Consultants Ltd, Aug. 14, 1989. THIS IS THE BEST KNOWN RANDOM NUMBER GENERATOR AVAILABLE. (However, a newly discovered technique can yield a period of 10^600. But that is still in the development stage.) It passes ALL of the tests for random number generators and has a period of 2^144, is completely portable (gives bit identical results on all machines with at least 24-bit mantissas in the floating point representation). The algorithm is a combination of a Fibonacci sequence (with lags of 97 and 33, and operation "subtraction plus one, modulo one") and an "arithmetic sequence" (using subtraction). On a Vax 11/780, this random number generator can produce a number in 13 microseconds. ************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <math.h> #define TRUE 1 #define FALSE 0 float u[97], c, cd, cm; int i97, j97, test; int rmarin(int ij, int kl); int ranmar(float rvec[], int len); int main() { float temp[100]; int i; int ij, kl, len; /*These are the seeds needed to produce the test case results*/ ij = 1802; kl = 9373; /*Do the initialization*/ if (1 == rmarin(ij,kl)) return 1; /*Generate 20000 random numbers*/ len = 100; for ( i=0; i<=199 ; i++) if (1 == ranmar(temp, len)) return 1; /*If the random number generator is working properly, the next six random numbers should be: 6533892.0 14220222.0 7275067.0 6172232.0 8354498.0 10633180.0 */ len = 6; if (1 == ranmar(temp, len)) return 1; for ( i=0; i<=5; i++) printf("%12.1f\n",4096.0*4096.0*temp[i]); return NULL; } /************************************************************************ This is the initialization routine for the random number generator RANMAR() NOTE: The seed variables can have values between: 0 <= IJ <= 31328 0 <= KL <= 30081 The random number sequences created by these two seeds are of sufficient length to complete an entire calculation with. For example, if several different groups are working on different parts of the same calculation, each group could be assigned its own IJ seed. This would leave each group with 30000 choices for the second seed. That is to say, this random number generator can create 900 million different subsequences -- with each subsequence having a length of approximately 10^30. Use IJ = 1802 & KL = 9373 to test the random number generator. The subroutine RANMAR should be used to generate 20000 random numbers. Then display the next six random numbers generated multiplied by 4096*4096 If the random number generator is working properly, the random numbers should be: 6533892.0 14220222.0 7275067.0 6172232.0 8354498.0 10633180.0 ************************************************************************/ int rmarin(int ij, int kl) { float s, t; int i, j, k, l, m; int ii, jj; /* Change FALSE to TRUE in the next statement to test the random routine.*/ test = TRUE; if ( ( ij < 0 || ij > 31328 ) || ( kl < 0 || kl > 30081 ) ) { printf ("RMARIN: The first random number seed must have a " "value between 0 and 31328\n"); printf (" The second random number seed must have a " "value between 0 and 30081"); return 1; } i = fmod(ij/177.0, 177.0) + 2; j = fmod(ij , 177.0) + 2; k = fmod(kl/169.0, 178.0) + 1; l = fmod(kl , 169.0); for ( ii=0; ii<=96; ii++ ) { s = 0.0; t = 0.5; for ( jj=0; jj<=23; jj++ ) { m = fmod( fmod(i*j,179.0)*k , 179.0 ); i = j; j = k; k = m; l = fmod( 53.0*l+1.0 , 169.0 ); if ( fmod(l*m,64.0) >= 32) s = s + t; t = 0.5 * t; } u[ii] = s; } c = 362436.0 / 16777216.0; cd = 7654321.0 / 16777216.0; cm = 16777213.0 / 16777216.0; i97 = 96; j97 = 32; test = TRUE; return NULL; } int ranmar(float rvec[], int len) { float uni; int ivec; if ( !test ) { printf ("RANMAR: Call the initialization routine (RMARIN) " "before calling RANMAR.\n"); return 1; } for ( ivec=0; ivec < len; ivec++) { uni = u[i97] - u[j97]; if ( uni < 0.0 ) uni = uni + 1.0; u[i97] = uni; i97--; if ( i97 < 0 ) i97 = 96; j97--; if ( j97 < 0 ) j97 = 96; c = c - cd; if ( c < 0.0 ) c = c + cm; uni = uni - c; if ( uni < 0.0 ) uni = uni + 1.0; rvec[ivec] = uni; } return NULL; } /* I use the following procedure in TC to generate seeds: The sow() procedure calculates two seeds for use with the random number generator from the system clock. I decided how to do this myself, and I am sure that there must be better ways to select seeds; hopefully, however, this is good enough. The first seed is calculated from the values for second, minute, hour, and year-day; weighted with the second most significant and year-day least significant. The second seed weights the values in reverse. */ void sow( seed1, seed2 ) int *seed1, *seed2; { struct tm *tm_now; float s_sig, s_insig, maxs_sig, maxs_insig; long secs_now; int s, m, h, d, s1, s2; time(&secs_now); tm_now = localtime(&secs_now); s = tm_now->tm_sec + 1; m = tm_now->tm_min + 1; h = tm_now->tm_hour + 1; d = tm_now->tm_yday + 1; maxs_sig = 60.0 + 60.0/60.0 + 24.0/60.0/60.0 + 366.0/24.0/60.0/60.0; maxs_insig = 60.0 + 60.0*60.0 + 24.0*60.0*60.0 + 366.0*24.0*60.0*60.0; s_sig = s + m/60.0 + h/60.0/60.0 + d/24.0/60.0/60.0; s_insig = s + m*60.0 + h*60.0*60.0 + d*24.0*60.0*60.0; s1 = s_sig / maxs_sig * 31328.0; s2 = s_insig / maxs_insig * 30081.0; *seed1 = s1; *seed2 = s2; }Nun der andere:
/******************************************************************** The McGill Super-Duper Random Number Generator G. Marsaglia, K. Ananthanarayana, N. Paul Incorporating the Ziggurat method of sampling from decreasing or symmetric unimodal density functions. G. Marsaglia, W.W. Tsang Rewritten into C by E. Schneider *********************************************************************/ static unsigned long mcgn, srgn; #define MULT 69069L void rstart (i1, i2) long i1, i2; { mcgn = (i1 == 0) ? 0 : i1 | 1; srgn = (i2 == 0) ? 0 : (i2 & 0x7FF) | 1; } long uni() { unsigned long r0, r1; r0 = (srgn >> 15); r1 = srgn ^ r0; r0 = (r1 << 17); srgn = r0 ^ r1; mcgn = MULT * mcgn; r1 = mcgn ^ srgn; return (r1 >> 1); } long vni() { unsigned long r0, r1; r0 = (srgn >> 15); r1 = srgn ^ r0; r0 = (r1 << 17); srgn = r0 ^ r1; mcgn = MULT * mcgn; r1 = mcgn ^ srgn; return r1; } /* "Anyone who consider arithmetic means of producing random number is, of course, in a state of sin" - John Von Neumann */Der dritte im Bunde ist:
/* This type of random generators originate in early 1950's, and their good properties were well known by late 50's (cf. D.Knuth 2nd ed., vol 2, section 3.2.2). A table of 90 different "magic pairs" like (97,23) is also given in Knuth, as well as generalizations of the simple add to primitive polynomials as suggested in your message. As for practical implementations on a micro, the floating point version will be very slow compared to integer version (even with 8087). I've actually used exactly the same pair (97,23) combined with lookup based CRC-16 instead of an add to obtain very fast and practically unlimited source for random numbers. One should note that to obtain floating point sequence, it is not enough to concatenate succesive random numbers from the say 16-bit integer generator. Instead one should use 32-bit integers or 64-bit integers for float/double (best done in assembler), with proper range reduction on the exponent part (usually just an AND/OR mask). As to seeding of the array[97], one can use rand() coupled with time/date functions as suggested in several other responses. I've used PC timer 8253 directly which runs at 1.19 Mhz, coupled with date and keyboard interrupt, the array is re-seeded by adding new-seed-rand() values to the existent ones whenever a key was struck. Also, the random numbers are continuously generated in any program-idle state. The core of the algorithm (without CRC and seed generator) is: */ /******************************************************************** Random Array ra[] is initialized to not-all-even, with e.g. rand() coupled with time/date. Before using the numbers, few thousands (+/- random number) should be generated and discarded. ********************************************************************/ typedef unsigned int rn; #define RA_TOP (ra+96) rn ra[97]; rn *p97=RA_TOP, *p23=ra+22; rn fast_rnd() { rn r; r = (*p97-- += *p23--); if (p97 < ra) p97=RA_TOP; else if (p23 < ra) p23=RA_TOP; return(r); }Ersteres Beispiel habe ich ein klein wenig umgeschrieben:
zunächst main.cpp:
#include <iostream> using namespace std; /************************************************************************ This random number generator originally appeared in "Toward a Universal Random Number Generator" by George Marsaglia and Arif Zaman. Florida State University Report: FSU-SCRI-87-50 (1987) It was later modified by F. James and published in "A Review of Pseudo- random Number Generators" Converted from FORTRAN to C by Phil Linttell, James F. Hickling Management Consultants Ltd, Aug. 14, 1989. THIS IS THE BEST KNOWN RANDOM NUMBER GENERATOR AVAILABLE. (However, a newly discovered technique can yield a period of 10^600. But that is still in the development stage.) It passes ALL of the tests for random number generators and has a period of 2^144, is completely portable (gives bit identical results on all machines with at least 24-bit mantissas in the floating point representation). The algorithm is a combination of a Fibonacci sequence (with lags of 97 and 33, and operation "subtraction plus one, modulo one") and an "arithmetic sequence" (using subtraction). On a Vax 11/780, this random number generator can produce a number in 13 microseconds. ************************************************************************/ #include <stdio.h> #include <stdlib.h> #include "random.h" int main() { Zufall zuf; int temp, i; /*Generate 20000 random numbers*/ for ( i=0; i<=150 ; i++) { temp = zuf.getrand(0,100); cout << endl << temp; //%12.1lf if (temp == 49) break; } return 0; }dann random.h:
#ifndef RANDOM_H_INCLUDED #define RANDOM_H_INCLUDED #include <time.h> #define TRUE 1 #define FALSE 0 void sow(int *seed1, int *seed2); int rmarin(void); float ranmar(void); int getrand(int min, int max); class Zufall { public: Zufall(void); ~Zufall(); int getrand(int min, int max); void sow( int *seed1, int *seed2 ); int rmarin(void); float ranmar(void); private: int initrandom; float u[97], c, cd, cm; int i97, j97, test; }; #endif // RANDOM_H_INCLUDEDzu guter letzt random.cpp:
#ifndef RANDOM_H_INCLUDED #define RANDOM_H_INCLUDED #include <time.h> #define TRUE 1 #define FALSE 0 void sow(int *seed1, int *seed2); int rmarin(void); float ranmar(void); int getrand(int min, int max); class Zufall { public: Zufall(void); ~Zufall(); int getrand(int min, int max); void sow( int *seed1, int *seed2 ); int rmarin(void); float ranmar(void); private: int initrandom; float u[97], c, cd, cm; int i97, j97, test; }; #endif // RANDOM_H_INCLUDED /************************************************************************ This is the initialization routine for the random number generator RANMAR() NOTE: The seed variables can have values between: 0 <= IJ <= 31328 0 <= KL <= 30081 The random number sequences created by these two seeds are of sufficient length to complete an entire calculation with. For example, if several different groups are working on different parts of the same calculation, each group could be assigned its own IJ seed. This would leave each group with 30000 choices for the second seed. That is to say, this random number generator can create 900 million different subsequences -- with each subsequence having a length of approximately 10^30. Use IJ = 1802 & KL = 9373 to test the random number generator. The subroutine RANMAR should be used to generate 20000 random numbers. Then display the next six random numbers generated multiplied by 4096*4096 If the random number generator is working properly, the random numbers should be: 6533892.0 14220222.0 7275067.0 6172232.0 8354498.0 10633180.0 ************************************************************************/ int Zufall::rmarin(void) { int ij, kl; float s, t; int i, j, k, l, m; int ii, jj; sow(&ij, &kl); /* Change FALSE to TRUE in the next statement to test the random routine.*/ test = TRUE; if ( ( ij < 0 || ij > 31328 ) || ( kl < 0 || kl > 30081 ) ) { cout << "\nRMARIN: The first random number seed must have a value between 0 and 31328\n"; cout << "\nThe second random number seed must have a value between 0 and 30081"; return 1; } i = fmod(ij/177.0, 177.0) + 2; j = fmod(ij , 177.0) + 2; k = fmod(kl/169.0, 178.0) + 1; l = fmod(kl , 169.0); for ( ii=0; ii<=96; ii++ ) { s = 0.0; t = 0.5; for ( jj=0; jj<=23; jj++ ) { m = fmod( fmod(i*j,179.0)*k , 179.0 ); i = j; j = k; k = m; l = fmod( 53.0*l+1.0 , 169.0 ); if ( fmod(l*m,64.0) >= 32) s = s + t; t = 0.5 * t; } u[ii] = s; } c = 362436.0 / 16777216.0; cd = 7654321.0 / 16777216.0; cm = 16777213.0 / 16777216.0; i97 = 96; j97 = 32; test = TRUE; return 0; } float Zufall::ranmar(void) { float uni; uni = u[i97] - u[j97]; if ( uni < 0.0 ) uni = uni + 1.0; u[i97] = uni; i97--; if ( i97 < 0 ) i97 = 96; j97--; if ( j97 < 0 ) j97 = 96; c = c - cd; if ( c < 0.0 ) c = c + cm; uni = uni - c; if ( uni < 0.0 ) uni = uni + 1.0; //*rewer = uni; uni *= 4096 * 4096; return uni; }Ich weiß, random.cpp und random.h hätte man besser schreiben können,
aber zum experimentieren reicht es.Hier meine Fragen:
Wenn ich bei den Beispielen die float-Variablen zu double oder long double
tauschen würde, was passiert dann mit dem Zufallszahlengenerator?
Wie steht es mit heutigen Codes, etwa in gcc?
Laut einigen Web-Seiten liegt die Periode, also die Anzahl von Zufallszahlen,
bei der dann wiederholungen auftreten bei solchen Codes bei 2 hoch 32.
Bein ersten Code wird sie aber mit 2 hoch 144 angegeben. Ist das für oberen
Code nicht zu hoch gegriffen?
-
rustyoldguy schrieb:
Welche Methode ist nun besser?
Definiere, was für dich einen "besseren" Zufallsgenerator auszeichnet.
Wenn ich bei den Beispielen die float-Variablen zu double oder long double
tauschen würde, was passiert dann mit dem Zufallszahlengenerator?Probier es doch aus?
Wie steht es mit heutigen Codes, etwa in gcc?
Was genau meinst du? Die Implementierung der rand-Funktion? Ist üblicherweise nicht für wissenschaftliches Rechnen geeignet. Vor allem kann und darf man sich nicht auf eine konkrete Implementierung verlassen.
Bein ersten Code wird sie aber mit 2 hoch 144 angegeben. Ist das für oberen
Code nicht zu hoch gegriffen?Nein.
-
Hallo SeppJ!
Danke für deine Antwort. Da im Netz die Angaben für diese Generatoren
normalerweise bei 2^32 liegt, war ich bei den Angaben, welche diesen
Code beiliegen, verwundert.Eine Erklärung, warum man für "normale" C-Codes niedrigere Perioden
als wie oben angibt wäre, das es einigen Schlapphut-Organisationen wie
ein Stein im Magen liegt, wenn es Verschlüsselungsprogramme gibt, die
auf einen solchen Code aufbauen, mit mehr als 2^32, etwa wie 2^144.Ich denke, das Recht auf Bildung sollte doch solchen Interessen stets
voranstehen. Außerdem kann ich mir nicht vorstellen, das durch eine
Verwendung solchen Codes gleich der Weltuntergang ausgelöst wird.
Es sei denn das ich hier die Macht von Organisationen wie die des kra
Key-Recovery-Association weit unterschätze. Die haben was besseres zu
tun, als solche Foren wie dieses auf harmlose "Softwarebastler" zu
filzen.Sehr interessant für mich ist dieser erste Code deshalb, da hier
beiint rmarin(int ij, int kl)Die Parameter ij und kl den Zufallszahlengenerator steuern. Damit läßt
sich eine Eingabe von Schlüsselzahlen oder von Codewörtern,
verwirklichen, welche durch Prozeduren eine Generierung die
zwei Steuerparameter von "rmarin" auslösen. Das wäre wesentlich
einfacher,als bei der bitweisen Transposition innerhalb eines Files
riesige Schlüsseldateien handhaben zu müssen.
-
rustyoldguy schrieb:
Eine Erklärung, warum man für "normale" C-Codes niedrigere Perioden
als wie oben angibt wäre, das es einigen Schlapphut-Organisationen wie
ein Stein im Magen liegt, wenn es Verschlüsselungsprogramme gibt, die
auf einen solchen Code aufbauen, mit mehr als 2^32, etwa wie 2^144.Nein, das hat absolut nichts mit Kryptographie zu tun. Keiner der hier gezeigten Generatoren ist kryptographisch sicher und sie dürfen auf keinen Fall für Kryptographie eingesetzt werden! Aber Algorithmen und Implementierungen kryptographisch sicherer Generatoren sind ganz offen erhältlich, da gibt es keine Geheimniskrämerei.
Eine lange Periode ist dann von Belang, wenn man eben sehr, sehr viele Zahlen nacheinander benötigt. Das ist in den allermeisten Fällen nicht der Fall, daher sind kurze Perioden nichts schlimmes (die Periodenlänge sagt nichts über die Qualität der Zufallszahlen aus!) und die 2^32 sind völlig ausreichend. Bei sehr, sehr aufwändigen Rechnungen kann es vorkommen, dass man mal mehr als 2^32 Zufallszahlen benötigt. Da darf man natürlich keinen solchen Generator nehmen, da man sich sonst das Ergebnis verfälscht.
rustyoldguy schrieb:
Sehr interessant für mich ist dieser erste Code deshalb, da hier
beiint rmarin(int ij, int kl)Die Parameter ij und kl den Zufallszahlengenerator steuern. Damit läßt
sich eine Eingabe von Schlüsselzahlen oder von Codewörtern,
verwirklichen, welche durch Prozeduren eine Generierung die
zwei Steuerparameter von "rmarin" auslösen. Das wäre wesentlich
einfacher,als bei der bitweisen Transposition innerhalb eines Files
riesige Schlüsseldateien handhaben zu müssen.Ich verstehe nicht, wovon du sprichst.
Es klingt so, als wolltest du irgendetwas bestimmtes erreichen, aber du traust dich nicht, danach zu fragen. Stattdessen redest du um den heißen Brei herum. Falls ich damit Recht haben sollte: Frag einfach nach dem, was du erreichen möchtest!
-
Hallo SeppJ!
Danke für die Infos über die Codes. Ich denke, wenn man Dateien oder
Nachrichten verschlüsseln muß, sollte man dies nicht nur mit einem
Programm machen, sondern ruhig mehrfach verschlüsseln, ruhig auch
mit einen selbstgebastelten Progamm. Seit manche Versionen von PGP und
anderen Programmen zwangsweise ein "Universalpasswort" eingepflanzt
wurde, sollte man über so etwas nachdenken. Nicht das ich was zum
verstecken hätte, mich reizt nur die technische Spielerei.Folgendes ist nur hypothetisch zu verstehen:
Nehmen wir an, das ich früher einmal Kurzwellenfunk betrieben hätte, und
wäre nur zufällig mal auf eine solche Funkfrequenz gestoßen, was einem
per Gesetz untersagt ist, so etwas zu veröffentlichen(Gibt es wirklich,
diese Bestimmung!!!), so wäre das der Anstoß gewesen, sich mal mit
Verschlüsselungstechniken zu befassen.Nehmen wir einmal an, das dort Zahlengruppen gesendet werden. Wie etwa
"Neugen drei vier acht Zero........ Neugen fünf acht acht zero drei....usw"
Diese Zahlengruppen würden dann zur Chiffrierung/Dechiffrierung benutzt.
Rein zum Spaß halber, so als Hobby, wäre es interessant, nur so ungefähr
zu wissen wie so etwas prinzipiell funktioniert oder?. So ähnlich wie Rätzelraten oder Buchlesen.
Ist ja auch nicht böse, so was zu schreiben. Man spielt ja nur etwas
mit dem PC, und nicht mit einer geladenen Waffe, oder?Nix für unguat!
-
rustyoldguy schrieb:
Danke für die Infos über die Codes. Ich denke, wenn man Dateien oder
Nachrichten verschlüsseln muß, sollte man dies nicht nur mit einem
Programm machen, sondern ruhig mehrfach verschlüsseln, ruhig auch
mit einen selbstgebastelten Progamm.Das ist normalerweise keine gute Idee.
Folgendes ist nur hypothetisch zu verstehen:
Nehmen wir an, das ich früher einmal Kurzwellenfunk betrieben hätte, und
wäre nur zufällig mal auf eine solche Funkfrequenz gestoßen, was einem
per Gesetz untersagt ist, so etwas zu veröffentlichen(Gibt es wirklich,
diese Bestimmung!!!), so wäre das der Anstoß gewesen, sich mal mit
Verschlüsselungstechniken zu befassen.Nehmen wir einmal an, das dort Zahlengruppen gesendet werden. Wie etwa
"Neugen drei vier acht Zero........ Neugen fünf acht acht zero drei....usw"
Diese Zahlengruppen würden dann zur Chiffrierung/Dechiffrierung benutzt.
Was du gehört hast, kennt absolut jeder, der ein Radio bedienen kann. Die Zahlen und Buchstaben dienen in diesem Fall nicht der Verschlüsselung, du hast die verschlüsselte Nachricht selbst gehört. Der Agent hat sein Codebuch, mit dem er dann die Nachricht entschlüsselt hat.
Rein zum Spaß halber, so als Hobby, wäre es interessant, nur so ungefähr
zu wissen wie so etwas prinzipiell funktioniert oder?. So ähnlich wie Rätzelraten oder Buchlesen.
Ist ja auch nicht böse, so was zu schreiben. Man spielt ja nur etwas
mit dem PC, und nicht mit einer geladenen Waffe, oder?Das, was da auf dem Radio gefunkt wurde, ist mit einem One Time Pad verschlüsselt worden. Das ist normalerweise kein gutes Verfahren (sogar ein äußerst schlechtes), wenn es um Datenaustausch zwischen Computern geht. Es ist ein gutes Verfahren, wenn man einen Geheimagenten hinter feindliche Linien geschleust bekommen hat, dem man per Radio etwas zukommen lassen möchte.
