Race Conditions == Random Number Generation
github.com
github.com
strace -Tiv -ttt nice -n 19 curl -Lv --raw https://google.com/news 2>&1 | shasum -a 512 | dd bs=1 count=2 2>/dev/null
This assumes Google News serves frequently changing content. The noncanonical Google News URL generates extra entropy from an HTTP 302 Moved Temporarily to an HTTP 301 Moved Permanently to an HTTP 200 OK with the final news page. strace and nice and curl add entropy from OS syscall timings and HTTP headers.
(OS X doesn't have strace, so you can just skip it.)
This reminds me of sleep sort. For those unfamiliar, sleepsort is where you have an unsorted array, then have 1 thread per element sleep for the amount of time specified by that element, then append it to a list.
Though sleep sort is obnoxious (& hilarious), I'm sure it could be of use in educational situations. It's both elegant and intuitive. Thought provoking, maybe?
It's kind of like claiming you have an O(n) sorting algorithm because you can run an O(n) selection algorithm to find the kth smallest element for each of 0..n-1 and then run n of them in parallel on n cores to get an O(n) sorting algorithm. If you actually have n cores then the wall clock time for executing that algorithm will be O(n), but the number of operations won't be and it all falls apart when you run out of hardware parallelism.
It reminds of me of bucket sort. There is an intellectually curious implementation to sort a list of unique fixed-width (e.g. 32-bit) integers that goes like this: You allocate an m bit (e.g. 2^32 bit / 512MByte) array and zero it (O(m)), then you inspect every element and set that bit of the array (O(n)), then you traverse the array and add an element to the end of the sorted list for every set bit (O(m)). So the overall algorithm is actually O(1) in the number of elements, because you're doing m+n+m work where m > n, which means you're doing at most m+m+m. The problem is that in practice for most real lists the constant factor is so much larger than n that using an O(n log n) sorting algorithm will be significantly faster. And it's clearly Do Not Use if you're sorting e.g. 128-bit ints. But for n sufficiently close to m it can actually be useful. It would probably be tough to beat for sorting a 3 billion element array of 32-bit ints. Or a 200 element array of 8-bit ints.
Not necessarily (though yes, in any efficient real life it would). It could wait for a tick of the clock and on each scan an unordered list of things to see if any are due to happen.
Of course if the list gets big enough that the list takes a long time to scan then it will break sleep sort because if enough time passes for two or more events to have happened between two checks, those events will happen in an undefined order.
It is a good example of how algorithm design can be done naively and algorithm analysis can be done badly, so definitely has at least some educational value.
Excluding implementation specific edge cases that would break the underlying assumptions regarding thread wakeup times, it is a O(N) time complexity sort in all (best, worst, average) cases. A miracle! Get thee to the patent office! Eat my shorts Shell!
Of course the constant time multiplier involved is so massive that it would not do better than an n(log n) or even an n*n sort in any practical situation, and this is before considering space requirements and thread processing overhead.
The OS needs to pick which thread to run from a pool of N threads - absolute best case an O(log N) operation, either when the thread is queued or when it's being selected. This happens N times, so the runtime seems like it would actually scale as O(N log N).
On the other hand, if you've got a scheduler that can pick the thread with the smallest sleep time from a list in O(1) time, you could just use whatever algorithm that's using to make an O(N) insertion sort...
So while that overhead could increase processing time, wall-clock time need to be affected.
Again this is why I think it makes a good example for illustrating critical thinking in the area of algorithm design and analysis. It is an obviously silly example which could actually work, within certain practical boundaries, and the many obvious problems with it are hidden in more complex processes/structures.
Thread scheduling may be difficult to predict precisely. This is a radically different property than being random.
A good source of randomness is becomes no more predictable given previous outputs. Being able to predict the next output precisely would obviously break a random number generator. But being able to weight the odds of the next output also break a random number generator; it's less obvious, but most certainly enough to beat the house in any gamble.
Which thread wins race conditions is certainly not random. CPU cache lines will create biases, the implementation of your processor's pipelining of memory fences is likely predictable, and on and on.
Use a CSPRNG.
A counterargument might begin with "But I don't need cryptographically valid randomness!", to which I would respond "then why are you thinking about this at all?" Cryptographically valid randomness is not hard from either a programmer braintime perspective (there are libraries, unless you take up deep issues with modern CSPRNGs) or a CPU-time perspective (CSPRNGs can spit bytes faster than your disk can accept them). If you don't need cryptographic randomness, then there are other even faster sources of psudeorandomness; use those, not this mechanism for creating CPU waste heat.
And indeed even as an educational opportunity to explore how very much not-random CPU scheduling over unguarded memory is, this is also probably a gem.
But I should hate to see anyone mistake this concept for useful.
Sorry to have been misleading.
You're correct. It's a horribly bad idea, and the thought I put into it was pretty minimal. Just a fun hack, really.
I'll put a note in the readme.
The cache coherency rules are different in ARM and Intel CPUs, you should see quite different result from unsynchronized access to same memory locations. On ARM, you need to be more careful with explicit memory barriers, especially when you attempt to write lock-free code, or you're in kernel space.
I expect that on ARM, you're going to see a lot less random because an entire cache line written to by one core will replace another cache line written to by another core, thereby showing only the randomness contribution of one core.
If you have a sufficiently well-developed model of thread-scheduling patterns, then the randomness reduces in quality to that of the system's PRNG. But thread-scheduling is a serious pain, so this seems promising.
I doubt it's more efficient than something like Mersenne Twister. Generating entropy this way is pretty damn expensive in terms of processor cycles.
It's difficult to have meaningful discussion (w/ regard to randomness) when involving more philosophical principles. For those who believe wholeheartedly in a deterministic universe, the concept is utter nonsense.
That's why it's important that pragmatic folk focus on practical and statistical randomness, rather than universal randomness.
By practical, I mean that the information required to predict generated numbers is simply not available. It may exist; it may not; but regardless, it's inaccessible to those in need of it.
In this case, I'm not certain if sufficient thread-scheduling information is available to derive accurate predictions, or if separate processes could be of effect without altering the speed at which RNG state mutation occurs simultaneously. Being interdependent on other thread & process CPU usage, my approach might be another case of "the act of observation changing the thing observed".
But then again, I'm know little of both cryptography and CPU scheduling. This comment, like this project, is largely speculative.
// For each byte in the buffer, use its value to index into another
// byte and XOR the two.
I'm not a cryptographer, but this smells extremely insecure to me. If the random seed is all zeroes this generator will generate all zeroes for perpetuity, no?
Even if you get a decent initial seed, I still strongly suspect this RNG strategy will be very statistically leaky, will tend to equilibria, and will generally be easily breakable in practice. An RGB visualization in the context of RNG means next to nothing.
Please children, don't do your own crypto.
Maybe I'll include a variable sleeping time determined by current buffer values. That way, thread synchronization would be further disorganized, and CPU power wouldn't be wasted quite as much.
In that case, it's important that mutations take place between every byte outputted tough.
(not confident in the credibility of this article) http://boallen.com/assets/images/randbitmap_computer.png
On Linux rand() doesn't suffer from the problem.
Random doesn't always look random. To make matters worse, we're biased towards seeing patterns in noise: http://en.wikipedia.org/wiki/Clustering_illusion
A bookmarklet (paste in address bar) to show truly random and "evened out" dot distributions side by side. (Don't laugh at my Javascript):
javascript:"<html><body><canvas id=\"tutorial\" width=\"200\" height=\"200\">foo</canvas><-><canvas id=\"tutorial2\" width=\"200\" height=\"200\">foo</canvas><script>var canvas = document.getElementById('tutorial');var ctx = canvas.getContext('2d');ctx.fillStyle = \"rgb(000,0,0)\";for (var i=0;i<400;i++) {ctx.fillRect (Math.random() * 200,Math.random() * 200, 2, 2); };</script><script>var canvas = document.getElementById('tutorial2');var ctx = canvas.getContext('2d');ctx.fillStyle = \"rgb(000,0,0)\";for (var i=0;i<20;i++) for(var j=0;j<20;j++) for(k=0;k<1;k++) {ctx.fillRect (i * 10 + Math.random() * 10, j * 10 + Math.random() * 10, 2, 2); };</script></body></html>"
I wouldn't evaluate a generator solely on the basis of a bytemap. But these visualizations are of value.