A Data Science Central Community
This article discusses a random number generator with an infinite period.
One of the best random sets of digits (extensively tested for randomness by hundreds of scientists using thousands of tests both in small and high dimensions) is the decimals of Pi. Despite its random character being superior to most algorithms currently implemented (current algorithms typically use recursive congruence relations or compositions of random permutations, and exhibit periodicity), decimals of Pi have two big challenges, making it useless as a random number generator:
Here is my answer to these two challenges, and as a result, a proposal for a new random number generator, which overcome these two difficulties:
Fast formulas to compute Pi:
[1] The formula,
is remarkable because it allows extracting any individual hexadecimal or binary digit of π without calculating all the preceding ones.
[2] The Chudnovsky brothers found in 1987 that
which delivers 14 digits per term.
PS: this is a reply to the following article: Classical random number generators result in identity theft, according to IEEE, see http://www.analyticbridge.com/profiles/blogs/classical-random-numbe...
Comment
I have one minor issue with some wording about random number generation. First, they are actually pseudo-random. Second, since infinity is not numerical, random number generators cannot achieve infinity. The can theoretically achieve the largest countable number, aleph-1, if we had the computational capacity to do so. I would just caution using infinity and random number generation in the same context. Though every number contains the concept of infinity, even 1.00000000..., infinity is not a number, we cannot count to it, and thus it is not possible to achieve the period computationally. Infinity is that which lies beyond the countable and uncountable.
I forgot that for those who really want randomness, they can put quantum physics in their PC! http://www.idquantique.com/true-random-number-generator/quantis-usb...
A bit expensive, but...
The first question for a random number generator is what is the purpose? If one is looking for statistical performance, for instance for simulation, very efficient generators (MRG or Mersenne-Twister) are known, and should be used. There are many statistical tests that can be used to evaluate them. TestU01 is a free software that implements dozens of them, and can identify bad generators (e.g. those proposed in Excel, VB, GNU Glibc,...). The IEEE article clearly do not address this (simulation) concern. If one is just looking for use in cryptography, the statistical properties are much less relevant, and the technique complexity is then more important. The important issue is not only to hide the seed, but also make the technique difficult to discover by an intruder. Modern generator have huge periods (the MT19935 has a period of 2^19937) so it is already virtually impossible to predict the number if one just had a small sequence. Combine different kind of generators, and the modern ones are fast (faster then the computer of pi decimals), and you have a very strong tool.
Another idea: use continued fractions to approximate Pi. Let us denote by p(n) he n-th approximant: p(n) = A(n) / B(n), where A(n) and B(n) are integers defined by simple recurrence relations. Modify these recurrence relations very slightly, et voila: we created a new interesting number, with (hopefully) random digits.
Or consider a simple continued fraction such as
F = 1 / (1 + 1 / ( 1 + 2 / ( 1 + 3 / ( 1 + 4 / ( 1 + 5 / ( 1 + 6 / 1 + .. ) ) ) ) ) )
Despite the very strong pattern in the construction of F, I am sure that its digits show very good randomness properties.
It would be interesting to study the function F(a,b,c,d) defined by formula [1], by replacing the numbers 4, -2, -1, -1 (numerator) by a, b, c, d. Of course, F(4,-2,-1,-1) = Pi.
Do interesting numbers share the two properties listed below? Could the number e=2.71..(or some other beautiful numbers) be a special case of F?
You need to be a member of AnalyticBridge to add comments!
Join AnalyticBridge