On Wed, 2 Feb 2000, Koen Claessen wrote:
> gen1
> / \
> gen1 gen2 -- once
> / | | \
> gen1 gen2 gen2 gen3 -- twice
>
> In fact, they will produce the *same* generator "gen2" on
> both sides, which will create an undesired dependency
> between the two recursive calls.
>
> This "bug" in Hugs is fixed in the newest version, but it
> was not really a bug in Hugs, but a bug in the report. The
> report should say: "two *independent* generators".
>
> The definition of independent might be: "two generators
> gen1 and gen2 are independent if no "split"-path starting at
> gen1 intersects with a "split"-path starting at gen2".
This might be quite difficult to prove/implement (or maybe not, I haven't
thought about it in real depth). Maybe the solution is to have an extra,
hidden part of the generator state that determines the splitting, so that
although two generators may be equal in the sense that repeatedly calling
next on them produces the same infinite stream of values, they will likely
produce different pairs of generators when they split. (Of course the
hidden state is still behaving deterministically (using a pseudo-random
number generator technique to evolve the splitting state) so that it can
still be forced to be reproducible for debugging purposes.)
This would mean that `independent' could be defined perhaps more tractably
in terms of a condition that a binary tree produced by repeated splitting
has negligible probability of any correlations between the generators in
any subset of the nodes. (The diagram of Koen's shows that it's as much
the fact that having made a non-independent split, the pattern then
repeats itself ad infinitum as the fact that a non-independent split is
made that's causing the problem.)
(One thing I haven't addressed is if it's feasible to have a large enough
internal splitting state that the node subset correlation probability is
very small, and yet be efficiently implementable for splitting the
generators being used at the moment.)
CAVEAT: this is a quick thought which may well be flawed...
___cheers,_dave________________________________________________________
www.cs.bris.ac.uk/~tweed/pi.htm Farenheit 451 is the temperature at
email: [EMAIL PROTECTED] which paper burns. Let's do an experiment to
work tel: (0117) 954-5253 see what temperature melts human brain cells.
