Source Code and Discussion of Newer & Better Portable Random Number Generators | REFERENCES | |||
index |
||||
Back to Deley's Homepage |
A couple of more recent PRNGs, such as, say, the Mersenne Twister or R250. Their power distribution characteristics and behavior in the low-order bits is vastly better than any linear-congruential generator, or Riemann-Zeta-based generator. The Twister also has the virtue of being quite fast. I've written 3D weather simulations where no linear-congruential generator, even coupled with all the tricks for suppressing short-term periodicity in certain bit patterns, was sufficiently well-behaved to prevent very obvious visual artifacting. At the time, I switched to R250 (which is, admittedly, slow, but which still handled the fairly dense particle system I was using), and the artifacts vanished. One other possible problem you could mention is that when you scale floating-point numbers to fit a range, you can mess up the power distribution for certain values due to how the processor normalizes such numbers, the amount of precision available, and the fact that the numbers expressible as floats are not only not topologically dense within the reals for your range, but aren't even linearly distributed. I suppose a final bit of completeness would point out that it's possible to apply a perfectly uniform generator to a problem space in a way that introduces non-linearities. The classic example of that I've seen (quite frequently in game programming, actually) is to try to get a uniform distribution of points in a spherical volume by applying a uniform generator to a bounding cube, then tossing out-of-range values. Computationally much cheaper, but if, for instance, you're computing fog values, or particle placement, you end up with "thin" lines of sight from the center through the vertices of the bounding box. This can be quite visually obvious. The place where non-uniformity can really be important is in generating key schedules for encryption algorithms; the rand() problem you mention was how the 40-bit RSA in Netscape was originally broken, as it reduced the size of the keyspace by several binary orders of magnitude. Some sites you might look at on PRNGs:
I'm sure there are newer sites, as these are ones I archived when I wrote my PRNG modules I use for most everything. Knuth has lots of material on PRNGs, but it's mostly linear congruential stuff, which he analyzes to death. Bruce Schneier has some material on his site, which I list below, because PRNGs are of critical importance to encryption algorithms (read his Yarrow-160 whitepaper; the implementation has problems, but the theory is fascinating). And Vegas gambling machines; I once almost took a position writing code for slot machines. They had to have someone who really understood how the things worked, and all the myriad ways implementation errors could mess up their distribution properties (hey, that's exactly how the 40-bit RSA encryption in Netscape was broken around 1996). You really don't want to run foul of the Las Vegas Gaming Commission. AES Some other sites somewhat related to this material (mostly numeric kinds of stuff):
—Reid Sweatman |
Source Code and Discussion of Newer & Better Portable Random Number Generators | REFERENCES | |||
index |
||||
Back to Deley's Homepage |