Re:The Complexity Paradox (1998)
by dexen on Wednesday October 14, 2020 @10:34AM
(#24776957)
As somebody who gave two honest attempt at building a PRNG... no, not quite. Building complexity -- especially one that isn't trivally reducible -- is quite hard.
[ Parent
| on HN ]
Re:The Complexity Paradox (1998)
by waynesonfire on Wednesday October 14, 2020 @11:45AM
(#24777933)
What does trivially reducible mean?
A PRNG is inherently complex and winners of https://www.ioccc.org/ are a class of complexity you deem reducible. This competition involves building complexity and since there are winners it's feasible to claim that to win it is "hard". Since this straddles a form of art, placing a value judgement as easy vs hard seems invalid.
The reason I'm thinking about this is because I recognize that adding accidental complexity is far easier than removing it. In fact, I spend a significant amount of time "trivially reducing" such complexity.
My both attempts at PRNGs resulted in rather short cycles -- ones that were easily compressed several-times-fold by GZIP and similar algorithms. Thus I consider them to have been trivially reducible.
Yes, a well designed PRNG algorithm and implementation can be quite simple, but it is quite hard to design them well. It takes either non-trivial math, or non-trivial amount of iterative improvements.