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.

If it even matters I have an improved version of my first program which uses on average 3.415 calls per number generated.

<pre>

   10   randomize
   11   dim STAT(38)
   12   R_count=0
   14   R=0
   15   for TEST=1 to 1000000
   19   if R>0 then 40
   20   R=fnRND
   40   if (R@7)=1 then V=1:goto 100
   45   if (R@7)=2 then V=1:goto 100
   50   if (R@7)=4 then V=33:goto 130
   55   if (R@7)=5 then V=33:goto 130
   60   if (R@7)=6 then V=37:goto 150
   65   if (R@7)=0 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:goto 150
  106   R=R-5:goto 151
  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:goto 150
  115   R=R-4:goto 151
  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:goto 150
  124   R=R-3:goto 151
  130   R=fnRND
  131   if R=1 then V=V+2:goto 140
  132   if R=2 then V=V+1:goto 150
  133   R=R-2:goto 151
  140   R=fnRND
  141   if R=1 then V=V+1:goto 150
  142   R=R-1:goto 151
  150   R=0
  151   ' 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)
</pre>

Posted by Brian Smith on 2004-06-16 13:47:48