Hello Dean,
- moves the stuff to common and fully removes random/srandom (Tom)
- includes a range generation function based on the bitmask method (Dean)
but iterates with splitmix so that the state always advances once (Me)
At the risk of repeating myself: do *not* invent your own scheme.
The problem with iterating using splitmix is that splitmix is a simple
shuffling function that takes a single input and returns a mutated
output depending only on that input.
It also iterates over its 64 bits state in a round robin fashion so that
the cycle size is 2^64 (it is a simple add).
So let's say for simplicity that you're generating numbers in the range
[0,N) with N=2^64-n and n<2^63. Each of the n values in [N,2^64) that
lie outside the range wanted are just mapped in a deterministic way back
onto (at most) n values in the range [0,N), making those n values twice
as likely to be chosen as the other N-n values.
I do understand your point. If the value is outside the range, splitmix
iterates over its seed and the extraction functions produces a new number
which is tested again. I do not understand the "mapped back onto" part,
the out of range value is just discarded and the loops starts over with a
new derivation, and why it would imply that some values are more likely to
come out.
So what you've just invented is an algorithm with the complexity of the
unbiased bitmask method,
That is what I am trying to implement.
but basically the same bias as the biased integer multiply method.
I did not understand.
I don't understand why you object to advancing the state more than
once. Doing so doesn't make the resulting sequence of numbers any less
deterministic.
It does, somehow, hence my struggle to try to avoid it.
call seed(0xdeadbeef);
x1 = somepseudorand();
x2 = somepseudorand();
x3 = somepsuedorand();
I think we should want x3 to be the same result whatever the previous
calls to the API.
In fact, I'm pretty sure you *have to* advance the state more than
once in *any* unbiased scheme. That's a common characteristic of all
the unbiased methods I've seen, and intuitively, I think it has to be
so.
Yes and no. We can advance another state seeded by the root prng.
Otherwise, I'm happy with the use of the bitmask method, as long as
it's implemented correctly.
I did not understand why it is not correct.
--
Fabien.
