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

Post a Comment

Popular posts from this blog

html - Sizing a high-res image (~8MB) to display entirely in a small div (circular, diameter 100px) -

first of all, thank being patient know simple question more couple of weeks' experience figure out. i've seen folks persevere , helpful on here , hope you're willing me. here fiddle: http://jsfiddle.net/65uzf/ here 1 of places searched answers on here: ( vertically center image thumbnails fix-sized div ) tried solutions on there , didn't work out me. i've searched ~4 or 5 others, , been unsuccessful those, too. what want take large image (what linked background-image #ysypic , #tabpic divs) , display thumbnail version of image in confines of divs have set it. is, using background properties have laid out in css, portion of image displays inside of circular divs. without these properties, display defaults smaller section of image [presumably pi*(50^2) area in top left] terrible resolution. i not care if entire image doesn't display inside of circles (it won't, given difference in shape), , overflow not being displayed fine. want able see figu
Read more

java - IntelliJ - No such instance method -

using intellij's 12 ultimate, i'm running following code in debugger: java import play.api.libs.json.jsvalue; public class foo { ... public jsvalue tojson() { ... } public class fooexample { ... foo foo = new foo(); system.out.println("...); //<-- breakpoint at breakpoint, right-clicked source code , picked "evaluate expression," typing in: foo.tojson() . but following error showed up: no such instance method: play.api.libs.json.jsvalue$class.com.foo.foo.tojson () am doing wrong? foo#tojson calls scala code, if matters. edit had breakpoint after instantiation of foo. downvoted it, deserved it. edit my answer no longer valid after op modified question (i.e. moved breakpoint actual is).. a breakpoint hit before line executed. in case foo has not yet been declared or instantiated (i.e. foo constructor has not yet been called). you'll need put breakpoint @ next line (or step on current line) if want evaluate foo .
Read more

identifier - Is it possible for an html5 document to have two ids? -

i wondering if html5 element can have 2 ids, this: <button id="thing1" id="thing2" name="button1" onclick="change()">click here</button> or this: <button id="thing1, thing2" name="button1" onclick="change()">click here</button> also, if 1 of ids said 1 thing, , other id said thing, 1 used? tl;dr : no. in versions of html, each element can have 1 id. see the spec : the id attribute specifies element's unique identifier (id). [dom] the value must unique amongst ids in element's home subtree , must contain @ least 1 character. the value must not contain space characters. note: there no other restrictions on form id can take; in particular, ids can consist of digits, start digit, start underscore, consist of punctuation , etc. note: element's unique identifier can used variety of purposes, notably way link specific parts of document usin
Read more