path: root/src/prng
AgeCommit message (Collapse)AuthorLines
2013-12-12include cleanups: remove unused headers and add feature test macrosSzabolcs Nagy-1/+0
2013-06-12improve the quality of output from rand_rRich Felker-1/+10
due to the interface requirement of having the full state contained in a single object of type unsigned int, it is difficult to provide a reasonable-quality implementation; most good PRNGs are immediately ruled out because they need larger state. the old rand_r gave very poor output (very short period) in its lower bits; normally, it's desirable to throw away the low bits (as in rand()) when using a LCG, but this is not possible since the state is only 32 bits and we need 31 bits of output. glibc's rand_r uses the same LCG as musl's, but runs it for 3 iterations and only takes 10-11 bits from each iteration to construct the output value. this partially fixes the period issue, but introduces bias: not all outputs have the same frequency, and many do not appear at all. with such a low period, the bias is likely to be observable. I tried many approaches to "fix" rand_r, and the simplest I found which made it pass the "dieharder" tests was applying this transformation to the output. the "temper" function is taken from mersenne twister, where it seems to have been chosen for some rigorous properties; here, the only formal property I'm using is that it's one-to-one and thus avoids introducing bias. should further deficiencies in rand_r be reported, the obvious "best" solution is applying a 32-bit cryptographic block cipher in CTR mode. I identified several possible ciphers that could be used directly or adapted, but as they would be a lot slower and larger, I do not see a justification for using them unless the current rand_r proves deficient for some real-world use.
2013-06-08prng: make rand_r have 2^32 period instead of 2^31Szabolcs Nagy-2/+2
this is a minor fix to increase the period of the obsolete rand_r a bit. an include header in __rand48_step.c is fixed as well.
2013-06-08prng: fix rand() to give good sequence with small stateSzabolcs Nagy-2/+4
some applications rely on the low bits of rand() to be reasonably good quality prng, so now it fixed by using the top bits of a 64 bit LCG, this is simple, has small state and passes statistical tests. D.E. Knuth attributes the multiplier to C.E. Haynes in TAOCP Vol2 3.3.4
2012-04-24ditch the priority inheritance locks; use malloc's version of lockRich Felker-9/+9
i did some testing trying to switch malloc to use the new internal lock with priority inheritance, and my malloc contention test got 20-100 times slower. if priority inheritance futexes are this slow, it's simply too high a price to pay for avoiding priority inversion. maybe we can consider them somewhere down the road once the kernel folks get their act together on this (and perferably don't link it to glibc's inefficient lock API)... as such, i've switch __lock to use malloc's implementation of lightweight locks, and updated all the users of the code to use an array with a waiter count for their locks. this should give optimal performance in the vast majority of cases, and it's simple. malloc is still using its own internal copy of the lock code because it seems to yield measurably better performance with -O3 when it's inlined (20% or more difference in the contention stress test).
2011-06-29locking support for random() prngRich Felker-7/+28
these interfaces are required to be thread-safe even though they are not state-free. the random number sequence is shared across all threads.
2011-06-23initial commit of prng implementation by Szabolcs NagyRich Felker-12/+107
2011-02-12initial check-in, version 0.5.0v0.5.0Rich Felker-0/+126