A particular random number generator returns positive integer n with probability 1/(2^n). (ie '1' with probability 1/2, '2' with probability 1/4, '3' with probability 1/8, etc.)
Using this random number generator, write an algorithm which chooses a random integer from 1 to 37 with equal probability.
This is my answer to the problem written in UBASIC
Lines 11-15, 199-205, 1005 are statistics lines.
Lines 1000-1050 simulate the random number generator given in the problem.
1,000,000 numbers 1-37 used 4,378,259 random number calls.
10 randomize
11 dim STAT(38)
12 R_count=0
15 for TEST=1 to 1000000
20 R=fnRND
30 if R=2 then 20
40 if (R@4)=1 then V=1:goto 100
50 if (R@4)=0 then V=33:goto 130
60 if (R@4)=2 then V=37:goto 150
70 goto 20
100 R=fnRND
101 if R=1 then V=V+16:goto 110
102 if R=2 then V=V+8:goto 120
103 if R=3 then V=V+4:goto 130
104 if R=4 then V=V+2:goto 140
105 if R=5 then V=V+1
106 goto 150
110 R=fnRND
111 if R=1 then V=V+8:goto 120
112 if R=2 then V=V+4:goto 130
113 if R=3 then V=V+2:goto 140
114 if R=4 then V=V+1
115 goto 150
120 R=fnRND
121 if R=1 then V=V+4:goto 130
122 if R=2 then V=V+2:goto 140
123 if R=3 then V=V+1
124 goto 150
130 R=fnRND
131 if R=1 then V=V+2:goto 140
132 if R=2 then V=V+1
133 goto 150
140 R=fnRND
141 if R=1 then V=V+1
150 ' print V;
199 STAT(V)+=1
200 next TEST
201 print
202 for STATS=1 to 37
203 print STATS;STAT(STATS),
204 next STATS
205 print:print "Random Calls";R_count
999 end
1000 fnRND
1005 R_count=R_count+1
1010 X=1
1020 if rnd>0.5 then 1050
1030 X=X+1
1040 goto 1020
1050 return(X)
My algorithm
