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.
[Algorytmy] Generowanie liczb, pseudolosowość
[Algorytmy] Generowanie liczb, pseudolosowość
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.
Powód: Temat umieszczony w złym dziale. Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
-
- 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ść
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)
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)
-
- Użytkownik
- Posty: 953
- 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ść
Algorytm do generowania liczby od 0 do 1 i bardzo dobrej jakości:
i teraz zwyczajnie mnożymy to przez całkowitą i bierzemy tylko część ułamkową:
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:
phi = 0.618..
. golden ratio i z precyzją 2 double powiedzmy, czyli dwie liczby doublei 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.
Powód: Stosuj tagi code i tex.
-
- Użytkownik
- Posty: 953
- 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ść
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);
}