Irrational numbers such as π may have been the first ones used to create perfect randomness and strong cryptographic systems. They were also among the first ones to be dismissed, long ago. Since then, they were never revisited and are completely abandoned.
Binary digits of numbers such as π are remarkable at mimicking randomness. Indeed a lot more than modern congruential random generator. They lead to pseudo-random number generators (PRNGs) with infinite period, and with no known pattern. To the contrary, new powerful congruential PRNGs pop up regularly, only to be broken a few years later. All of them are periodic, but that is not an issue since the period is incredibly long. The problem is low-dimensional patterns. In the case of the Mersenne twister, that dimension is 623. Yet this PRNG invented in 1997 is widely used, including in many programming languages such as Python. It also fails my prime test of randomness, depending on the seed: see my article “Detecting Subtle Departures from Randomness”, here.
Historical Reasons to Abandon Irrational Numbers
Using congruential PRNGs amounts to using rational numbers with very large periods. The number of rational numbers is denoted as א. This symbol (aleph) represents a cardinality, and it is infinite. However, there are 2א irrational numbers to choose from. This is a much bigger infinite. I spare the details here, but this is a well-known result established by Georg Cantor long ago. In short, pretty much all numbers are irrational.
However, detractors claim that typical irrational PRNGs use only a few of these numbers, always the same, like π or 5π + 3π2. If this was true, of course such PRNGs would be extremely easy to break, making them highly vulnerable. It also ignores the fact that you can start at any position in the decimal expansion, not just the first position. This amounts to introducing a seed.
Another common supposed weakness of digits of irrational numbers is that they are deterministic: easy to predict, not random at all. But the same is true for congruential PRNGs. These are even more deterministic, since the formulas involved lead to faster implementations than irrational PRNGs. Perhaps the strongest argument against using irrational numbers is the fact that extracting the digits is very time consuming. In the next section, I debunk this idea, by introducing a new breed of irrational PRNGs.
Technological Breakthrough: Quadratic PRNGs
Here I summarize the results of my research on designing fast and strong irrational PRNGs. It is true that computing 3 billion bits (binary digits) requires 9 times as many computations as for 1 billion. The computational complexity is O(n2), where n is the number of bits produced from a same irrational number. Congruential PRNGs are O(n) instead.
The breakthrough consists of using billions of different irrational numbers at once — blended together — each with as many digits as you want. Typically you use few digits of each irrational number (less than 10,000), but billions of different numbers in order to get a very fast implementation. The ingredients that make this method powerful are as follows:
- A very simple formula to compute the binary digits of infinitely many quadratic irrationals, involving basic integer additions only.
- A fast procedure to get a digit in arbitrary position, without having to compute the previous digits. Again, only involving simple integer operations including multiplication by a power of two (that is, the shift operator also found in all congruential PRNGs).
- The fact that two different quadratic irrationals in the list of authorized numbers have independent digit sequences. The lack of cross-correlations was recently mathematically proved.
The Python implementation, including all the little details to do it the right way, are described in my technical article, available here.
About the Author
Vincent Granville is a pioneering data scientist and machine learning expert, founder of MLTechniques.com and co-founder of Data Science Central (acquired by TechTarget in 2020), former VC-funded executive, author and patent owner. Vincent’s past corporate experience includes Visa, Wells Fargo, eBay, NBC, Microsoft, CNET, InfoSpace. Vincent is also a former post-doc at Cambridge University, and the National Institute of Statistical Sciences (NISS).
Vincent published in Journal of Number Theory, Journal of the Royal Statistical Society (Series B), and IEEE Transactions on Pattern Analysis and Machine Intelligence. He is also the author of “Intuitive Machine Learning and Explainable AI”, available here. He lives in Washington state, and enjoys doing research on stochastic processes, dynamical systems, experimental math and probabilistic number theory.
