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
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
