java - Why are pseudorandom bits not cached when only one bit is used per "draw" (e.g. a call to nextBoolean)? -


i going through source code math.random , have noticed source code nextboolean()

public boolean nextboolean() {    return next(1) != 0; } 

calls new draw of pseudorandom bits, via next(int bits) "iterates" lc-prng next state, i.e. "draws" whole set of new bits, though 1 bit used in nextboolean. means rest of bits (47 exact) pretty wasted in particular iteration.

i have looked @ prng appears same thing, though underlying generator different. since multiple bits same iteration used other method calls (such nextint(), nextlong(), ...) , consecutive bits assumed "independent enough" 1 another.

so question is: why 1 bit used draw of prng using nextboolean()? should possible cache, 16-bits (if 1 wants use highest quality bits), successive calls nextboolean(), mistaken here?

edit: mean caching results this:

private long booleanbits = 0l; private int c = long.size; public boolean nextboolean(){     if(c == 0){         booleanbits = nextlong();         c = long.size;     }      boolean b = (booleanbits & 1) != 0;     booleanbits >>>= 1;     return b;      //return ( next() & 1 ) != 0; } 

sure, it's not sure , pretty commented out text, ends in 64x less draws. @ cost of 1 int comparison, , 1 right-shift operation per call nextboolean(). mistaken?

edit2: ok, had test timings, see code here. output follows:

uncached time lapse: 13891 cached time lapse: 8672  testing if order matters..: cached time lapse: 6751 uncached time lapse: 8737 

which suggest caching bits not computational burden improvement instead. couple of things should note test:

  1. i use custom implementation of xorshift* generators heavily inspired sebastiano vigna's work on xorshift* generators.

  2. xorshift* generators faster java's native generator. if use java.util.random draw bits, caching make larger impact. or that's expect @ least.

  3. single-thread application assumed here, no sych issues. that's of course common in both conditions.

conditionals of kind can quite expensive (see why faster process sorted array unsorted array?), , next doesn't many more operations: count 5 arithmetic operations plus compareandset, shouldn't cost in single-threaded context.

the compareandset points out issue -- thread-safety -- harder when have 2 variables need kept in sync, such booleanbits , c. synchronization overhead of keeping in sync multithreaded use exceed cost of next() call.


Comments

Popular posts from this blog

php - regexp cyrillic filename not matches -

c# - OpenXML hanging while writing elements -

sql - Select Query has unexpected multiple records (MS Access) -