10

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.

  • What you are talking about is a pseud-random-number generator, to be specific. – Marcel Jul 15 '13 at 6:22
  • Most languages allow the possibility of instantiating a random number generator without having to specify the seed so that the seed is "random" as well. There is a reason why seeds are used. – Neil Jul 15 '13 at 8:52
  • 1
    @Neil: in those cases, there is still a seed, it's just implicit, usually the system time. – Michael Borgwardt Jul 15 '13 at 9:24
  • @MichaelBorgwardt, I simply said that the seed would be random as well. Of course nothing is truly random, but usually the system time provides a decent seed, so long as you do not often instantiate a random number generator without passing a seed, in which case you may get the same seed "random" seed twice. – Neil Jul 15 '13 at 9:33
  • There's an interesting research area into inexact hardware, which has a statistically well-defined inaccuracy. The potential benefit is a lower power use. Just calculating 2.0 + 2.0 on such a system would not give identical results. It doesn't need another source of randomness. – MSalters Jul 15 '13 at 10:23
15

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.

14

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 – ConditionRacer Jul 15 '13 at 16:13
7

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. – ConditionRacer Jul 15 '13 at 16:17
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.