The title sums it up. I'm interested to know if there exists an algorithm capable of producing variable output given identical input without relying on other sources for randomness such as DateTime.Now or a number generated from a light sensor etc. In addition, the algorithm can not be run in sequence, just two distinct, unrelated runs that produce different output.
asked Jul 15, 2013 at 4:53
4 Answers
I'm interested to know if there exists an algorithm capable of producing variable output given identical input without relying on other sources for randomness such as DateTime.Now or a number generated from a light sensor etc.
No, that's fundamentally impossible, because the very definition of an algorithm is that it's well-defined and deterministic, i.e. given the same input will always produce the same output. There are randomized algorithms, but they require randomness as input.
Furthermore, determinism is the most important design goal of computer hardware. A CPU that does not produce the same output given the same input would be utterly useless for most purposes.
answered Jul 15, 2013 at 9:33
No, a pseudo-random number generation algorithm will always produce the same output given the same seed (hence pseudo-random).
I find it interesting that you used the term, "algorithm" rather than "program." This excludes a certain class of yes answers (soft errors in RAM, different thread interleavings in a multi-threaded RNG, etc.). If you take it as granted that every run of your algorithm takes the same input on each iteration is well-specified with no randomness, then it will generate the same output on each run.
That being said, even basic things like CPU temperature are unpredictable enough to act as an entropy source if they are normalized appropriately. So, don't think this implies that a "cryptographically secure" random number generator can be predicted if you know what time it was run; many of them make use of system-generated entropy feed.
-
Algorithm was the right word :) I'm specifically trying to eliminate outside sources of entropy, memory faults, thread order, unpredictable input such as a light source, etc. I think my question stems from my lack of understanding of random algorithms and maybe I could have made the question more generic. I'm really wondering if it is possible to create any function that returns different results given identical input (including all sources of entropy). Seems like the answer is no Commented Jul 15, 2013 at 16:13
Did you know that people work very hard to ensure that, given the same seed, the same sequence of random numbers is produced every time? This is a desirable property for things like Monte Carlo simulation, as it it means that results are fully reproducible. If you don't specify the seed, something like the time will be used, but that exact reproducibility is really wanted.
The only RNGs where this is truly undesired are those used for cryptography, and those typically achieve this by using the operating system's own random number source (which is not rewindable under normal circumstances and which may use fancy hardware) to provide their seed.
-
Yes, I understand what you're saying. I'm not trying to implement anything new, this was just a late night curiosity. Commented Jul 15, 2013 at 16:17
I suppose if you implemented the algorithm on different hardware platforms and it used techniques like taking the middle N bits from an integer, you could conceivably get different answers if the integer encoding was different (big/little/mid-endian). You also might run into issues running on machines with FPUs versus those that don't if you're manipulating floating-point numbers. Probably not an issue on desktop-class machines, but could be an issue on phones.
2.0 + 2.0on such a system would not give identical results. It doesn't need another source of randomness.