|
0 registered members (),
5,880
guests, and 3
spiders. |
|
Key:
Admin,
Global Mod,
Mod
|
|
|
Re: NVidia Number Test
[Re: Joey]
#162305
10/22/07 18:33
10/22/07 18:33
|
Joined: May 2002
Posts: 7,441
ventilator
Senior Expert
|
Senior Expert
Joined: May 2002
Posts: 7,441
|
julzmighty has explained the problem with the more likely combinations. ... i had a new idea: Code:
s = 1
def rand7():
global s
s = 1 - s
result = 0
if rand5() > (2+s): result += 1<<0
if rand5() > (2+s): result += 1<<1
if rand5() > (2+s): result += 1<<2
return result
but it uses a global variable and 0 and 7 are about 15% more probable than the rest of the numbers. ... i wonder how much time the candidates have for this question at nvidia and how many come up with a correct solution.  or is this some very well known problem you learn about if you study computer science at an university?
|
|
|
Re: NVidia Number Test
[Re: ventilator]
#162309
10/22/07 20:04
10/22/07 20:04
|
Joined: Jul 2000
Posts: 8,973
Bay Area
Doug
Senior Expert
|
Senior Expert
Joined: Jul 2000
Posts: 8,973
Bay Area
|
Quote:
you still will only get 5 different values. it's like TWO's try.
I missed the "integer" part. 
My updated answer (just off the top of my head):
Code:
ans = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5()) / 7;
6 adds, 1 div, and 7 function calls.
Not a great answer, just a first draft.
|
|
|
Re: NVidia Number Test
[Re: ventilator]
#162310
10/22/07 20:13
10/22/07 20:13
|
Joined: Jun 2005
Posts: 4,875
broozar
Expert
|
Expert
Joined: Jun 2005
Posts: 4,875
|
ok, at first i solved the probabilities:  each arrow from ran5() is 1/5, each from rand2() is 0.5 rand5() is known rand2() is (rand()%2)+6 so the function is (not elegant, but correct, i assume): rand7(){ switch ((rand()%7)){ //first level: determin rand5() or rand2() case 0: case 1: rand2(); break; // 2/7 prob case 2: case3: case 4: case 5: case 6: rand5(); break; // 5/7 prob }}
|
|
|
Re: NVidia Number Test
[Re: broozar]
#162311
10/22/07 20:19
10/22/07 20:19
|
Joined: May 2002
Posts: 7,441
ventilator
Senior Expert
|
Senior Expert
Joined: May 2002
Posts: 7,441
|
doug, this way the probabilites aren't equal. see julzmighty's explanation. and you made a small mistake. after -7 the range is 0..28. Code:
(rand5()+rand5()+rand5()+rand5()+rand5() - 2) / 3
gives this distribution after 1 million runs: {1: 6864, 2: 72170, 3: 243728, 4: 355145, 5: 243124, 6: 72255, 7: 6714} did anyone have a thought about the one i posted earlier? Code:
(rand5() + 5*rand5() + 25*rand5() + 125*rand5() + 625*rand5() + 3125*rand5() + 15625*rand5() - 19531) % 7) + 1
is there some hidden flaw? the result seems to be correct: {1: 143263, 2: 142785, 3: 142579, 4: 142533, 5: 143609, 6: 142520, 7: 142711}
|
|
|
Re: NVidia Number Test
[Re: ventilator]
#162312
10/22/07 20:30
10/22/07 20:30
|
Joined: Jun 2005
Posts: 4,875
broozar
Expert
|
Expert
Joined: Jun 2005
Posts: 4,875
|
Quote:
rand5() + 5*rand5() + 25*rand5() + 125*rand5() + 625*rand5() + 3125*rand5() + 15625*rand5() - 19531) % 7) + 1
is nothing but
Code:
(very_large_nuber)%7+1
which is
Code:
rand()%7+1
of course that's correct, but why would you need 7 function calls, 6 multiplicatios... for such a simple task? you do not really use rand5(), it's only a factor to make your factor in the brackets bigger, you could have used rand6(), rand9() etc. without any change in the result.
|
|
|
|
