Assuming this generator is well-seeded, you probably can't learn much about the next output. You observe two outputs, so 32 bits in total. The state of the generator is 48 bits. Thus, there will probably be about $2^{16}$ states of the generator that are compatible with your two observations. This means that most of the 16-bit values for the next output are (heuristically) likely to be possible.
Thus, your best bet might be to look at how the generator is seeded. I have a vague recollection that Java's PRNG is poorly seeded, using a seed that has less than 48 bits of entropy. If this is the case, then it might be possible to predict the next output, by enumerating candidates for the initial seed and seeing which ones are consistent with the outputs you've observed.
If you need to enumerate which values for the next output are possible, here is a way to do it.
The naive way is to enumerate all $2^{32}$ possible values of seed[i]
(you know its top 16 bits, thanks to your knowledge of R[i]
, so you just need to enumerate all possibilities for its low 32 bits), then test which ones are compatible with the observed value of R[i+1]
, and for each one that survives, compute the resulting value of R[i+2]
. This takes about $2^{32}$ steps of computation, so you can probably make it run in a few seconds or tens of seconds of computation power.
With a little bit of cleverness, you can make this run a lot faster. Since we know the value of R[i+1]
, we know the range of possible values for seed[i+1]
: in particular, we know that 2^32 * R[i+1] <= seed[i+1] <= 2^32 * R[i+1] + 2^32 - 1
. Also, we know that seed[i+1] = 0x5DEECE66D * seed[i] + 11 - c * 2^48
for some c
in the range 0x5DEEC * R[i] <= c <= 0x5DEED * (R[i]+1)
. Moreover, we know the top 16 bits of seed[i]
, so we can write seed[i] = 2^32 * R[i] + x
, for some integer x
satisfying 0 <= x <= 2^32 - 1
.
Combining all of this, it follows that
2^32 * R[i+1] <= 0x5DEECE66D * 2^32 * R[i] + 0x5DEECE66D * x + 11 - c * 2^48 <= 2^32 * R[i+1] + 2^32 - 1
or equivalently,
(2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] - 11 - c * 2^48)/0x5DEECE66D <= x <= (2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] + 2^{32} - 12 - c * 2^48)/0x5DEECE66D
This range is of width less than 1, so if you know the left-hand-side and the right-hand-side, you can immediately infer x
.
Thus, if we know c
, then the value of x
is determined, which reveals seed[i]
and thus the next output of the generator. Finally, there are only about 0x5DEED
$\approx 380,000$ possible values of c
.
This gives an algorithm that enumerates all possible values for the next output, using about $380,000$ steps of computation. We enumerate over all $380,000$ possible values of c
; for each possible value of c
, we round (2^32 * R[i+1] - 0x5DEECE66D00000000 * R[i] + 2^{32} - 12 - c * 2^48)/0x5DEECE66D
down to the nearest integer, call it x
, and then we infer the value of seed[i]
(namely, seed[i] = 2^32 * R[i] + x
) and run the generator for two steps to observe the implied next output. We collect all possible next outputs of the generator. This gives us the set of all possible values for the next output. Each iteration uses just a few simple arithmetic operations, and we do $380,000$ iterations, so this procedure should run extremely fast: in milliseconds or less.
R[i+2]
). Ah if you had three values ofR[]
, even non-contiguous... Other idea: the question is similar enough to this one that perhaps the method in that answer can help to compute the exact distribution of the possibleR[i+2]
givenR[i]
andR[i+1]
, assuming flat randomseed[0]
; I don't know for sure. $\endgroup$ – fgrieu♦ Jan 28 '14 at 7:09R[i]
=42 andR[i+1]
=2014, then for certainR[i+2]
is not among {0, 4, 9, 12, 13, 21, 24, 33, 38, 45, 46, 54, 68, 71, 80, 83, 92, 95, 100, 104, ..}, and it has odds 3/65537 to be among {201, 888, 1517, 1959, 2402, 3031, 3717, 4160, 4346, 4789, 5231, 6547, 6989, ..}. In a game, that could help. My quick and dirty brute program to compute such statistics runs in seconds for any given (R[i]
,R[i+1]
) pairs (it is markedly above your 30k steps bound, but likely that can be improved by the method I pointed to). $\endgroup$ – fgrieu♦ Jan 28 '14 at 20:08R[i+2]
, assuming flat distribution ofseed
,R[i]
=42 andR[i+1]
=2014. $\endgroup$ – fgrieu♦ Jan 29 '14 at 6:52