A simple (but effective) random number generator(?!)

[orz]

Jorgen
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc or platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

Sebastion
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The leftshift then bitwise or a trinary operator on the most
significant bit thing. It's an obfuscated 1 bit barrel shift.
Replacing it with a non-obfuscated barrel shift seems more
straightforward, and makes it possible to add the amount of the shift
as another template parameter. Although... empirical testing suggests
that 1 may be the ideal amount of barrel shift there, assuming no
other details of the algorithm were changed.
C. The xor by mask is equivalent to a bitwise not operation. And
since it's done on a result of an xor anyway, it's equivalent to
applying the bitwise not to one of the terms of the xor. And since
one of the terms of the xor is a simple counter, that's pretty much
equivalent to not applying the bitwise not operation at all, and
simply decrementing counter instead of incrementing it.

 

[orz]

Jorgen
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using a modulo operator on an RNG
output is never optimal (though it can be convenient), but it's far
from the only way that the low bits of an RNGs output might be
emphasized. Those people who chose libc or platform RNGs have
historically (and to present day so far as I know) consistently picked
bad to mediocre RNGs.

Sebastion
Assuming that the algorithm I'm working with correctly represents the
one you're working with, possible changes to consider are:
A. Simply forcing scale to always be an odd number fixes the issue
where the top bits of value get thrown away. That change alone
results in an enormous improvement in the RNGs quality.
B. The leftshift then bitwise or a trinary operator on the most
significant bit thing. It's an obfuscated 1 bit barrel shift.
Replacing it with a non-obfuscated barrel shift seems more
straightforward, and makes it possible to add the amount of the shift
as another template parameter. Although... empirical testing suggests
that 1 may be the ideal amount of barrel shift there, assuming no
other details of the algorithm were changed.
C. The xor by mask is equivalent to a bitwise not operation. And
since it's done on a result of an xor anyway, it's equivalent to
applying the bitwise not to one of the terms of the xor. And since
one of the terms of the xor is a simple counter, that's pretty much
equivalent to not applying the bitwise not operation at all, and
simply decrementing counter instead of incrementing it.

 

[Francesco S. Carta]

I think we got that. ;-)

I think that's not exactly orz's fault - Google Groups is messed up and
isn't showing posts on the web interface, even if keeping posting it...

I'm sending this message to orz's email too.

 

[orz]

I think we got that. ;-)

Regards

Paul Bibbings

Sorry about the multiple posts, I'm having technical difficulties
posting to google groups. In fact I've had 3 different kinds of
technical difficulties posting from 3 different computers. I'm
beginning to hate this.

 

[Öö Tiib]

On Wed, 2010-06-23, orz wrote:

...


Yes. There are mixed opinions on the wisdom of that -- there have been
heated discussions about it here in the past.  To use myself as an
example, I happily do rand() % N, and call implementations old and
broken if this gives bad results. At least Linux and the BSDs are
documented to have PRNG where this is ok.

When that N is not twos complement you get (slightly) loaded dice with
all RNG-s.

 

[Ian Collins]

Sorry about the multiple posts, I'm having technical difficulties
posting to google groups. In fact I've had 3 different kinds of
technical difficulties posting from 3 different computers. I'm
beginning to hate this.

Then don't use it! Access Usenet in the traditional manner and all will
be well with the world.

 

[Jorgen Grahn]

When that N is not twos complement you get (slightly) loaded dice with
all RNG-s.

I'm not sure what you mean, but yeah, there is a problem when
RAND_MAX % N != 0. (It's easy to see and not so slight if you imagine
RAND_MAX being 100, and you want values between 0 and 90.)

I have learned to compensate for that in recent years, but forgot to
mention that.

/Jorgen

 

[Jorgen Grahn]

On Fri, 2010-06-25, orz wrote:

[about using rand() % N]

Jorgen:
I think the answer is pretty clear. Any detectable failure of any
bits of output is a major flaw. Using % on an RNG output is never
optimal (though it can be convenient), but it's far from the only way
that the low bits of an RNGs output might be emphasized. Those people
who chose libc / platform RNGs have historically (and to present day
so far as I know) consistently picked bad to mediocre RNGs.

I guess what I'm saying is that for my purposes, I'm happy with a
mediocre PRNG. The bad ones -- I'm assuming they belong to history.

/Jorgen