random real number between 0 (inclusive) and 1 (inclusive)

[Piotr Kobzda]

Sorry if this is a double post, network problems...

Piotr Kobzda wrote:
Patricia Shanahan wrote:

[...]

How about first obtaining a long in the range [0,2^53]. That could be
done by combining the results of a couple of nextInt calls. Then
divide
by (double)(1L << 53).

Or, instead of using nextInt() calls, the following should work as
well:

Random r = new Random() {
public double nextDouble() {
return (((long)(next(26)) << 27) + next(27) + next(1))
/ (double)(1L << 53);
}
};

If you are going to do that you have to extend Random, because next is
protected.

Patricia

He did extend Random.
Although, my argument would be that he shouldn't override nextDouble,
but create a new method, as the new method has different semantics than
the original nextDouble.

Yup, I realized that, and canceled my message just after I sent it, but
cancel does not always catch up :-(

I agree that the new method should be given a different name, because of
the different semantics.

Yes, you are both right. In fact, I have had a different name of that
method in my initial approach, but have changed that for simplicity just
while editing my post.

Of course, the general purpose solution should not change nextDouble()
semantics.

But the problem here is, that the general purpose implementation must
extend the concrete Random implementation (which can not be anonymous
class). The best approach I can think of to achieve that might look as
follows:


public class RandomExtend extends java.util.Random {

public interface BitsProvider {
int nextBits(int numBits);
void setSeed(long seed);
}

protected BitsProvider bitsProvider;

private class DefaultBitsProvider implements BitsProvider {

public final int nextBits(int numBits) {
return RandomExtend.this.defaultNext(numBits);
}

public final void setSeed(long seed) {
RandomExtend.this.defaultSetSeed(seed);
}
}

public RandomExtend() {
super();
this.bitsProvider = new DefaultBitsProvider();
}

public RandomExtend(long seed) {
super(seed);
this.bitsProvider = new DefaultBitsProvider();
}

public RandomExtend(BitsProvider bitsProvider) {
super(0L);
this.bitsProvider = bitsProvider;
}

@Override
protected final int next(int numBits) {
return bitsProvider.nextBits(numBits);
}

@Override
public void setSeed(long seed) {
bitsProvider.setSeed(seed);
}

final int defaultNext(int bits) {
return super.next(bits);
}

final void defaultSetSeed(long seed) {
super.setSeed(seed);
}

public double nextDoubleWith1() {
return (((long)(next(26)) << 27) + next(27) + next(1))
/ (double)(1L << 53);
}
}

Note that the above implementation allows for any concrete Random
support through the use of BitsProvider interface (any Random
implementation, including SecureRandom, even when not extendable may be
supported with that).

However, as you can see, there is much more coding necessary than in the
approach with broken semantics of nextDouble() in anonymous class.

So, is that all extra coding really worth the effort? I think, that
"yes" is not always the only right answer...


piotr

 

[Eric Sosman]

[...]
But the problem here is, that the general purpose implementation must
extend the concrete Random implementation (which can not be anonymous
class). The best approach I can think of to achieve that might look as
follows: [...]

Encapsulation might be a better choice than extension,
and would certainly be less troublesome to code.

public class FunnyRandom {
private final Random rand = new Random();
public double nextInclusiveDouble() {
// flawed implementation:
double r = rand.nextDouble();
return rand.nextBoolean() ? r : 1.0 - r;
}
}

If you wanted, you could add a constructor that supplies
a pre-existing Random instead of generating a new one, and/or
an access method to return a reference to the internal Random,
and assorted other decorations. But it doesn't seem to me
that there's any compelling reason that a generator of a
special distribution should also "be a" Random.

(As discussed elsethread, the value of implementing this
particular special distribution is questionable. Also, even
though I proposed the algorithm shown here, I have since
realized that it is incorrect. As I wrote when I suggested it,
"trust, but verify.")

 

[Piotr Kobzda]

[...]
But the problem here is, that the general purpose implementation must
extend the concrete Random implementation (which can not be anonymous
class). The best approach I can think of to achieve that might look
as follows: [...]

Encapsulation might be a better choice than extension,
and would certainly be less troublesome to code.

Yup, that's often a better choice.

public class FunnyRandom {
private final Random rand = new Random();
public double nextInclusiveDouble() {
// flawed implementation:
double r = rand.nextDouble();
return rand.nextBoolean() ? r : 1.0 - r;
}
}

If you wanted, you could add a constructor that supplies
a pre-existing Random instead of generating a new one, and/or
an access method to return a reference to the internal Random,
and assorted other decorations. But it doesn't seem to me
that there's any compelling reason that a generator of a
special distribution should also "be a" Random.

There is no real need to do so. The reason for me was to combine
default implementation of Random with encapsulated "accessor"
(BitsProvider) of the protected next() of Random. BTW, maybe better
would be calling it RandomDelegate instead of RandomExtend...

When we don't want delegation model (a bit tricky BTW, there are only
two methods delegated), we just don't need setSeed() in proposed
BitsProvider interface. However, "something" should still extend
concrete Random implementation in order to access its next(), otherwise
it must be simulated, e.g. using nextInt(), as proposed earlier by Patricia.

