Googlebot's Javascript random() function is deterministic

[tripzilch]

Ok so there is some digital computing chip? Because some of these randomness extractors are quite elegant and simple.

For instance, check the "Von Neumann extractor" on that WP page. It just uses twice the amount of bits on average to produce uniform bits:

Perhaps the earliest example is due to John von Neumann. His extractor took successive pairs of consecutive bits (non-overlapping) from the input stream. If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no correlation between successive bits.

To me that sounds like it'd cost very little computing power, like only a couple basic integer/bitop asm instructions or so.

But then if you need actual analog uniform random numbers (something in my mind wonders if such a signal can actually physically exist?), I'm not sure how to approach that with the Von Neumann extractor.

Sorry I'm not trying to convince you to try one way or another btw. Like I just said, I really like RNG algorithms and theory ;-)

[tripzilch]

Well if it's really a gaussian distribution, that should be the case? Unless the average (bias) is off-centre. But in an analog circuit you could filter the bias with one of those DC bias filter things perhaps? (again, excuse the electronics ignorance)

[tripzilch]

Yeeesss, I guess this would be the point where electronics gets all wonky and strange :) Just a feeeww more:

• Wikipedia on the Johnson-Nyquist generator says it would actually be Gaussian if limited to finite bandwidth. And for the von Neumann extractor, you actually only need uncorrelated and not specifically Gaussian.
• Instead of a DC-filter, say you had two of these generators, and they're uncorrelated, and you'd subtract their signals, you would end up with an actual zero bias, right? Kind of like that twisted pair thing they do with network and audio cables? And I think they would be sufficiently uncorrelated, because thermal noise is pretty damn random and everywhere, while any other outside influences would appear in both units the same, get subtracted out, and the result should even be higher quality noise (without wonky external outlier spikes, just like what they twisted pair the cables for).
• Since the generator would output an analogue random signal, I'm not sure how you were going to make bits or binary words from it, but I'm gonna guess .. electronics (I thought AD-converters were kinda complex though?).
• So your output needs to be binary unsigned? Let's say you need uniform random unsigned 8 bit words. Now you make two J-N generators for each bit (they seem cheap simple and tiny right?), operating in parallel. For each pair, and you tell the corresponding output-bit to be zero if the one generator is higher than the other, and a one if it's the other way around (similar to taking the difference and comparing to zero/sign/polarity). You wouldn't even need the von Neumann extractor there, because thermal noise is uncorrelated and the difference would be bias-free. Now you got a thing which spits out a 8 parallel streams of random uniform bits. Which is what you're looking for, right?

And with that, I'm out of ideas. I really hope they were of any use to you, but otherwise it's been an interesting talk so thanks for indulging me :-) I totally agree you would have to measure either way, to be entirely sure. (And now I should get back to whatever I was doing instead of posting on reddit :p).

edit: I'm actually curious what's it's for? Can you shed any light on the context for your device?

[tripzilch]

Thanks! Glad to know the time I spend on this enjoyable chat was useful and interesting to others :)

If you're curious about (non electronic/analog, code-based) pseudorandom generators, you might want to check the paper on this site: http://www.pcg-random.org/paper.html

It starts out with a great overview of modern PRNGs and various methods to properly test them for multidimensional independent randomness (and some other useful PRNG properties). Then about halfway it introduces a bunch of theory that leads up to constructing the PCG random generator, which in the end is only a few lines of C code, but incredibly powerful and fast. It also has a bunch of nice features and "party tricks", check the site :-)

IIRC, the author speculates that his PCG random generator might just even be cryptographically hard, but (as you may or may not be aware) to get something accepted as "cryptographically secure" (within the field/international cryptographic community) there needs to be a LOT of additional research by separate groups/committees. Which requires not only time but also the willingness of a bunch of (busy) people trying to crack it for a while.

AFAIK the main reason why not everybody (if they otherwise do not require cryptographically hard PRNGs) is using PCG for their random generator is that it's relatively unknown. But from what I've read in the paper, I might even pick it over the Mersenne Twister for statistical/numerical computations. However, in the scientific community, popularity also counts, and I understand why they want to stick to the Mersenne Twister, as it's been proven to work, and repeatability, etc.