jeudi 31 octobre 2019

About rand() in c

q1)

Is this implementation of rand() and srand():

  • correct?
  • required by the standard?
unsigned int __seed;

void srand(unsigned int s) {
    __seed = s;
}

int rand() {
    __seed = __deterministic_and_fast_mathematical_expression_that_depend_only_of_seed(__seed); // Call it expr(), Declared somewhere
    return __seed;
}

q2)

Then, if q1) is true (or in another way), is it true to say that there is cycles in such function, that rand() can be interpreted as a cyclic sequence given at a random point?

// Hypotetically
srand(a)
if rand() = b then expr(a) = b
if rand() = a then expr(b) = a
// Then any call to rand would give successively [a, b, a, b, a, ...] infinitely
// This example is for two values but can work for a sequence of any length

I assume that the rand() function is cyclic after a maximal of 2^64 iterations on 64 bits and 2^32 on 32 bits. For example, if somewhere in the sequence there is:

12891, 872821, 33, 872821, 33, 872821, ... Infinitely

We can isolate the part 33, 872821 and the part before and make a arrow from second to first. Then the rand function could be described by this graph, generated by this procedure:

for(int i = 0; i < RAND_MAX; i++) {
    srand(i);
    while(rand() != i);
    // ISolate the cycle for seed = i
}

q3)

If q2) is true (or in another way), how can we ensure that this function won't give any "broken" sequence with repetitions or very fewly, or just it's unspecified?




Aucun commentaire:

Enregistrer un commentaire