the lost logbook

Utkarsh's mind.random() on Programming, India and Startups

next() in Java from The art of computer programming

leave a comment

xkcd: Random NumberI have always used Random’s nextInt() or nextLong(). So was curious on how “random” is it actually? Then I found this protected method next().

protected int next(int bits)

 

Implementation of Random.java via Google code:

1
2
3
4
5
6
7
8
9
    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

The general contract of next is that it returns an int value and if the argument bits is between 1 and 32 (inclusive), then that many low-order bits of the returned value will be (approximately) independently chosen bit values, each of which is (approximately) equally likely to be 0 or 1. The method next is implemented by class Random by atomically updating the seed to

(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

and returning

(int)(seed >>> (48 - bits))

This is a linear congruential pseudorandom number generator, as defined by D. H. Lehmer and described by Donald E. Knuth in The Art of Computer Programming, Volume 3: Seminumerical Algorithms, section 3.2.1.

Interesting!

EDIT: Something even more interesting: Why this code is giving strange result? So Random?

Link to JavaDocs for Random.

Written by Utkarsh

August 1st, 2011 at 11:47 pm

Posted in Technology

Leave a Reply

*

Page optimized by WP Minify WordPress Plugin