> After a while of confused debugging, we eventually discovered that the RNG was a linear congruential generator, which, when used the way we did to generate N-tuples, tends to produce points that tend to lie on a small number of N-1 dimensional surfaces! Oops.
Yep, this is the "Random Numbers Fall Mainly in the Planes" problem that the late George Marsaglia of xorshift fame wrote about in 1968: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/
Great paper with one of the best titles I can remember :)
Re:A Simple Hash for Perlin Noise
by knighthack on Tuesday May 10, 2022 @09:36PM
(#31334873)
Kudos to the skeptic at least for being willing to accept, and declare, that he was wrong in the first place.
There are many skeptics who would rather disregard other assertions, than to admit their own possible flawed testing/experimental/verification methodologies.
Re:A Simple Hash for Perlin Noise
by Dave_Rosenthal on Tuesday May 10, 2022 @10:00PM
(#31335023)
Indeed. It was many years ago but I clearly remember he used a lot of volume and language on the initial call. It was followed a few days later up by an equally-memorably note that started with 'HERE IS WHERE I EAT CROW' in all caps. The sales guys were sure we had lost the account :)
Re:A Simple Hash for Perlin Noise
by nescioquid on Tuesday May 10, 2022 @10:24PM
(#31335167)
I really appreciate that you called this part out.
When you need to admit you are wrong, your vis-a-vis will trust you more as a result. When the shoe is on the other foot, you learn who you can trust.
Re:A Simple Hash for Perlin Noise
by adgjlsfhk1 on Tuesday May 10, 2022 @07:18PM
(#31333908)
Thankfully the awful linear congruential generators of past have mostly been killed by now. Mersenne twister isn't ideal (kind of slow and uses a bunch of memory), but it is pretty solid. The xoshiro family also is pretty widely used in now for programming languages, and that's a major an improvement over lcg on all fronts (except roughly tied for speed).
Re:A Simple Hash for Perlin Noise
by galangalalgol on Tuesday May 10, 2022 @07:32PM
(#31334002)
Have they gotten one that implements well in a gpu yet? Last I read many people doing stochastic filters (resampling etc.) Were generating noise cpu side and shipping it over to the device. But that has been a while.
1) I remember building a game in 90s where the locations of resources on a 2d game map were generated by successive calls to random() (and then were probably mod 1024ed or something). But, when we looked at the locations, they were clearly in a line pattern. Huh? After a while of confused debugging, we eventually discovered that the RNG was a linear congruential generator, which, when used the way we did to generate N-tuples, tends to produce points that tend to lie on a small number of N-1 dimensional surfaces! Oops.
2) I remember a big debate with a statistician at a company we were selling data analytics software to. We were putting random data elements into random groups to support certain types of statistical analysis. He was adamant that the randomization we were doing would introduce bias into the data and showed us similar tests he had done that "proved it". He told us that his company would be dropping our product because they couldn't trust it. I told him that there was no way bias was introduced and I took a closer look at his tests. It turns out the RNG in whatever tool he was using was just not very good and it had apparently shaken his very understanding of statistics :) Luckily, I told him that we were using MD5 for randomness (once bitten!) and that if he simply redid his experiments with MD5 he would see the bias disappear. To say he was skeptical would be an understatement, but, thankfully for our contract, his tests didn't actually crack MD5, all bias was gone, and we got a very generous email from the skeptic informing us that he would be trusting our software for everything from now on.