2
$\begingroup$

For programming purposes I want a function f(x,R) that given a certain seed x returns the same random value every time, in an arbitrary range R. But, I also want the output to be equally distributed. Is this mathematically possible?

For example, I can take the 1st - nth decimal places of sin(x) such that 10^n > R and divide by R, but I'm sure that this isn't evenly distributed even for R = 10.

Otherwise (veering slightly into Stack Overflow territory here) are there existing well-established functions/algorithms for producing (pseudo)random numbers in this fashion?

  • 2
    Your question is unclear. The distribution of the output will depend on the distribution of the input. Besides, there is no uniform probability distribution on $\mathbb{R}$. So either you fix a range in advance or you go for some non-uniform distribution.2011-03-01
  • 0
    Thanks for the input/output clarification. So you're saying it can't be both "equally distributed" and "arbitrary size"? My comment on Jens' answer might clear things up.2011-03-01
  • 0
    Maybe I should add an example, let's say I'm writing a time-based die rolling simulator, so R is the number of sides and X is the timestamp at which the die is rolled. So I roll a d6 at 2011-03-01 15:09:00.32, so I want f(6,2011030115090032) to a value from 1-6, and the same value (1-6) every time. And f(20,2011030115090032) should also work. And f(1000,2011030115090032) too. And they should all be fair dice.2011-03-01
  • 0
    that is not what mathematicians mean when they say "arbitrary size." To a mathematician this means "any positive integer." You should say "in an arbitrary given range."2011-03-01
  • 0
    @Qiaochu: thanks, I'll fix that2011-03-01

2 Answers 2

0

As per your comment, it seems that you actually want some deterministic function $f(N,x)$ that returns a integer in $[1..N]$, and which, for a fixed $N$ and for different values of $x$ returns values that appear random in that interval. Still, this requirement is not totally clear, because one should stipulate a distribution of $x$. But, if I understand your scenario, one can assume that $x$ is uniform in some large interval (say, the range the full range of integers in you platform-language). So, a simple recipe would be to use a standard pseudorandom generator and use $x$ as a seed. For example, in Java:

static  int getrand(int N,long x) {     Random r = new Random(x);  // random number generator, with x as seed     return r.nextInt(N)+1;     // pseudoradom number in 1..N range  }  

Or you can directly implement your own pseudorandom routine, eg,

static  int getrand2(int N,long x) {     long a=1664525;       long c=1013904223;     long res = (a*x+c)&0xFFFFFFFF;      return (int)((res % N)+1); } 
  • 0
    Thanks. [Linear congruential generator](http://en.wikipedia.org/wiki/Linear_congruential_generator) is basically the answer I was looking for, and of course it led me to [pseudorandom number generators](http://en.wikipedia.org/wiki/Pseudorandom_number_generator) which seems so obvious in hindsight.2011-03-02
0

To give a StackOverflowy answer, how about generating a random value in your given range for every new input and return the previously generated value if the input appears again? You'd have to store every pair, though. I think this is the only way to introduce randomness into your setup.

The example given in your question is not random at all, it is deterministic. Are you sure that you are really looking for randomness instead of maybe a hash function?

  • 0
    Maybe I'm looking for human unpredictability rather than true randomness. I think a hash function that returns sufficiently large results would work - something like hash(x) mod R. What term should I be using instead of "random"? "Deterministic chaotic"?2011-03-01
  • 0
    See also my example added as a comment to the question.2011-03-01