@Jitesh: I did. But here is another try:
We construct a fraction p' by using the random number generator to
select the bits. So the number is 0.f()f()f()f()..., where each f() is
a zero- or a one-bit. We compare p to p'. If, no matter what remaining
bits we choose for p' we will have p < p', then we return 1. If, no
matter what remaining bits we choose for p' we will have p > p', then
we return 0. If we can't say either of those cases for sure, we
generate another fraction bit and try again. So when does one of the
comparisons succeed? If a bit of p is 0 and the corresponding bit of
p' = 1, then we know that p < p', Similarly, if a bit of p is 1 and
the corresponding bit of p' = 0, then we know that p > p'. Now,
looking at the code, note that i = p+p is 0 if p < 1/2, or 1 if p >
1/2. I.e., I is the high order bit of the fraction p. Then p+p-i is
the fractional part of 2*p. The do-while loop then exposes the bits of
p, one at a time. These are compared to the random stream of values of
f(). As long as they agree, we can't tell whether the p' implicit in
the stream of values of f() so far will be less than or greater than
p. But when they disagree, we know which way the test will go, so we
return 0 or 1 as appropriate. Hope this helps.
Dave
On Sep 13, 12:39 am, JITESH KUMAR <jkhas...@gmail.com> wrote:
> Hi Dave,
> Can you please explain your approach?
>
>
>
>
>
> On Tue, Sep 13, 2011 at 9:21 AM, Dave <dave_and_da...@juno.com> wrote:
> > Here's another way, using a rejection technique on the bits of the
> > mantissa of p. Each iteration of the do-while loop exposes another
> > high-order bit of p, and the do-while loop iterates as long as the
> > random bits produced by f match the high order bit sequence of p. This
> > most likely will use fewer evaluations of f() than Don's approach.
>
> > int g(double p)
> > {
> > int i;
> > do
> > {
> > i = p + p;
> > p += p - i;
> > } while( i == f() );
> > return 1 - i;
> > }
>
> > Dave
>
> > On Sep 12, 10:19 am, Don <dondod...@gmail.com> wrote:
> > > For particular values of p we might be able to do better, but for
> > > unknown values of p, I can't think of anything better than this:
>
> > > int g(double p)
> > > {
> > > int n = 0;
> > > for(int i = 0; i < 30; ++i)
> > > n += n+f();
> > > return n > (int)(p*1073741824.0);
>
> > > }
>
> > > On Sep 12, 9:55 am, JITESH KUMAR <jkhas...@gmail.com> wrote:
>
> > > > Hi
> > > > You are given a function f() that returns either 0 or 1 with equal
> > > > probability.
> > > > Write a function g() using f() that return 0 with probability p (where
> > 0<p<1
> > > > )
>
> > > > --
> > > > *Regards
> > > > Jitesh Kumar*- Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> *Regards
> Jitesh Kumar
> *- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
