addressalign-toparrow-leftarrow-rightbackbellblockcalendarcameraccwchatcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-checkcircle-with-crosscircle-with-pluscrosseditemptyheartfacebookfolderfullheartglobegmailgoogleimagesinstagramlinklocation-pinmagnifying-glassmailminusmoremuplabelShape 3 + Rectangle 1outlookpersonplusprice-ribbonImported LayersImported LayersImported Layersshieldstartickettrashtriangle-downtriangle-uptwitteruseryahoo

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

From: user 7.
Sent on: Sunday, January 27, 2013 1:51 AM
Another attempt from me Friday's teaser extends to Sunday... Thanks Wes, because I wasn't quite happy with the do while loop. This uses lots of BigDecimals instead...

    // To avoid the mucky do while loop we need a number format that
    // returns 0.0 to 1.0 but has enough distinct values to represent
    // all values of long.
   
    // The total range of numbers [1] represented by a long is 2 ^ 64 - 1
    // which is 1.844E19 distinct values. Using a integer based decimal
    // we need 20 decimal places to be able to contain enough distinct
    // values. We will use 32 to be safe! Plus 32 is a nice round number ;-)       
   
    public static long generateLong(long min, long max) {
       
        // This decimal represents a random long as an unsigned value
        BigDecimal bigRand = new BigDecimal(new Random().nextLong()).add(new BigDecimal(Long.MIN_VALUE).negate());
       
        // This is the range of long values which is used as a divisor
        // to convert the random long into a value between 0 and 1
        BigDecimal bigDivisor = new BigDecimal(Long.MAX_VALUE).subtract(new BigDecimal(Long.MIN_VALUE));
       
        // Use division to 32 places to create the 0 to 1 value (inclusive)
        BigDecimal bigRatio = bigRand.divide(bigDivisor, 32, BigDecimal.ROUND_DOWN);
       
        // Convert these values to do a bit of math with BigDecimals...
        BigDecimal bigMax = new BigDecimal(max);
        BigDecimal bigMin = new BigDecimal(min);
       
        // Same math used in commons math RandomDataImpl but using BigDecimal
        return bigRatio.multiply(bigMax).add(bigRatio.negate().add(BigDecimal.ONE).multiply(bigMin)).add(bigRatio).longValue();
    }

    // [1] The range of values represented by a long is
    // [masked] to[masked] which
    // is [masked] distinct values.


On Sat, Jan 26, 2013 at 7:06 PM, Stuart Wakefield <[address removed]> wrote:
Not kind, Michael, credit where credit's due! I didn't like the do while loop but it is the only way I can think of doing it, I've tried exploring different methods. Even the commons math RandomDataImpl falls into the same trap as my version, the only difference is they are doing something fairly clever to avoid having to use BigIntegers, they don't use a range at all in their implementation of the method but the method won't pick all values of long because they are basing it around a random double. I believe your method to be the best of all that have been listed so far.


On Sat, Jan 26, 2013 at 6:03 PM, Michael Rogers <[address removed]> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aww shucks. Thanks Stuart, that's very kind. :-)

Cheers,
Michael

On 26/01/13 17:07, Stuart Wakefield wrote:
> 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] <mailto:[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] <mailto:[address removed]>>
> wrote: 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
>
>>
>>
>>
>>
>> -- Please Note: If you hit "REPLY", your message will be sent to
> everyone on this mailing list ([address removed]
> <mailto:[address removed]>)
>> http://www.meetup.com/Londonjavacommunity/ This message was sent
>> by Michael Rogers ([address removed]
> <mailto:[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]
> <mailto:[address removed]>
>>
>
>
>
>
> -- Please Note: If you hit "REPLY", your message will be sent to
> everyone on this mailing list ([address removed]
> <mailto:[address removed]>)
> http://www.meetup.com/Londonjavacommunity/ This message was sent by
> Wesley Hall ([address removed]
> <mailto:[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]
> <mailto:[address removed]>
>
>
>
>
>
>
> -- Please Note: If you hit "*REPLY*", your message will be sent to
> *everyone* on this mailing list ([address removed]
> <mailto:[address removed]>) This message was sent by Stuart
> Wakefield ([address removed]) from LJC - London Java
> Community <http://www.meetup.com/Londonjavacommunity/>. To learn
> more about Stuart Wakefield, visit his/her member profile
> <http://www.meetup.com/Londonjavacommunity/members/74908532/> 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]

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iQEcBAEBAgAGBQJRBBphAAoJEBEET9GfxSfMU5gH/2eAIF5UzUwtUP4mHgOj+JdY
5Fg+cjCPC6JnxPuluMOGvnvFSvn/smjPTtUbPkRxlAMSwwK/v1n9q6Bzwxw7gSr5
XXpVj2Y/Hs/g5zr2O1SGd8mgQ/DhXfbYHEANQcUJa7W2R5Vw/P+LuhJCZ8939Kmx
7aIejpzm3VQD8WDEUCI9p9OgIHFLNcxCIAkPRJDDFuotukAIL7hqwgvvrWwaquNv
/gyLJzVR4cWexHUgx71WNFlsa/PESrTnq67hjLAcGoPYHta1ZDxbql3NoT/RSuks
IxF4S+U09N/qtjpys/VCOPMdWlkHtdm47/teEB827EPtiuudSR+PlKycJyETgNk=
=LLTJ
-----END PGP SIGNATURE-----


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.

  • Craft Rebellion

    Your choice of fresh craft beer, delivered. For 10% off use ‘LJC'

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