3

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?

Mark Elliot
  • 75,278
  • 22
  • 140
  • 160
tibet_lama
  • 131
  • 2
  • 8
  • 2
    please format the code, i've shown you how – Drakosha Jun 19 '11 at 05:05
  • 1
    There's no need to mention your prospective employer. I reworded your question a bit and formatted it all, please consider reviewing my edit before continuing to update it. – Mark Elliot Jun 19 '11 at 05:12
  • `rand(1,7) := rand(1,5)` works. – Mateen Ulhaq Jun 19 '11 at 05:53
  • Similar: http://stackoverflow.com/q/288739/293791 – Dennis Zickefoose Jun 19 '11 at 05:59
  • When you say "between a and b inclusive", do you mean that `b` is a possible return value? And I guess `random(0,1)` always returns a value less than 1? That would make this particularly tricky. – OpenSauce Jun 19 '11 at 07:57
  • As an aside, if the last question is supposed to be about *integer* random number generators rather than *float* random number generators, then it's actually quite tricky. You can't do it with a bounded number of calls to `random(1,5)`, basically because no power of `5` is a multiple of `7`, so you can never uniformly assign all the possible results of the random calls to outputs. However, you can arrange that the expected number of calls required is quite small (less than 3, I think). For integers this is a classic interview question, for floats it's really just the same question again. – Steve Jessop Jun 19 '11 at 11:30

7 Answers7

8

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

badawi
  • 885
  • 6
  • 8
  • Yups, there was a mistake in generating random integral-number. – badawi Jun 19 '11 at 17:29
  • "Thus, Rand(1,7) = 1 + 6 * (rand(1,5) - 1) / 4" How could this equation possibly generate 7 different outputs when rand(1,5) can only generate 5 outputs? – Terminal Jun 19 '11 at 19:33
  • 1
    I am considering rand(1,5) generates a random real number not integer number. Theoretically, rand(1,5) should generate infinite random numbers between 1 and 5 inclusive. So, rand(1,7) is still infinite sequence of numbers. – badawi Jun 20 '11 at 01:41
  • similar: http://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7 – Terminal Jun 20 '11 at 06:34
4

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)

CAFxX
  • 28,060
  • 6
  • 41
  • 66
2
random(a,b) from random(c,d) = a + (b-a)*((random(c,d) - c)/(d-c))

No?

cadabra
  • 288
  • 2
  • 7
  • 1
    No. First, map from [c,d] to [0,1], then map from [0,1] to [a,b]. You're missing a `random - c` from the first step. – Dennis Zickefoose Jun 19 '11 at 05:45
  • Also, there might be a fencepost error here; I can never remember when you're supposed to add one to get the proper end points. – Dennis Zickefoose Jun 19 '11 at 05:53
  • @Dennis: fenceposts only become an issue if we're talking about integer ranges. The width of a range of rational/real numbers is just the difference between the ends, regardless of whether none, one or both endpoints are included in the range (i.e. whether the range is open, half-open or closed). It's only with integers (or other non-dense sets) that the open-ness of the ends affects the length of the range. – Steve Jessop Jun 19 '11 at 11:35
1

[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..

jemmanuel
  • 466
  • 4
  • 13
0

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.

Identicon
  • 1
  • 1
0

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.

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
-2

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.

Amm Sokun
  • 1,298
  • 4
  • 20
  • 35
  • 1
    -1 for giving an answer that is plain wrong. Why should the product of two uniform random numbers be uniform? Already if you see it for your example of discrete uniform distributions, you easily see that in the range `0..25` there are certain numbers that you will never get, namely the prime numbers. So by no means the result is another uniform distribution. BTW even the sum of two such random variables wouldn't do. Just think of the sum of two independent dice. – Jens Gustedt Jun 19 '11 at 07:41
  • 1
    This is almost but not quite the correct technique for uniform random integers. It should be `A = random(0,4) + 5 * random(0,4)`, where the endpoints are *included* in my `random` function, as stated by the questioner. And of course `random(0,4)` is just `random(1,5) - 1`. Then you retry the last few values, and take A modulo 7 as stated here. – Steve Jessop Jun 19 '11 at 11:39