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.