Re: [gnugo-devel] rand() % n

[Douglas Ridgway]

On Fri, 14 May 2004, Gunnar Farnebäck wrote:

> David wrote:
> > I was really wondering why so much time was being spent worrying
> > about the low order bits when it does seem that most any decent RNG
> > (and perhaps even a known poor one) would be far better than this
> > application would require.
> 
> You'd have to ask Douglas about that. :-)

*sigh* I'd rather not spend any time worrying about low order bits --
that's why I wrote the patch. Picking out and using low order bits is a
standard solecism with a standard solution, which is what the patch is
trying to implement. Using a generator with good properties for every bit
would work too, of course. Any strong crypto algorithm should be fine, for
example, but they don't normally get used for RNG for performance reasons.

As to why bother, the justification is the same as using a good RNG:  it
may or may not make a difference in any particular situation, but it's no
more effort, and it's one less thing to think about when things get funky.  
It wasn't supposed to be controversial :-)

> > It was not my intent to suggest the use of another RNG, unless the
> > overflow problem really is an issue.
> 
> The overflow problem only exists in the proposed patch,

I'm not certain that I understand the overflow problem. The numerator can
reach 2^64 or so (if both n and next_rand() are 2^32-1), but that doesn't
mean 64 bits of precision are required. There only needs to be enough to
get the right answer after dividing by 2^32 and drop the noninteger part
-- 33 should be enough, and 53 should be lots. But maybe I'm confused,
it's happened before.

> not in the
> current code. I see no reason to change the latter. Except for
> everything else introducing floating point computations in the random
> number generation would add another potential source for platform
> dependencies.

On portability and performance, I'll defer to your judgement. Fixing this 
is not that important.

doug.