what is the purpose of this line of code?
while (bits - val + (n - 1) < 0);
From a syntactic perspective, it ends the do opened above. From a functional perspective, it makes the pseudo-random number generated uniform on the specified interval. I'll focus on the later aspect.
Assume n was $3\cdot2^{29}\,$ (that is 3<<29) rather than $6$. After the statement bits = next(31); this quantity is uniformly random in $[0,2^{31})$. Therefore val = bits % n; is
bits with probability 75%; and then uniform on $[0,3\cdot2^{29})$- or
bits-(3<<29) with probability 25%; and then uniform on $[0,2^{29})$
It follows that before the while, val is in $[0,2^{29})$ with probability 50%, in $[2^{29},3\cdot2^{29})$ with probability 50%. The second interval is twice as large as the first, and we see that val is very far from uniform on the whole interval $[0,3\cdot2^{29})\ $!
The while repeats the loop when in the problematic second bullet, and thus makes the outcome uniform on the full interval $[0,3\cdot2^{29})$.
Alternate explanation with small numbers
Imagine that, starting from $b=0$, four times: we double $b$, then add $1$ to $b$ if we get a tail from a fair coin throw. The outcome is $b$ a nonnegative integer less than $2^4=16$, and each of these $16$ integers is equally likely. That is, the outcome is a discrete uniform random number $b$ in $[0,16)$.
From this we want a uniform random number $v$ in $[0,6)\,$ just like nextInt(6) is tasked to do. Problem is, if we use a fixed assignment of values of $b$ from $[0,16)$ to values of $v$ in $[0,6)$, the outcome can't be uniform. The most even we can get is that $4$ values of $v$ have probability $3/16$, and the $2$ other $2/16$. Think of separating $16$ mints (the $b$) into $6$ persons (the $v$).
A simple solution to that is: when $b$ is in $[0,6)$, that's our $v$. When $b$ is in $[6,12)\,$, our $v$ is $b-6$. Otherwise, we try again, generating another $b$ using coin throws. That's what the code does in it's do … while loop, only with $2^{31}$ using next(31) where our analogy uses $2^4$ and coin throws; using bits for $b$, and val for $v$.
Off-topic: what's up with bits - val + (n - 1) < 0 ?
One wonders how while (bits - val + (n - 1) < 0); manages to do what's described above. bits is in range [0, 0x7FFFFFFF], n is 6, val is bits % n, thus val < bits holds and bits - val is non-negative. But it does not follow that bits - val + (n - 1) is non-negative, because the operations are carried per two's-complement arithmetic over 32-bit.
That's how int works in Java, many other computer languages, and most modern computer hardware when manipulating signed integers as a 32-bit quantities. If the int quantities u and v represent the integers $u$ and $v$, these integers are both in range $[-2^{31},2^{31}-1]$, then u + v is an int quantity representing an integer $w$ in range $[-2^{31},2^{31}-1]$ with $u+v\equiv w\bmod2^{32}$, that is by definition $u+v-w$ a multiple of $2^{32}$, and depending on values of $(u,v)$ that multiple can be $0$, $2^{32}$, or $-2^{32}$. In the end, $w$ is the integer $((u+v+2^{31})\bmod2^{32})-2^{31}$. That arithmetic is commutative, associative, has neutral zero, and every element has an opposite. A caveat: $-2^{31}$, that is -0x80000000, shares with zero the property of being it's own opposite.
So for example if bits was $2^{31}-2$, val is $0$, bits - val is $2^{31}-2$, bits - val + (n - 1) is $((2^{31}-2+(6-1)+2^{31})\bmod2^{32})-2^{31}$, that is $((2^{32}+3)\bmod2^{32})-2^{31}=3-2^{31}$, and that's negative.
For those that just want to move along: the condition bits - val + (n - 1) < 0 is logically equivalent to bits - val >= ((long)1<<31) + 1 - n (with no overflow and only non-negative quantities, thanks long being 64-bit).
It should now be apparent that bits - val + (n - 1) < 0 holds when bit is at the top of its interval [0, 0x7FFFFFFF]. It is left as an exercise to the reader to show that the rest of the interval contains a multiple of n integers, thus all the n values of val on exit of the loop are exactly as likely, under the assumption that all values of bits are.
How does one reverse engineer
That's already done. The question has reverse-engineered the algorithm, and even more than this: simplified the code from what it is in a recent Java environment by removing the thread-safety stuff (or traveling back in time to get the source before that was added); and thought about removing the part of the code that is demonstrably unreachable in the circumstance.
and find the seed from a set of numbers generated from this procedure?
Next step towards that goes: compute the probability that the condition in the while statement is true when n is $6$, and decide what can be done about this case.
Then proceed. There's several paths to resolution:
- Brute force, trying all $2^{48}$ initial state values. This is feasible, but inelegant and resource-hungry.
- Reducing the above search space by a factor of $6$ by exploiting the first result available.
- Using that $6$ is even to get 18 bits of the seed out of 48 (with fair probability), then brute force the rest. That's relatively simple and educative. It's outlined in this answer of mine. Some combinations with the above tweaks work.
- A that-could-well-work-but-I-didn't-bother-to-try approach using SAT solvers (in same answer).
Likely there are other approaches, but if there's anything readily applicable here or here, I missed it.
If stuck, state at what point at the bottom of the present question.
