Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Alex B. Mar 1 '11 at 8:28
    
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. –  d3vid Mar 1 '11 at 12:59
    
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. –  d3vid Mar 1 '11 at 13:11
    
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." –  Qiaochu Yuan Mar 1 '11 at 14:45
    
@Qiaochu: thanks, I'll fix that –  d3vid Mar 1 '11 at 18:58

2 Answers 2

up vote 0 down vote accepted

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);
}
share|improve this answer
    
Thanks. Linear congruential generator is basically the answer I was looking for, and of course it led me to pseudorandom number generators which seems so obvious in hindsight. –  d3vid Mar 2 '11 at 6:31

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?

share|improve this answer
    
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"? –  d3vid Mar 1 '11 at 12:56
    
See also my example added as a comment to the question. –  d3vid Mar 1 '11 at 13:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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