So, no valid answer yet?

How about this?
Code:

---

int rand7()
{
  int x;
  do
  {
    x = ((rand5()+5*rand5())-5);
  } while(x>21);
  return ((x%7)+1);
}

---

Again, top of my head. But it gives equal probability (no dice effect).
I do not like the loop, but it is quicker than finding the LCD.

that's basically the same as mine posted a bit more than a week ago. go show-all and search "794517" to jump straight to it if need be, but it's mostly the same as yours (except it returns between 1-7 instead of 1-6 )

julz

Yes, as far as I can tell you have the only correct answer in the thread (I went back and fixed my +1 error ).

Congratulations on your job at nVidia.

But, if I gave this as an interview question, my next question would be: "Can you do it without the loop?".

as i said, it seems impossible to acheive both equal distribution and no predictability without at least one branch.

it does seem impossible i was looking for some relationships between the probabilities of different digits showing 1's in binary format (as i'm sure Joey or Ventilator touched on earlier but i can't seem to find it), but that wasn't getting anywhere, and i have loads of studying to do (for exams which won't ask questions like this ).

did anyone find out how much time candidates were given?

Quote:

---

Congratulations on your job at nVidia.

---

haha i wouldn't want a job there.

julz

Code:

---

temp = 0
def rand7():
    global temp
    temp += rand5() + 5*rand5()
    return temp % 7 + 1

---

how about joey's solution but with a second rand5()? wouldn't the predictability be negligible then?

...
i think nvidia just wants to hear something like: you either need a conditional which will result in non predictable runtime or you have to live with some small error in the probability distribution.

the question is how much time you have to find this answer. if you have a whole day to experiment and write test programs it wouldn't be that hard.

i gotta say i really like that answer

julz

IMHO: When you need a random number you want it to be truly random.
Predictable is not always a bad thing, but you want random distribution.
So "(rand5() + 5*rand5())%7 + 1" would not be a valid answer.

Quote:

---

the question is how much time you have to find this answer. if you have a whole day to experiment and write test programs it wouldn't be that hard.

---

Normally they ask these questions during an on-site interview, but this could be a take home test to help weed out candidates.

Even with a whole day, most people wouldn't get it right.

Quote:

---

as i said, it seems impossible to acheive both equal distribution and no predictability without at least one branch.

---

Nope. It is possible but (as far as I can see) not practical.
One method involves generating the numbers "offline" and just using a lookup table. Another method requires very large numbers.

well you could sort-of write your own random number generator without using a single branch or loop, but then you could skip using rand5 anyway.

Joey: That is certainly thinking "outside the box". But I'm guessing nVidia wants you to use rand5.

Besides, can you write a true random number generator that ran quicker?