CODEWITHSUNDEEP
c++calgorithm
tibet_lama
tibet_lama

Reputation: 131

Generating random numbers given a uniform random number generator

I was asked to generate a random number between a and b, inclusive, using random(0,1). random(0,1) generates a uniform random number between 0 and 1.

I answered 

(a+(((1+random(0,1))*b))%(b-a))

My interviewer was not satisfied with my usage of b in this piece of the expression:

(((1+random(0,1))*b))

Then I tried changing my answer to:

int*z=(int*)malloc(sizeof(int));
(a+(((1+random(0,1))*(*z)))%(b-a));

Later the question changed to generate random(1,7) from random(1,5). I responded with:

A = rand(1,5)%3
B = (rand(1,5)+1)%3
C = (rand(1,5)+2)%3

rand(1,7) = rand(1,5)+ (A+B+C)%3

Were my answers correct?

Upvotes: 3

Views: 4580

Answers (7)

Identicon
Identicon

Reputation: 1

I think that there is a nicer answer to this. There is one value (probability -> zero) that this overflows and thus the modulus is there.

  1. Take a random number x in the interval [0,1].

  2. Increment your upper_bound which could be a parameter by one.

  3. Calculate (int(random() / (1.0 / upper_bound)) % upper_bound) + 1 + lower_bound .

This ought to return a number in your desired interval.

Upvotes: 0

Amm Sokun
Amm Sokun

Reputation: 1298

given random(0,5) you can generate random(0,7) in the following way

A = random(0,5)*random(0,5) now the range of A is 0-25

if we simply take the modulo 7 of A, we can get the random numbers but they wont be truly random as for values of A from 22-25, you will get 1-4 values after modulo operation, hence getting modulo 7 from range(0,25) will bias the output towards 1-4. This is because 7 does not evenly divide 25: the largest multiple of 7 less than or equal to 25 is 7*3=21 and it is the numbers in the incomplete range from 21-25 that will cause the bias.

Easiest way to fix this problem is to discard those numbers (from 22-25) and to keep tying again until a number in the suitable range come up.

Obviously, this is true when we assume that we want random integers.

However to get random float numbers we need to modify the range accordingly as described in above posts.

Upvotes: -2

cadabra
cadabra

Reputation: 288

random(a,b) from random(c,d) = a + (b-a)*((random(c,d) - c)/(d-c))

No?

Upvotes: 2

badawi
badawi

Reputation: 895

I think you were confused between random integral-number generator and random floating-point number generator. In C++, rand() generates random integral number between 0 and 32K. Thus to generate a random number from 1 to 10, we write rand() % 10 + 1. As such, to generate a random number from integer a to integer b, we write rand() % (b - a + 1) + a.

The interviewer told you that you had a random generator from 0 to 1. It means floating-point number generator.

How to get the answer mathematically:

  1. Shift the question to a simple form such that the lower bound is 0.
  2. Scale the range by multiplication
  3. Re-shift to the required range.

For example: to generate R such that

a <= R <= b.  
Apply rule 1, we get a-a <= R - a <= b-a 
                       0 <= R - a <= b - a.

Think R - a as R1. How to generate R1 such that R1 has range from 0 to (b-a)?

R1 = rand(0, 1) * (b-a)   // by apply rule 2.

Now substitute R1 by R - a

R - a = rand(0,1) * (b-a)    ==>   R = a + rand(0,1) * (b-a)

==== 2nd question - without explanation ====

We have 1 <= R1 <= 5

==>   0 <= R1 - 1             <= 4
==>   0 <= (R1 - 1)/4         <= 1
==>   0 <= 6 * (R1 - 1)/4     <= 6
==>   1 <= 1 + 6 * (R1 - 1)/4 <= 7

Thus, Rand(1,7) = 1 + 6 * (rand(1,5) - 1) / 4

Upvotes: 8

Michael Burr
Michael Burr

Reputation: 340188

Were my answers correct?

I think there are some problems.

First off, I'm assuming that random() returns a floating point value - otherwise to generate any useful distribution of a larger range of numbers using random(0,1) would require repeated calls to generate a pool of bits to work with.

I'm also going to assume C/C++ is the intended platform, since the question is tagged as such.

Given these assumptions, one problem with your answers is that C/C++ do not allow the use of the % operator on floating point types.

But even if we imagine that the % operator was replaced with a function that performed a modulo operation with floating point arguments in a reasonable way, there are still some problems. In your initial answer, if b (or the uninitialized *z allocated in your second attempt - I'm assuming this is a kind of bizarre way to get an arbitrary value, or is something else intended?) is zero (say the range given for a and b is (-5, 0)), then your result will be decidedly non-uniform. The result would always be b.

Finally, I'm certainly no statistician, but in your final answer (to generate random(1,7) from random(1.5)), I'm pretty sure that A+B+C would be non-uniform and would therefore introduce a bias in the result.

Upvotes: 0

jemmanuel
jemmanuel

Reputation: 476

[random(0,1)*(b-a)] + a, i think would give random numbers b/w a&b. ([random(1,5)-1]/4)*6 + 1 should give the random nubers in the range (1,7) I am not sure whether the above will destroy the uniform distribution..

Upvotes: 1

CAFxX
CAFxX

Reputation: 30291

random(a,b) from random(0,1):

random(0,1)*(b-a)+a

random(c,d) from random(a,b):

(random(a,b)-a)/(b-a)*(d-c)+c

or, simplified for your case (a=1,b=5,c=1,d=7):

random(1,5) * 1.5 - 0.5

(note: I assume we're talking about float values and that rounding errors are negligible)

Upvotes: 4

Related Questions