[Algorytmy] Generowanie liczb, pseudolosowość

adammm
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 28 cze 2014, o 22:28
Płeć: Mężczyzna
Lokalizacja: Poznań

[Algorytmy] Generowanie liczb, pseudolosowość

Post autor: adammm »

Witam,

mam pytanie odnosnie generowania liczb pseudolosowych.
Na jakiej podstawie korzystając z generatora, wynik podawany jest do okreslonego miejsca po przecinku? Od czego to zalezy?

Pozdrawiam.
Ostatnio zmieniony 2 lip 2014, o 20:19 przez Afish, łącznie zmieniany 1 raz.
Powód: Temat umieszczony w złym dziale. Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Generowanie liczb, pseudolosowość

Post autor: Afish »

Zależy od użytego algorytmu, generatorów jest wiele i mogą różnie sobie radzić, więc musisz podać, o który generator chodzi.
Podejrzewam, że najczęstszym podejściem jest generowanie liczb całkowitych, a następnie podzielenie wyniku przez maksymalną osiągalną wartość, dzięki czemu uzyskany wynik będzie w przedziale od zera do jedności. Tak działa domyślna implementacja w Hotspot (Java od Oracle'a) oraz w .NET. Uzyskana precyzja zależy od typu danych i przyjętej reprezentacji zmiennoprzecinkowej (w wyżej wymienionych będzie to dokładność typu podwójnej precyzji z IEEE 754)
Fibik
Użytkownik
Użytkownik
Posty: 952
Rejestracja: 27 wrz 2005, o 22:56
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 11 razy
Pomógł: 74 razy

[Algorytmy] Generowanie liczb, pseudolosowość

Post autor: Fibik »

Algorytm do generowania liczby od 0 do 1 i bardzo dobrej jakości:

phi = 0.618... golden ratio i z precyzją 2 double powiedzmy, czyli dwie liczby double

i teraz zwyczajnie mnożymy to przez całkowitą i bierzemy tylko część ułamkową:
x = (phi*n) mod 1; n++; // albo n += 345433; nie ma to znaczenia...
no i to tyle...

można użyć innej liczby zamiast tego phi, ale phi jest najlepsze, bo ta liczba ma ekstremalną własność - jest najtrudniejsza do aproksymacji za pomocą ułamka \(\displaystyle{ \frac{n}{m}}\), czyli ona jest jakby najbardziej niewymierna w sensie obliczalności, co daje właśnie maksymalną równomierność rozkładu.

Np. liczba Pi jest dużo gorsza... generator byłby znacznie gorszy - mniej równomierny.

Potem można sobie z tego robić losowe z dowolnego przedziału - zwyczajnie mnożąc:

Kod: Zaznacz cały

int random(n) { return rndreal() * n; } // losowa od 0 do n-1
Ostatnio zmieniony 4 lip 2014, o 20:33 przez Afish, łącznie zmieniany 1 raz.
Powód: Stosuj tagi code i tex.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Generowanie liczb, pseudolosowość

Post autor: Afish »

Fibik, jakieś źródło?
Fibik
Użytkownik
Użytkownik
Posty: 952
Rejestracja: 27 wrz 2005, o 22:56
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 11 razy
Pomógł: 74 razy

[Algorytmy] Generowanie liczb, pseudolosowość

Post autor: Fibik »

Już nie pamiętam gdzie to znalazłem, ale mam kod:

Kod: Zaznacz cały

/*-------------------------------------------------------------------------*/
/*  Uniform random numbers: Multiplicative congruential generator for      */
/*                          uniformly distributed random numbers on (0, 1) */
/*                                                                         */
/*  Modul m = 2**54,  Multiplier a  =  2.783.377.640.906.189               */
/*  Period  = 2**52,                =  a1 * 2**27 + a2                     */
/*                    where  a1 = 20.737.779, a2 = 59.760.077              */
/*-------------------------------------------------------------------------*/
/*                                                                         */
/* The multiplier a of the generator was the winner of a search among one  */
/* million possible multipliers near to the well-known golden section      */ 
/* factor f = .5*(sqrt(5)-1)*2^52. The multiplier a was choosen because of */
/* its good lattice properties up to dimension 8 measured by both Beyer    */ 
/* quotients (Afflerbach/Grothe,1985, Computing 35, 269-276) and           */ 
/* standardized values of the spectral test according to Fishman (1990),   */ 
/* Math.Comput. 54,331-344. The search was carried out by J.H. Ahrens(1992).*/ 
/* The generator (denoted as krand) was implemented and tested as described*/ 
/* in Stadlober/Kremer (1992), Lecture Notes in Econ.Math.Systems 374,     */ 
/* 154-162.                                                                */
/* The values of the measures from dimension 2 to dimension 8 are:         */
/* Beyer-quotients:  .87, .71, .72, .73, .66, .82, .80;  Minimum = .6626   */
/* Spectral-test:    .87, .76, .79, .78, .75, .73, .69;  Minimum = .6870   */
/*                                                                         */
/*-------------------------------------------------------------------------*/
/*                                                                         */
/* The seed-values z_hi and z_lo has to be defined as follows:             */                  */
/* printf("Input seed-high (0 ... 2^27 - 1)  -->   ");                     */
/* scanf("%ld", &z_hi);                                                    */
/* printf("Input seed-low  (0 ... 2^25 - 1)  -->   ");                     */
/* scanf("%ld", &z_lo); z_lo = z_lo*4L + 1L;                               */
/*-------------------------------------------------------------------------*/

#include <math.h>

double drand(unsigned long int *z_hi, unsigned long int *z_lo)
{
 union ux {
	 double   d;
	 short    i[4];
 	 } x;

	unsigned long int i_x;
 	double             d_x;

	x.d = (double)(*z_lo) * 59760077.0;  x.i[3] -= 0X01b0;
	i_x = x.d;
       *z_hi = (*z_hi * 59760077L + *z_lo * 20737779L + i_x) & 0X07FFFFFFL;
	d_x = x.d -= (double)i_x;            x.i[3] += 0X01b0;
       *z_lo = x.d;
	x.d = (double)*z_hi + d_x;           x.i[3] -= 0X01b0;

	return (x.d);
}
ODPOWIEDZ