Uniform random number is not Uniform!!!
Torbjorn Granlund
tege at swox.com
Tue Oct 3 04:12:55 CEST 2006
rohan <rohan076 at gmail.com> writes:
I used the unsigned long mpz_urandomm(ran, s, N) function to generate a
random number. the documentation says that the number generated will be
uniformly distributed between 0 and n-1 inclusive!!! but after running the
program several times i realised that for smaller N's the random numbers are
better distributed in the range 0 to n-1
I wrote this small piece of code, it basically generates random numbers from
0 to n-1, where n = z^ex
---------------------
#include <stdio.h>
#include <gmp.h>
int main(void) {
gmp_randstate_t s;
unsigned long seed, i, z,ex;
mpz_t big;
mpz_init(big);
mpz_t store;
ex = 10;
z=2;
mpz_ui_pow_ui(big, z, ex);
gmp_printf("BIG : %Zd", big);
gmp_randinit_default(s);
seed = time(NULL); // system time
gmp_randseed_ui(s, seed);
for(i = 0; i < 50; ++i) {
mpz_init(store);
mpz_urandomm (store, s, big);
gmp_printf("\nRAN : %Zd", store);
}
gmp_randclear(s);
return 0;
}
-------------------------------------------------------
now the random numbers were evenly distributed for ex=10, but for ex = 256,
the random numbers generated were mostly in the range on 2^240 to 2^256 ,
how can this be called evenly distributed?? am I missing something or this
has something to do with the seed value.
You're confused.
In the range 0..2^256, half of the numbers actually
lie in the range 2^255..2^256, so about half of the uniformly distributed
random numbers should lie there too.
Only about 1 random number in 65536 will be less than 2^240.
End of this discussion, please.
--
Torbjörn
More information about the gmp-discuss
mailing list