Zufallszahlen
-
Hmm, muss mir morgen mal https://github.com/dials/boost/blob/master/boost/random/uniform_int_distribution.hpp reinziehen...
-
Ich würde auch empfehlen, was fertiges zu nehmen wie uniform_int_distribution, denn das selber zu machen klingt nur nach einer unnötigen und schwer zu findenden Fehlerquelle, vor allem wenn der Fehler subtil genug ist.
Wenn du 3 Mal rand() aufrufst und jeder Aufruf dir 15 zufällige Bits gibt (indem du jeweils auf 15 Bit runtermaskierst), kannst du die aber auch einfach alle verketten zu 45 Bits insgesamt und dann auf 32 Bit maskieren. Oder überseh ich was?
Ich würde aber egal was du machst sehr sicher sein wollen, dass deine rand()-Funktion gut ist und sogar in Frage stellen, warum du eine eigene rand()-Funktion benutzen möchtest, anstatt was fertiges. Hängt aber natürlich auch davon ab, ob es für Kryptografie oder für ein Spiel oder sowas ist (bei ersterem wär eine eigene rand()-Funktion nämlich ein Warnzeichen).
-
@christoph sagte in Zufallszahlen:
Wenn du 3 Mal rand() aufrufst und jeder Aufruf dir 15 zufällige Bits gibt (indem du jeweils auf 15 Bit runtermaskierst), kannst du die aber auch einfach alle verketten zu 45 Bits insgesamt und dann auf 32 Bit maskieren. Oder überseh ich was?
Naja, ja. Ich hab nicht dazugesagt, dass ich manchmal auch andere Intervalle benötige. Dann geht das nicht mehr. Aber auch hier hilft mir die uniform_int_distribution von Boost weiter.
Ich würde aber egal was du machst sehr sicher sein wollen, dass deine rand()-Funktion gut ist und sogar in Frage stellen, warum du eine eigene rand()-Funktion benutzen möchtest, anstatt was fertiges.
Mag ich ja nicht, aber die, die ich hab liefert zu kleine Zahlen. Aber mit uniform_int_distribution löst sich mein Problem.
Falls jemand noch meine Rückfragen zu uniform_int_distribution beantworten kann wäre mir sehr geholfen: https://github.com/boostorg/random/issues/43
Ich muss das nämlich in eine andere Sprache übersetzen.MfG SideWinder
-
@sidewinder Mir ist auch gerade aufgefallen, dass mein Vorschlag mit dem Maskieren auf 15 Bits gar nicht funktioniert, weil es auch die Gleichverteilung kaputt macht.
Dein rand() so oft aufrufen bis eine Zahl mit <= 15 Bits rauskommt, sollte gleichverteilte 15-Bit-Zahlen produzieren, ist aber vielleicht nicht optimal.
-
@SideWinder Ein Generator wie xorshift ist gut und sehr einfach selbst zu implementieren. Dazu eine Funktion ala
uniform_int_distributionund ... tadaa.
-
Die Kernidee eines Zufallsgenerators sieht in der ur Mimik etwa so aus:
... Code ... char zufall(short bis) { static unsigned char Z[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} ; static short i=2; if((i++) > 20)i=2; Z[i] = (Z[i-1]+Z[i-2]) % (bis); return( Z[i] ); } void main() { while(getch() != 32) { printf("wert = %d\n",zufall(2)); } }Wenn man es sehr schnell benötigt kann man mit Asm weiter kommen:
... Code ... short random(); #pragma aux random = "mov esi,offset seed "\ "mov eax,1107030247 "\ "mul dword ptr [esi]"\ "add eax,97177 "\ "mov [esi],eax "\ "shr eax,15 "\ "and ax,8191 "\ "sub ax,4096 "\ value [AX] \Oder etwas ausgeprägter mit timer:
... Code ... ;±±±±±±±±±±±±±±±± rand ±±±±±±±±±±±±±±±± ;returns a random value in range -4096..4095 rand PROC NEAR mov eax,1107030247 mul ds:seed add eax,97177 mov ds:seed,eax shr eax,15 and ax,8191 sub ax,4096 ;size optimizatin, some code moved from after all rand calls add bx,2 mov ds:[bx],ax ret rand ENDP ;±±±±±±±±±±±±±±±± timer ±±±±±±±±±±±±±±±± inittimer PROC NEAR mov eax,fs:[8*4] mov ds:oldint8,eax mov ax,cs shl eax,16 mov ax,OFFSET intti8 mov dx,17000 ;70hz jmp @@1 deinittimer: mov eax,ds:oldint8 xor dx,dx @@1: cli mov fs:[8*4],eax mov al,036h out 43h,al mov al,dl out 40h,al mov al,dh out 40h,al sti ret inittimer ENDP intti8 PROC FAR ;timer interrupt push ax mov al,20h out 20h,al inc cs:framecounter pop ax iret intti8 ENDPDer beste Zufallsgenerator ist jedoch das weiße rauschen aus einem DVBT-Stick
indem man Stichproben aus den Daten abgreift.
Grüße
Karsten
-
Hallo SideWinder!
Vielleicht teilst du die ganze Sache auf. "Normale" rand-Funktionen gehen von 0 bis 65535.
Bei einem 64-Bit-System verarbeitet.
define RAND_MAX /implementation defined/
ist bei 327674294967295 / 65535 = 65537
Du müsstest also das Ganze in 65537 Felder unterteilen. Da aber eine Null auch vorkommen kann(sollte)
sind das genau 65536^2.
also zuerst mit rand eine Zahl zwischen 0 und 65535 dann noch eine und beide Multiplizieren.
Praktisch wie früher in DOS, also segment und Offset, wenn du weißt was ich meine.
Auf einigen Seiten
http://man7.org/linux/man-pages/man3/rand.3.html
ist das aber anders zu lesen. Einige Systeme arbeiten bis etwa 199506.
Da ich erst kürzlich meine CD-Sammlung entsorgt habe, hier mal ein Code:/************************************************************************ 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> #include <time.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); void sow( int *seed1, int *seed2 ); int main() { float temp[100]; int i; int ij, kl, len; /*These are the seeds needed to produce the test case results*/ sow( &ij, &kl); //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 0; } /************************************************************************ 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 0; } 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 0; } /* 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( int *seed1, int *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; }Vielleicht kannst du den Code ja umarbeiten.
-
Genau genommen meine ich so etwas
int randinitcount = 0; void RANDOMIZE(void) { long bwer; srand( (unsigned)(time(&bwer) % 20)); if (randinitcount < 2) randinitcount++; }int getrandom( int min, int max)
{
int zuza, zuza2, zuza3, rewer;
zuza = rand();
zuza2 = (max - min + 1);
zuza3 = zuza % zuza2;
rewer = zuza3 + min;
return rewer;
}long getlongrand(long min, long max)
{
long rewer = 0, rest, bereichsfeld;
int bereich, limit = 32767;bereichsfeld = max / 32767;
bereich = getrandom((int)min, (int)bereichsfeld);
if (bereich > 1) rewer = 32767 * (long)bereich;
rest = max - rewer;
if (rest < 32767) limit = (int)rest;rewer += (long)getrandom(0, limit);
return(rewer);
}
-
Nur um das nicht so stehenzulassen: Was gutes aus dem Standard wie Mersenne twister (mt19937) und uniform_int_distribution nehmen ist schon sinnvoll, außer man hat sehr spezielle Anforderungen und kennt die Mathematik dahinter.
Die ganzen Funktionen, die hier in den letzten 3 Postings gepostet wurden, haben Probleme mit der dem Algorithmus und der Gleichverteilung. Modulo funktioniert nicht, wenn man eine Gleichverteilung haben möchte.
-
@KahnSoft sagte in Zufallszahlen:
Die Kernidee eines Zufallsgenerators sieht in der ur Mimik etwa so aus:
Mhm. Das ist der erste rng den ich sehe der ein statisches Array braucht um zu funktionieren. Du könntest wiklich mal aufhören geistigen Dünnpfiff zu verbreiten. Ein paar Iterationen und dein "Zuffalsgenerator" erledigt sich zu
1 2 3 5 8 13 21 34 55 89 44 33 77 10 87 97 84 81 65 46für
zufall(100).Edit: Die Zitierfunktion scheint jetzt noch kaputter als zu Anfang. But what shells, death is near.
-
uint32_t num; uint32_t i; uint8_t *ptr; ptr = (uint8_t *) # for(i = 0; i < sizeof(num); i++) { *ptr = rand(); ptr++; }unter unix macht man das übrigens eigentlich mit
uint32_t num; int file = open("/dev/urandom", O_RDONLY); read(file, &num, sizeof(num)); close(file);unter windows wirds etwas komplizierter, geht aber auch.