So, as long as an implementation does not needs the next() access (as in
your example) there is no need for Random extension.

(As discussed elsethread, the value of implementing this
particular special distribution is questionable. Also, even
though I proposed the algorithm shown here, I have since
realized that it is incorrect. As I wrote when I suggested it,
"trust, but verify.")

Well, there is no need for that in the _final_ problem of the OP, no
question on that. Proposed here is the solution of the _original_
problem, i.e. with no mention of taking just "two billion" distribution
(that's the goal added later by the OP). The proposed solution is just
to generate random sequence of doubles containing 1 with the same
(approximately) probability as for the other doubles. Do you think it's
incorrect for that?


piotr

 

[Eric Sosman]

Piotr Kobzda wrote On 11/05/07 11:55,:

public class FunnyRandom {
private final Random rand = new Random();
public double nextInclusiveDouble() {
// flawed implementation:
double r = rand.nextDouble();
return rand.nextBoolean() ? r : 1.0 - r;
}
}

[...]
(As discussed elsethread, the value of implementing this
particular special distribution is questionable. Also, even
though I proposed the algorithm shown here, I have since
realized that it is incorrect. As I wrote when I suggested it,
"trust, but verify.")

Well, there is no need for that in the _final_ problem of the OP, no
question on that. Proposed here is the solution of the _original_
problem, i.e. with no mention of taking just "two billion" distribution
(that's the goal added later by the OP). The proposed solution is just
to generate random sequence of doubles containing 1 with the same
(approximately) probability as for the other doubles. Do you think it's
incorrect for that?

Yes. The nextDouble() call produces 0.0 and 0.125 and
0.675 and ... with equal probability (to the limits of the
underlying PRNG); call it probability P. My modification
produces 0.0 with probability P/2 and 1.0 with probability
P/2, while 0.375 and so on still have probability P: the
returned values are not equiprobable. (In effect, I've
"smeared" the original probability of 0.0 across the two
values 0.0 and 1.0.)

The easiest way I can think of to meet the original
requirement is to use a rejection technique, as in

double nextInclusiveDouble() {
long number;
do {
number = ( ((long)rand.next(27) << 27)
+ rand.next(27);
} while (number > 1L << 53);
return number / (double)(1L << 53);
}

The loop executes at least once, more than once about 1/2
the time, more than twice 1/4 of the time, ... for an
average of two executions per method call. That's not
an especially wonderful ratio for rejection, but I can't
think of an alternative that wouldn't risk introducing
a bias somewhere.

 

[Piotr Kobzda]

Piotr Kobzda wrote On 11/05/07 11:55,:

[...] The proposed solution is just
to generate random sequence of doubles containing 1 with the same
(approximately) probability as for the other doubles. Do you think it's
incorrect for that?

Yes. The nextDouble() call produces 0.0 and 0.125 and
0.675 and ... with equal probability (to the limits of the
underlying PRNG); call it probability P. My modification
produces 0.0 with probability P/2 and 1.0 with probability
P/2, while 0.375 and so on still have probability P: the
returned values are not equiprobable. (In effect, I've
"smeared" the original probability of 0.0 across the two
values 0.0 and 1.0.)

OK, now I see your point, thanks for explanation. The same
incorrectness I think applies to my previous proposition.

The easiest way I can think of to meet the original
requirement is to use a rejection technique, as in

double nextInclusiveDouble() {
long number;
do {
number = ( ((long)rand.next(27) << 27)
+ rand.next(27);
} while (number > 1L << 53);
return number / (double)(1L << 53);
}

The loop executes at least once, more than once about 1/2
the time, more than twice 1/4 of the time, ... for an
average of two executions per method call. That's not
an especially wonderful ratio for rejection, but I can't
think of an alternative that wouldn't risk introducing
a bias somewhere.

Nice.

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?


piotr

 

[Piotr Kobzda]

Piotr Kobzda wrote On 11/05/07 11:55,:

[...] The proposed solution is just
to generate random sequence of doubles containing 1 with the same
(approximately) probability as for the other doubles. Do you think it's
incorrect for that?

Yes. The nextDouble() call produces 0.0 and 0.125 and
0.675 and ... with equal probability (to the limits of the
underlying PRNG); call it probability P. My modification
produces 0.0 with probability P/2 and 1.0 with probability
P/2, while 0.375 and so on still have probability P: the
returned values are not equiprobable. (In effect, I've
"smeared" the original probability of 0.0 across the two
values 0.0 and 1.0.)

OK, now I see your point, thanks for explanation. The same
incorrectness I think applies to my previous proposition.

The easiest way I can think of to meet the original
requirement is to use a rejection technique, as in

double nextInclusiveDouble() {
long number;
do {
number = ( ((long)rand.next(27) << 27)
+ rand.next(27);
} while (number > 1L << 53);
return number / (double)(1L << 53);
}

The loop executes at least once, more than once about 1/2
the time, more than twice 1/4 of the time, ... for an
average of two executions per method call. That's not
an especially wonderful ratio for rejection, but I can't
think of an alternative that wouldn't risk introducing
a bias somewhere.

Nice.

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] seems to be equal. Is it
correct?


piotr

 

[Piotr Kobzda]

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;

Woops, zero is impossible that way. Math.nextUp(1d) should be used
instead of 1d here.

return lastr = r;
}

piotr

 

[Piotr Kobzda]

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;

Woops, zero is impossible that way. Math.nextUp(1d) should be used
instead of second 1d here.

return lastr = r;
}

piotr

 

[Patricia Shanahan]

Woops, zero is impossible that way. Math.nextUp(1d) should be used
instead of second 1d here.

There is a more general solution approach that splits the problem into
two parts:

1. Construct a long equivalent of nextInt(int), using the same
implementation approach.

2. use nextLong((1L<<53)+1)/(double)(1L<<53)

Patricia

 

[Hunter Gratzner]

To put it yet another way: The population of Costa Rica
is approximately four million, but you happen to know that
one of these "people" is actually a space alien. You have
a special detector that can test whether someone is a space
alien or an authentic homo sapiens, but you can use it only
once: The detector's theta ray generator shorts out and
fuses to a useless mass on its first and only discharge.
Here's your plane ticket to Costa Rica; your mission is
to bring back the ET. What do you think of your chances?

Chances? Who cares about chances? I volunteer to do the experiment.

Send the ticket - free holiday in Costa Rica
Send the detector - will catch a fortune when sold on eBay

 

[Dr J R Stockton]

In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r
@4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <[email protected]
om.invalid> posted:

Multiply the number by 1+ulp where ulp in the smallest increment in a
double in the vicinity of 1.0

By stretching [0, 1) to cover [0, 1] there is necessarily a hole
created, perhaps at 0.5 .

By creating random R in [0, 1) and doing if (R==0.5) { R = 1 } ;
(apologies; I'm slowly learning to read Java;
writing it properly may follow)
one also gets a hole.

Now replace 0.5 by a random in [0, 1) independently generated and
renewed each time it is hit (so not correlated with the main Random),
and ISTM that all values in [0, 1] should be obtained with virtually
equal probability.

 

[Piotr Kobzda]

There is a more general solution approach that splits the problem into
two parts:

1. Construct a long equivalent of nextInt(int), using the same
implementation approach.

There is a long used in implementation for computations, so equivalent
nextLong(long) will need 126 bits (or two longs) to do the similar --
not so straightforward reimplementation...

2. use nextLong((1L<<53)+1)/(double)(1L<<53)

I think that the Eric's approach (a "rejection technique") is "almost"
equivalent to the above steps. It just omits the optimization, i.e. the
special treatment of the power of 2 cases.


piotr

 

[Piotr Kobzda]

There is a long used in implementation for computations, so equivalent
nextLong(long) will need 126 bits (or two longs) to do the similar --
not so straightforward reimplementation...

But that's the problem of the optimization only. Fortunately, do not
applies to the heart of the algorithm implemented there.

The following should work as expected:

public long nextLong(long n) {
//...

long bits, val;
do {
bits = next(63);
val = bits % n;
} while (bits - val + (n-1) < 0);
return val;
}


piotr

 

[Richard F.L.R.Snashall]

There is a more general solution approach that splits the problem into
two parts:

1. Construct a long equivalent of nextInt(int), using the same
implementation approach.

2. use nextLong((1L<<53)+1)/(double)(1L<<53)

How about, if the random is less than or equal to 1/2, use it; otherwise
generate another and subtract half of that from 1.0? The only
risk I can think of will be the possibility of giving 0.5 too much
probability, depending on the rounding mode.

 

[Eric Sosman]

Hunter Gratzner wrote On 11/05/07 15:18,:

Chances? Who cares about chances? I volunteer to do the experiment.

Send the ticket - free holiday in Costa Rica
Send the detector - will catch a fortune when sold on eBay

Your ticket and the detector are in the mail, along
with the latest batch of purple pills and the, er, latex
novelty items you ordered. Glad, as always, to provide
service to my long-time customers!

;-)

 

[Lew]

To put it yet another way: The population of Costa Rica
is approximately four million, but you happen to know that
one of these "people" is actually a space alien. You have
a special detector that can test whether someone is a space
alien or an authentic homo sapiens, but you can use it only
once: The detector's theta ray generator shorts out and
fuses to a useless mass on its first and only discharge.

Why not simply look for the bent pinky finger?

 

[Eric Sosman]

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. `lastr' is essentially the fractional
part of the sum of N uniformly-distributed values. The
sum itself will converge toward a normal distribution as
N increases, so the question is about the distribution
of X mod 1 when X is normally distributed. It's possible
that the distribution of X mod 1 is uniform, but it's not
"obvious." Not to me, anyhow.

 

[Patricia Shanahan]

In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r
@4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <[email protected]
om.invalid> posted:

Multiply the number by 1+ulp where ulp in the smallest increment in a
double in the vicinity of 1.0

By stretching [0, 1) to cover [0, 1] there is necessarily a hole
created, perhaps at 0.5 .

By creating random R in [0, 1) and doing if (R==0.5) { R = 1 } ;
(apologies; I'm slowly learning to read Java;
writing it properly may follow)
one also gets a hole.

Now replace 0.5 by a random in [0, 1) independently generated and
renewed each time it is hit (so not correlated with the main Random),
and ISTM that all values in [0, 1] should be obtained with virtually
equal probability.

The Java code would be something like:

double nextInclusiveDouble(){
double r = nextDouble();
return r == nextDouble() ? 1 : r;
}

If we were using a true random number generator, this would be close to
perfect. Let N be 2**53, the number of different nextDouble results, and
assume they are uniformly distributed and the results of consecutive
calls are independent.

The two nextDouble calls have N*N possible results. Of those, N give
result 1. N-1 of the pairs result in e.g. 0. N numbers are each chosen
with probability (N-1)/(N*N), and 1.0 is chosen with probability
N/(N*N)=1/N.

This is indeed close enough that I don't think the difference would be
measurable over the probable lifetime of Java.

Does anyone know whether nextDouble produces pairs of consecutive equal
numbers with the correct probability, remembering that it is based on a
pseudo-random number generator?

Patricia

 

[Christian]

In comp.lang.java.programmer message <jnasi31porsaqq0nb4u3r6mkdt3otanu9r
@4ax.com>, Sun, 4 Nov 2007 20:28:11, Roedy Green <[email protected]
om.invalid> posted:

What I need is to generate a lot of random real numbers between 0 and
1, both inclusive (normally it's possible to generate the number
between 0(inclusive) and 1 (exclusive!!!) )
Multiply the number by 1+ulp where ulp in the smallest increment in a
double in the vicinity of 1.0

By stretching [0, 1) to cover [0, 1] there is necessarily a hole
created, perhaps at 0.5 .

By creating random R in [0, 1) and doing if (R==0.5) { R = 1 } ;
(apologies; I'm slowly learning to read Java;
writing it properly may follow)
one also gets a hole.

Now replace 0.5 by a random in [0, 1) independently generated and
renewed each time it is hit (so not correlated with the main Random),
and ISTM that all values in [0, 1] should be obtained with virtually
equal probability.

The Java code would be something like:

double nextInclusiveDouble(){
double r = nextDouble();
return r == nextDouble() ? 1 : r;
}

If we were using a true random number generator, this would be close to
perfect. Let N be 2**53, the number of different nextDouble results, and
assume they are uniformly distributed and the results of consecutive
calls are independent.

The two nextDouble calls have N*N possible results. Of those, N give
result 1. N-1 of the pairs result in e.g. 0. N numbers are each chosen
with probability (N-1)/(N*N), and 1.0 is chosen with probability
N/(N*N)=1/N.

This is indeed close enough that I don't think the difference would be
measurable over the probable lifetime of Java.

Does anyone know whether nextDouble produces pairs of consecutive equal
numbers with the correct probability, remembering that it is based on a
pseudo-random number generator?

Patricia

really nice solution I like it
...
though I doubt even just using nextDouble() could be measured over the
usual lifetime
2 ** 53 doubles and you will need at least log n more experiments if I
am not wrong until you can really measure something is wrong (chernov
was it?) .. so its about 2**60 which results if 1 Billion numbers can be
generated per second in 36 years of computing power.

using anything else but simple nextDouble() seems to be overkill.

 

[Piotr Kobzda]

Patricia Shanahan wrote:

[...]

Does anyone know whether nextDouble produces pairs of consecutive equal
numbers with the correct probability, remembering that it is based on a
pseudo-random number generator?

To produce that, the default generator (a linear congruential generator)
implemented in java.util.Random must generate a sequence of two
consecutive equal pairs of 26, and 27 bits (both higher) of 48 bits of
four consecutive seeds. Where each seed is generated using the
following formula:

seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

As you can see, that's not easy to guess (at least to me) if that ever
happens. And unfortunately, my machine would require about two years to
check a whole period (2^48 at most) of the generator defined like that.

There are of course other pseudo-random number generators which makes
your question even harder to be answered... So, I don't know the
answer. But I like the idea.


piotr