Re: random real number between 0 (inclusive) and 1 (inclusive)
Eric Sosman wrote:
Piotr Kobzda wrote On 11/05/07 14:28,:
[...]
So, what do you think about the following:
private double lastr = rand.nextDouble();
public double nextInclusiveDouble() {
double r = lastr + rand.nextDouble();
if (r > 1d) r -= 1d;
return lastr = r;
}
The probability of each double in range [0, 1] seams to equal. Is it
correct?
I don't know. [...]
... but I've been thinking about it, and I've found the
answer. Three answers, in fact: Yes, No, and Maybe.
YES: The first number returned is the sum of two uniformly
distributed values, possibly minus one. Call the two uniform
values X and Y, and think of them as coordinates in the unit
square. The returned value is x+y for any point in the lower
left triangle or x+y-1 in the upper right triangle. This value
will be less than some chosen r, 0<=r<=1, if (x,y) is in a small
triangle at the origin (where x+y<r) or in a band just above the
diagonal (where 1<x=y<1+r). The area of the small triangle is
0.5*r^2, and the area of the band is 0.5-0.5*(1-r)^2. Add those,
and the total area in which the returned value is <r comes to r,
which is precisely the definition of a uniformly distributed
variable. So lastr is uniform after the first use, and will
remain uniform for all subsequent uses: the lastr from one use
becomes the X of the next one, with nextDouble contributing a
new Y, and the same argument applies all over again.
NO: The above assumes sums and differences are computed with
perfect accuracy, but in fact a double has finite precision: 53
bits for Java (one implicit, for normalized values). To keep
the illustration easy, imagine that double had only five bits of
precision. Express X and Y as binary fractions .xxxxx and .yyyyy,
where the x's and y's are jumbles of 1's and 0's. If the sum
z=x+y is less than 1, it looks like .zzzzz and all is well. But
if it's 1 or greater, it's 1.zzzz: one bit has been rounded off.
Now subtract 1 from this, and you get .zzzz0 -- that is, after a
subtraction step, the lowest-order fraction bit is necessarily
zero. If x+y<1 the low-order bit is about equally likely to be
zero or one, but the other half of the time it is always zero;
all in all, the low-order bit is zero 75% of the time and one
only 25% of the time. (A comment in the source of nextDouble
says that early versions of that method had a related bug.)
MAYBE: A double has 53 bits of precision when stored, but
some JVM's use higher precision in intermediate computations if
strictfp is not specified. On such JVM's, the sum of x+y might
be 1.zzzz (rounded) or 1.zzzzz (exact, in a high-precision CPU
register), and in the latter case subtracting 1 will not introduce
a low-order 0. So you're at the mercy of the particular JVM and
of exactly how the JIT decides to compile the byte code.
"Go not to c.l.j.p. for advice, for they will say both Yes
and No -- and sometimes Maybe."
--
Eric Sosman
esosman@ieee-dot-org.invalid