addressalign-toparrow-leftarrow-rightbackbellblockcalendarcameraccwcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-checkcircle-with-crosscircle-with-pluscrossdots-three-verticaleditemptyheartexporteye-with-lineeyefacebookfolderfullheartglobegmailgooglegroupshelp-with-circleimageimagesinstagramFill 1linklocation-pinm-swarmSearchmailmessagesminusmoremuplabelShape 3 + Rectangle 1ShapeoutlookpersonJoin Group on CardStartprice-ribbonShapeShapeShapeShapeImported LayersImported LayersImported Layersshieldstartickettrashtriangle-downtriangle-uptwitteruserwarningyahoo

Re: [ljc] A little Friday morning challenge for the group...

From: Bruno M.
Sent on: Monday, January 28, 2013 12:04 PM
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
own.
So this is what I got:
http://pastebin.c...­

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
once).

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
distribution.
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
> though.
>
> 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!!
>


-- 
Bruno Medeiros

Our Sponsors

  • Our Blog

    Read the latest news from the LJC

  • RecWorks Ltd

    Fixing Tech Recruitment using the Power of Community

  • jClarity

    Java/JVM Performance Analysis Tools & mentoring for Java related matters

  • LJC Aggrity

    Our LJC Aggrity site contains blog posts from our members

  • LJC Book Club

    Our Book club with book reviews from our members

  • Devoxx UK

    Java Community Conference in collaboration with the LJC, 8-10th June 16

  • SkillsMatter

    "Host, help organise, promote, film many of our meetings."

  • IBM

    Build Enterprise-grade apps at start-up speed.

  • New Relic

    New Relic makes sense of billions of metrics a day in real time.

  • Hazelcast

    Hazelcast is the leader in operating in-memory computing.

  • Java.Net

    We are an official Java User Group recognised by Oracle's JUG program

  • JRebel

    Free 3 month J-Rebel license.

  • O'Reilly

    40% discount on printed books and 50% on e-books.

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy