I'm pretty sure the time of this function is dominated by the call to
rand(), but it never occurred to do a table lookup for the mask,
interesting idea.
- Don
On Thu, 2006-12-07 at 22:36 +0100, Antoine de Maricourt wrote:
> If this randint routine is critical, you can save some calls to rand()
> when you know that n is always below some value (see my previous post
> about bitmap go).
> For instance if n < 128 (probably true for 9x9 go), you could try:
>
> while (true) {
> r = rand();
>
> if ((r & v) < n) return (r & v);
> r >>= 7;
> if ((r & v) < n) return (r & v);
> r >>= 7;
> ... // 2 more times
> }
>
> Also it could be better to read the mask (v) from a table (provided
> the upper limit of n is small enough). At least on a P4, it will avoid
> a long data dependency chain and might give a (probably small)
> improvment. It might even be benefical on other processors.
>
> Antoine
>
> > On Thu, 2006-12-07 at 16:05 +0100, Łukasz Lew wrote:
> >
> > > ii = pm::rand () % empty_v_cnt; // TODO improve speed "%"
> > >
> >
> >
> > Try this, I think it could be faster, not sure, but has the advantage
> > that it's slightly more correct.
> >
> > // returns an integer between 0 and n-1 inclusive
> > //
> > unsigned long randint(unsigned long n)
> > {
> > unsigned long v = n;
> > unsigned long r;
> >
> > v--;
> > v |= v >> 1;
> > v |= v >> 2;
> > v |= v >> 4;
> > v |= v >> 8;
> > v |= v >> 16;
> >
> > do { r = rand(); } while ( (r & v) >= n );
> >
> > return( r & v );
> > }
> >
> >
> >
> > - Don
> >
> >
> > _______________________________________________
> > computer-go mailing list
> > [email protected]
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> >
> >
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
