views:

59

answers:

4

suppose I have some numbers that form a series for example : 652,328,1,254 and I want to get a seed that if I ,for example ,do

srand(my_seed);

I will get some kind of approximation with bounded error to my origonal sequance , when all numbers appearing in the same order.

thanks,
Alex

+3  A: 

Depends on the algorithm used for the pseudo-random generation. If the algorithm is a simple linear congruential generator, then getting the seed back is just a matter of solving a linear modular equation (note that the solution may be non-unique, but as such a generator is memory-less, it doesn't matter).

If the algorithm is more complex, this may be impossible.

Note that the algorithm used in the C standard library isn't restricted by the standard, so different platforms may have different implementations.

Eli Bendersky
thanks, you gave me a direction where to look.
Alex
Not only does the algorithm have to be simple enough to analyze; it also has to have enough bits of state to encode the series you want to reproduce. The combination seems unlikely in practice. For example, I think you can configure glibc to use an LCG by calling `setstate` with a small enough buffer; but then that LCG only has 32 bits of state, so at best you can choose the first 32 bits of output. Everything after that is deterministic.
Jason Orendorff
More directly: if `srand` takes a 32-bit argument on your platform, you can ask for at most 2^32 different sequences. But of course there are far more possible sequences than that, even if you only want to reproduce a very short sequence.
Jason Orendorff
+1  A: 

Check out this question.

Like Justin says, it's possible to backtrack a linear congruent generator (which rand() implementations often are) when you have a sequence of generated numbers. I guess the problem is to know which one of the previous values is the original seed...

liwp
[citation needed] - where's the requirement that `rand()` is an LCG i.e. bad?
MSalters
I don't thinks there's any requirement for `rand()` to be and LCG, that's just what most implementations seem to be (I've edited the answer to be more clear about this). Also, and LCG isn't necessarily bad - it's very quick to compute and in many cases the provided pseudo-randomness is fine.
liwp
+1  A: 

You can't have an error bound in general. Either your algorithm works or it doesn't. The reason for this is that a reasonable error bound is obviously much smaller that RAND_MAX. That in turn means that the the low bits are not as random as the higher bits. But a good PRNG makes certain that all bits are equally random.

Consider this slow but mathematically sound example of an RNG algorithm:

int rand() {
  state = AES_encrypt(state);
  return state % RAND_MAX;
}
void srand(int seed) {
  state = AES_encrypt(seed);
}

If you can find any significant correlation between the output sequence and the previous state, the AES algorithm should be considered broken.

MSalters
+1  A: 

The definition of a crytographic PRNG is one in which this exact property is computationally infeasible - however, as has been mentioned, there are much weaker (and much faster) PRNGs for which this is possible. So it depends on your algorithm.

BlueRaja - Danny Pflughoeft