I think I've found a good solution to the problem. Note though, I was
approaching the problem as an algorithmic puzzle. If I needed to use
this in real code, I would just google the web for some premade
solution, that is certainly the best thing to from a software
development perspective. I wouldn't be spending time trying to roll my
So this is what I got:
It uses a random generator to generator a coin toss (either one or
zero). It basically looks at the range of numbers to generate, and
uses a coin toss to decide whether to generate a random number in the
lower half, or the upper half, and then continues recursively until
the range is small enough to be just one choice. It runs in
log2(max-min) complexity then, so that's good. Similar to a binary
search. In fact it was when I thought of binary searches that I took
inspiration for this idea (and a similar problem that I read on a book
The only tricky thing is dealing with odd ranges. If a range is odd
(say min=2 max = 6), you can't split it in half neatly. If you just
assign the middle element to the same half you will break the uniform
The solution was to make another coin toss to determine whether the
middle element would be included in the half to process or not (giving
it a 50% chance to be included, just like any other numbers).
I tested it a bit, but not extensively, so I don't know if there is
any minor bug or not. But the basic algorithm should work... @_@
On Fri, Jan 25, 2013 at 5:03 PM, Bruno Medeiros
<[address removed]> wrote:
> Interesting problem! I knew when I saw your original post that it must
> be trickier that what it looked at first.
> Any code that uses (max - min) where max and min are longs is broken
> because of the issue of long overflow. That could easily be solved
> But the hardest part is indeed what Michael pointed out: that the
> "double values between 0.0 and 1.0 is less than the number of long
> values between Long.MIN_VALUE and Long.MAX_VALUE."
> I thought up of two solutions (both generally work by dividing the
> delta in two parts and calculating the random for of each part) which
> strictly speaking do work according to your requirements , but they
> are not good solutions because although they would generate within the
> correct range:
> * the first one is does not generate a uniform distribution. Values on
> the edges of the (max-min) delta would be more likely to be generated,
> potentially a lot more.
> * The second solution does generate a uniform distribution, but
> requires a potentially quite large number of retries to the random
> function call, having a non-deterministic performance...
> I'm still trying to think of something better, which is a problem
> because I have work to do, damn you!!