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.
Random – Can a Random Number Generator Produce Different Output with Identical Seeds?
random
Related Solutions
Digging from http://www.befria.nu/elias/pi/binpi.html to get the binary value of pi (so that it was easier to convert into bytes rather than trying to use decimal digits) and then running it through ent I get the following for an analysis of the random distribution of the bytes:
Entropy = 7.954093 bits per byte.
Optimum compression would reduce the size of this 4096 byte file by 0 percent.
Chi square distribution for 4096 samples is 253.00, and randomly would exceed this value 52.36 percent of the times.
Arithmetic mean value of data bytes is 126.6736 (127.5 = random).
Monte Carlo value for Pi is 3.120234604 (error 0.68 percent).
Serial correlation coefficient is 0.028195 (totally uncorrelated = 0.0).
So yes, using pi for random data would give you fairly random data... realizing that it is well known random data.
From a comment above...
Depending on what you are doing, but I think you can use the decimals of the square root of any prime number as a random number generator. These should at least have evenly distributed digits. – Paxinum
So, I computed the square root of 2 in binary to undetake the same set of problems. Using Wolfram's Iteration I wrote a simple perl script
#!/usr/bin/perl
use strict;
use Math::BigInt;
my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;
while(1) {
my $unew;
my $vnew;
if($u->bcmp($v) != 1) { # $u <= $v
$unew = $u->bmul(4);
$vnew = $v->bmul(2);
} else {
$unew = ($u->bsub($v)->bsub(1))->bmul(4);
$vnew = ($v->badd(2))->bmul(2);
}
$v = $vnew;
$u = $unew;
#print $i," ",$v,"\n";
if($i++ > 10000) { last; }
}
open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);
Running this for the first 10 matched A095804 so I was confident I had the sequence. The value vn as when written in binary with the binary point placed after the first digit gives an approximation of the square root of 2.
Using ent against this binary data produces:
Entropy = 7.840501 bits per byte.
Optimum compression would reduce the size
of this 1251 byte file by 1 percent.
Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.
Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).
First, you use Normal distribution to generate population of each village. This should give you number that is pretty close to total population. To get exact population, just add or remove the difference evenly across all villages.
The problem of this algorithm is that there is some probability of generating negative population. But that heavily depends on parameters. For parameters from your example, the probability is extremely slim. But for parameters (10000, 100, 50), the probability is there.
import random
def generate_villages(total, count, deviation):
average = total / count
villages = [random.gauss(average, deviation) for _ in range(count)]
diff = (sum(villages) - total)/count
villages = [round(v - diff) for v in villages]
return villages
vil = generate_villages(400000, 800, 50)
print(vil)
print(sum(vil))
While this code doesn't give precise number. It deviates +-10 which is fine.
Best Answer
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.