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

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

From: user 7.
Sent on: Saturday, January 26, 2013 4:53 PM
I'm going to hands down call Michael my hero. The solution that I came up with is quick and dirty and quite right it won't return every value of long because there are not enough distinct values of double between 0.0 and 1.0 to cover every distinct value of long. The problem with a do while for Random.nextLong() is for a small range you could be generating a huge number of random longs but you should get an equal distribution (it says in the docs that the seed is only 48 bits so you don't get every value of long but I must be too dumb to understand why because the source shows that it simply packs two random ints which it says there should be an approximately equal distribution). Michael's solution while quite long tackles to problem of nextLong by increasing the probability of a match by only generating a number with the amount of bits required to represent the range, this will reduce the number of potential loops to return a match within the required range. Genius and my hero.


On Sat, Jan 26, 2013 at 3:38 PM, Wesley Hall <[address removed]> wrote:
Michael,

Nice :). I would have to say that all the bit shifting and binary
mathematics is probably a good sign that you are smarter than I am.
Curse these inconvenient ten fingers ;).

Jahan,

Yeah, actually once I figured out the max - min problem, then the next
step my mind took was to do some midpoint calculations. I put your
solution into my IDE and tested it and it appears to work beautifully,
the only anomaly I can see is that for a range -100 to 100, then 0 is
about twice as frequent as any other given result.



On Sat, Jan 26, 2013 at 12:33 PM, Michael Rogers
<[address removed]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 25/01/13 11:01, Wesley Hall wrote:
>> Your mission, should you choose to accept it, is to write a method,
>> in Java, with the following signature...
>>
>> public static long generateRandom(long min, long max) { // code
>> here }
>
> My attempt (rather heavyweight but I think it's correct):
>
> import java.math.BigInteger;
> import java.util.Random;
>
> public class LongRandom {
>
>     private static final Random random = new Random();
>
>     public static long generateRandom(long min, long max) {
>         BigInteger bigMin = BigInteger.valueOf(min);
>         BigInteger bigMax = BigInteger.valueOf(max);
>         BigInteger exclusive = bigMax.subtract(bigMin);
>         BigInteger inclusive = exclusive.add(BigInteger.ONE);
>         // Work out how many bytes we need to generate
>         int bits = exclusive.bitLength();
>         int bytes = (bits % 8 == 0) ? bits / 8 : bits / 8 + 1;
>         assert bytes > 0 && bytes <= 8;
>         // The PRNG generates bytes, so there will be up to 7 spare bits
>         int spareBits = bytes * 8 - bits;
>         assert spareBits >= 0 && spareBits < 8;
>         // Mask out the spare bits each time we generate bytes
>         int mask = 0xff;
>         for(int i = 0; i < spareBits; i++) mask ^= 1 << (7 - i);
>         // Generate random bytes until we get a value in the required
>         // range (unlike the modulus, this gives a uniform distribution)
>         byte[] b = new byte[bytes];
>         BigInteger rand;
>         do {
>             random.nextBytes(b);
>             b[0] &= mask; // Mask out the spare bits
>             rand = new BigInteger(1, b); // Positive signum
>         } while(rand.max(inclusive).equals(rand));
>         rand = rand.add(bigMin);
>         assert rand.min(bigMin).equals(bigMin); // rand >= min
>         assert rand.max(bigMax).equals(bigMax); // rand <= max
>         return rand.longValue();
>     }
> }
>
> Cheers,
> Michael
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
>
> iQEcBAEBAgAGBQJRA8esAAoJEBEET9GfxSfM3ZoIAIPXmuAFuU4+zzQi0mGUd2vL
> X3d7z0fO1PsKYRLiD4wvgtz6u8gcwfCpLLj7EXvLR0uC4O6MbgAbQdIBzkUAH+ly
> IkftRzwOpWwLhUnaoK01Cqa2dzCQ+3lfWN59uz8Qmjs6UDEW0PoedlKLlcpJUn66
> YrfaUoDDvzODs/jyuqwYmC4loqDcDWI6WyE/Wpk3D0NNDJmBG6tdqUSDkum4DcgI
> q0QA4SUKusM0vSDhf69aqc+yiVByZ/1robvSuTAT5sk3fmmdF09ZH32aPpJB36pA
> MCGDtWnFLEGjQ0pMNUUa99PMMErQzA08ut8lscfCW4Vz3IEzQ6pK1GOeVmcIa68=
> =LuNA
> -----END PGP SIGNATURE-----
>
>
>
>
> --
> Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
> http://www.meetup.com/Londonjavacommunity/
> This message was sent by Michael Rogers ([address removed]) from LJC - London Java Community.
> To learn more about Michael Rogers, visit his/her member profile: http://www.meetup.com/Londonjavacommunity/members/49372592/
> Set my mailing list to email me
>
> As they are sent
> http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=1
>
> In one daily email
> http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=2
>
> Don't send me mailing list messages
> http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=0
> Meetup, POB 4668 #37895 NY NY USA 10163 | [address removed]
>




--
Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
http://www.meetup.com/Londonjavacommunity/
This message was sent by Wesley Hall ([address removed]) from LJC - London Java Community.
To learn more about Wesley Hall, visit his/her member profile: http://www.meetup.com/Londonjavacommunity/members/15396461/
Set my mailing list to email me

As they are sent
http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=1

In one daily email
http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=2

Don't send me mailing list messages
http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=0
Meetup, POB 4668 #37895 NY NY USA 10163 | [address removed]


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