-2

How can I pick a random number from the following set:

  • All positive integers that can be represented exactly by a double precision floating point number (i.e. a Java double).

Distribution

In my particular use case, I don't need uniform distribution. I am, however, academically interested in such a solution. Also, uniform could be interpreted in (at least) 2 different ways:

  • The distribution is uniform in [0, Double.MAX_VALUE].
  • The probability of picking each possible value is equal.
Bart van Heukelom
  • 43,244
  • 59
  • 186
  • 301
  • 2
    Where is your tried code ? – Suresh Atta Oct 14 '14 at 12:48
  • 1
    What do you mean by exactly ? – Emrys Myrooin Oct 14 '14 at 12:48
  • 1
    what do you mean by `exactly by a double precision floating point number`? – amit bhardwaj Oct 14 '14 at 12:49
  • http://stackoverflow.com/questions/15643067/range-of-integers-that-can-be-expressed-precisely-as-floats-doubles – assylias Oct 14 '14 at 12:53
  • It's quite an interesting set, however! The set contains: `1, 2, 12345, 1.2345e100`; and doesn't contain `1234567891234567891234` – Dmitry Bychenko Oct 14 '14 at 12:54
  • Suresh: What I tried is `Math.round(random.nextDouble())`, forgetting that `nextDouble` returns between 0 and 1, not all possible double values. Emrys: Given the number as a `long`, that `number == (long)((double)number)` – Bart van Heukelom Oct 14 '14 at 12:55
  • 3
    Why all the downvotes? In my opinion the question is both interesting (if perhaps not very practical) and sufficiently precise... – Bart van Heukelom Oct 14 '14 at 12:57
  • @BartvanHeukelom I don't think downvoters have understood the question. – assylias Oct 14 '14 at 13:12
  • Do you need to be able to draw every number in the set with equal probability? If so then this is a *very* interesting question. Else you could draw a double, multiply by Double.MAX_VALUE and test that result to see it if it's an integer. – Bathsheba Oct 14 '14 at 14:33
  • 1
    Confessions of a downvoter: Edited the question so I can upvote. This question is going to bug me all afternoon. – Bathsheba Oct 14 '14 at 14:37
  • So what is it? (1) uniformly from the set or (2) such that the resulting distribution is uniform? Do let me know if the difference is not obvious to you. – Bathsheba Oct 14 '14 at 14:40
  • @Bathsheba: Though I may occasionally use the wrong terms, the difference is clear. I don't care either way, this question is purely academical now. I've found that in my use case it's easier to just generate a random 48 bit unsigned integer (`nextLong() & 0xFFFF_FFFF_FFFF`), since that's a large enough space and all values can be represented by a `double`. – Bart van Heukelom Oct 14 '14 at 14:59

2 Answers2

2

Given that doubles are 64 bits you could generate 8 bytes of randomness and use NIO to get the corresponding double, this should provide full coverage I think... however it wouldn't produce a uniform distribution.

Random random = new Random();
byte[] buffer = new byte[8];
random.nextBytes(buffer);

System.out.println(Math.abs(Math.round(ByteBuffer.wrap(buffer).getDouble())));

I've been reminding myself how doubles are represented in Java by looking at double 64 binary layout, there are 11 bits for the exponent and 52 bits for the fraction. I think an answer that provides a uniform distribution would be pretty tricky

Adam
  • 35,919
  • 9
  • 100
  • 137
  • I did think of something like that. Of course, you'd need to apply `round` and `abs` to make it a positive integer. I don't think the distribution would be very uniform. That's not a problem in my current use case, but it hurts the perfectionist inside :) – Bart van Heukelom Oct 14 '14 at 13:28
  • If you study the spec. for IEEE 754 you could combine that with my approach... http://en.wikipedia.org/wiki/IEEE_floating_point – Adam Oct 14 '14 at 13:30
  • 1
    +1 for mentioning the fact that the resulting distribution is not uniform. – Bathsheba Oct 14 '14 at 14:19
0

I've thought of the following untested methods.

The distribution is uniform in [0, Double.MAX_VALUE].

  • Generate a random BigInteger between 0 and Double.MAX_VALUE (here).
  • Apply doubleValue()

The probability of picking each possible value is equal.

  • Create a buffer of 64 bits.
  • Set the sign to positive.
  • Set the exponent randomly between 1 and 1023.
  • Fill the rest (the fraction) with random bits.
  • If the number is not normalized (e.g. it's 200 * 2, where the normalized version is 400 * 1), discard it and try again.
Bart van Heukelom
  • 43,244
  • 59
  • 186
  • 301