These days, why would anyone bother with software generated random numbers? Use hardware generation, amplified noise or quantum detection. Bypass the requirement of algorithm verification. Bypass the problem of a limited number of seeds. -- Gene
________________________________ From: Warren D Smith <warren.wds@gmail.com> To: math-fun <math-fun@mailman.xmission.com>; richard.brent <Richard.Brent@anu.edu.au> Sent: Monday, September 30, 2013 1:19 PM Subject: Re: [math-fun] linear psu-random generators with linear "feed-in"
actually I think the best psu-random generator would be "hierarchical." That is, you use a very fast+simple generator for a while, then reseed it using a slower but more random generator, that in turn would be re-seeded at longer intervals with a slower but still more random generator etc.
You aim to get nearly the speed of the fastest but nearly the randomness of the slowest generator. The "feedin" technique is a way to do such reseeding in a "continual slow drip" rather than all at once. Seems to me the hierarchical idea can be backed up with a
THEOREM (or pretty close): If "randomness" is measured by expected computational complexity of a statistical test that finds a problem with it, and if achievable randomness grows with generator runtime exponentially, then it is possible to achieve arbitrarily enormous randomness with only a constant factor slower average runtime than the simplest generator.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun