But your answer is not the answer to your question. You claim to be an engineer. The correct answer is that PRNG might be functionally equivilent to a "real" random sequence, depending on the application. For example "monte-carlo simulation" or even an on line casino. In some cases the fact that you could predict the sequence is unimportant, and in others you have no way of finding out enough information in a short enough time. And of course in some applications it really is important that the sequence be truly random and hence unpredictable no matter what.
So if you are going to set up strawmen, at least knock them down properly.
As you can see, it's a more efficient algorithm since it starts at positive infinity and decrements. However, after running for a few weeks, it's still initializing i. If it ever finishes, I'm probably really going to regret not adding a print statement.
To me it is. If you don't like it, well what do I care ...
Implying what? Is this sort of remark relevant?
This is the end of this conversation.
--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer: Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix . netcom . com
My abilities are such that, for any set of truly random numbers, of any length whatsoever, I can predict whether or not each value is prime with significantly better than 50% accuracy.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Fine. Don't let the virtual door hit you in the virtual behind on the way out.
The comment was reflecting on your .sig where you claim to be an engineer. Then you ignore one of the attributes of engineering, where the requirements of the problem are considered when formulating the solution and proceed to dis prn in favor of true random when there are many applications in which the difference makes no difference.
Are you sure you are not a Mathematician traveling incognito?
I would think not because the calculation of pi is a deterministic algorithm just like a pseudo random number generator. This looks likely to be just a Finite Improbability.
If you need only a modest number of truely random bits and don't want to buy any hardware, but have network access, there is always John Walker's hotbits for a free and readily available source.
formatting link
--
- Stephen Fuld
e-mail address disguised to prevent spam
Of course it is. However, the claim I responded to was *not* a claim that all PRNGs are crackable, but rather a claim that there exists a method, taught in statistics classes, that can distinguish the output of a PRNG from a true random output.
*That* claim is false. They can all be cracked, but there does not at this time exist a method that can crack them all.
Nor do I say such a silly thing. I only say that you can't tell whether the output is from a PRNG or is really-truly random. See proof below.
That's what I say as well. In particular, you can get good enough that the output cannot be distinguished from a true random output using any known method running on any known hardware.
The proof is as follows:
[1] A true random source can have any output pattern. If any patterns are impossible, it isn't a true random generator.
[2] "Any output pattern" includes the *exact same* patterns as are produced by any and all PRNGs.
[3] Therefore, one cannot look at an output pattern and tell for sure whether it came from PRNG X or a true random number generator that just happened to have that exact same output by random chance.
In addition to the absolute proof above, there are the following difficulties for any realizable system:
[A] All known methods running on all known hardware are limited to examining only a finite amount of the output. If the universe is finite, all possible methods running on all possible hardware will have the same limitation.
[B] A PRNG produces a deterministic pattern. If it has a finite internal state it must repeat, but even seeing it repeat a billion times does not tell the person examining the output that it will repeat the billion and first time. You need to look at an infinite amount of output to know for sure that it doesn't stop repeating at some point above the highest number you looked at.
I am guessing from some of your comments that you may be under the false impression that I have claimed some sort of uncertainty or some departure from determinism in a PRNG, but if you examine my posts you will fail to find any example of me making such a claim.
I *do* claim that there exist PRNGs where the observer is ignorant and cannot become non-ignorant by looking at the output. For example:
01234567890123456789012345678901234567890123456789... (Take it out as far as you wish, including to infinity).
Is it the output of a PRNG? You don't know for sure. Maybe it is a random pattern that just happens by chance to be exactly the same pattern as the output of a simple repeating 0-9 counter. Unlikely, but possible. If that pattern wasn't possible, it wouldn't be a random pattern. All you can do is look at the statistics and assign a probability (in this case very high, in the case of a good PRNG very close to 50/50) that it is the output of a PRNG.
There is a far better method, one that I used when I designed a hardware RNG.
Take any repeating but random event. Thermal noise crossing zero, radioactive decay events, key-presses, cosmic rays - any event that repeats at somewhat random intervals.
Make a high resolution timer with a very stable high frequency clock. Use it to measure the time of each event.
Measure time between two consecutive events. If the time is longer than the last time between the last two consecutive events, output a one. If it is shorter, output a zero. Don't output anything if it is a tie.
Yes, that would work, but is very complex. There are easier approaches to removing bias.
A) Generate bits in pairs, ignore ones that are the same, and convert (0,1) to 0 and (1,0) to 1.
B) Generate bits, in parallel generate alternating 0 and 1, and return the exclusive or of the two.
I should require notice of the question of whether your method is likely to be better at removing flaws other than bias - it may well be - the ones that I describe remove only bias. The second can be extended to any fixed size group of bits, of course, in the obvious way :-)
The set of prime numbers (there is only one) fails the "no amount of knowledge will allow prediction of the next number" test.
The sets of random numbers (there are infinitely many) all pass the "no amount of knowledge will allow prediction of the next number" test.
The set of prime numbers is a member of the sets of random numbers, but you cannot know that a particular set of random numbers is the set of prime numbers without comparing them both to infinity. You can, of course, know that a particular set of random numbers is not the set of prime numbers; finding a single non-prime in the set proves that.
I believe that the set of all sets of random numbers is equal to the set of all sets of numbers.
Nick Maclaren made the follow "There is a universal test that will distinguish all pseudo-random generators from true ones. Actually, there are many, and several have been known (to statisticians) since the 1920s, but there were a couple of 1980 (?) CS papers that described these as new :-) Let's agree on that one."
This cannot possibly be true, because the set of numbers that are outputs of pseudo-random number generators is a subset of the set of numbers that are outputs of true-random number generators.
The exact same set of numbers may be output of a pseudo-random number generator or the output of a true-random number generator - so how can Mr. Maclaren or his fictional statistics instructor possibly distinguish between them?
There is no such paper. Mr. Maclaren is invited to prove that one exists by the simple act of citing one. Further verbal abuse as a substitute for reasoned discourse will be taken as Mr. Maclaren admitting that he is grossly in error.
Until and unless you post a specification of what you mean by a set of random numbers, that is a meaningless statement. It is not true for the values of random variates (with probability one).
No, you were offensive, and I pointed out that is is a standard, known result in statistics. If I recall, it is due to Kolmogorov. Why don't you look it up?
Well, let's try a computer science approach :-)
Enumerate all pseudo-random number generators, with the meaning that they are input-free Turing machines that generate a semi-infinite output stream (of bits).
At each step N, generate the next bit from the first N pseudo-random number generators. Reject any that don't match, and don't use them in the next step (but count them in the N). Return 1 if there are any not rejected, and 0 otherwise.
The test determines that a generator is pseudo-random if it ends in a semi-infinite stream of ones. Otherwise it is not. This will get answer right with probability one.
Until and unless you post a specification of what you mean by a set of random numbers, that is a meaningless statement. It is not true for the values of random variates (with probability one).
No, you were offensive, and I pointed out that is is a standard, known result in statistics. If I recall, it is due to Kolmogorov. Why don't you look it up?
Well, let's try a computer science approach :-)
Enumerate all pseudo-random number generators, with the meaning that they are input-free Turing machines that generate a semi-infinite output stream (of bits).
At each step N, generate the next bit from the first N pseudo-random number generators. Reject any that don't match, and don't use them in the next step (but count them in the N). Return 1 if there are any not rejected, and 0 otherwise.
The test determines that a generator is pseudo-random if it ends in a semi-infinite stream of ones. Otherwise it is not. This will get answer right with probability one.
I am sorry to the people who have seen this three times - I failed to notice that the newsgroups has been subtly edited.
Until and unless you post a specification of what you mean by a set of random numbers, that is a meaningless statement. It is not true for the values of random variates (with probability one).
No, you were offensive, and I pointed out that is is a standard, known result in statistics. If I recall, it is due to Kolmogorov. Why don't you look it up?
Well, let's try a computer science approach :-)
Enumerate all pseudo-random number generators, with the meaning that they are input-free Turing machines that generate a semi-infinite output stream (of bits).
At each step N, generate the next bit from the first N pseudo-random number generators. Reject any that don't match, and don't use them in the next step (but count them in the N). Return 1 if there are any not rejected, and 0 otherwise.
The test determines that a generator is pseudo-random if it ends in a semi-infinite stream of ones. Otherwise it is not. This will get answer right with probability one.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.