From:

Eric Sosman <esosman@ieee-dot-org.invalid>

Newsgroups:

comp.lang.java.programmer

Date:

Tue, 06 Nov 2007 08:18:50 -0500

Message-ID:

<hcidnbA2P78g9K3anZ2dnUVZ_uiknZ2d@comcast.com>

Piotr Kobzda wrote On 11/05/07 14:28,:

I don't know. [...]

[...]

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?

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

Generated by PreciseInfo ™

"With all of the evidence to the contrary," the district attorney said

to the defendant,

"do you still maintain Nasrudin, that your wife died of a broken heart?"

"I CERTAINLY DO," said Mulla Nasrudin.

"IF SHE HAD NOT BROKEN MY HEART, I WOULDN'T HAVE SHOT HER."

to the defendant,

"do you still maintain Nasrudin, that your wife died of a broken heart?"

"I CERTAINLY DO," said Mulla Nasrudin.

"IF SHE HAD NOT BROKEN MY HEART, I WOULDN'T HAVE SHOT HER."