Increase the period for rand, fix negative time

[yaxu]

I've noticed that rand has a period of 300 cycles.

tidal> (1 ~> struct "t t t t" rand) :: Pattern Double
(0>¼)|0.392595736309886
(¼>½)|0.13890133425593376
(½>¾)|0.602940147742629
(¾>1)|0.3260140661150217
tidal> (301 ~> struct "t t t t" rand) :: Pattern Double
(0>¼)|0.392595736309886
(¼>½)|0.13890133425593376
(½>¾)|0.602940147742629
(¾>1)|0.3260140661150217

I haven't heard of anyone noticing it loop, but it's feasible that someone could under some conditions.

@dktr0 do you see an advantage in setting at that, rather than something a few orders of magnitude higher?

Also what looks more like a bug, negative time gives negative numbers:

tidal> (-1 ~> struct "t t t t" rand) :: Pattern Double
(0>¼)|-0.392595736309886
(¼>½)|-0.13890133425593376
(½>¾)|-0.602940147742629
(¾>1)|-0.3260140661150217

[dktr0]

@yaxu I don't fully remember why I settled on 300 ages ago... but doing a few quick tests now, if you stretch the algorithm over 300000 or 3000000 cycles, and then sample at 1/16 of a cycle, there is a clear pattern of cyclical behaviour. Here's at 300000:

*Test> fmap timeToRand $ fmap (/16) [0..64]
[0.0,5.2969591692090034e-2,0.10644272342324257,0.15890990756452084,0.21238190680742264,0.2804735545068979,0.31832335516810417,0.3859429322183132,0.4247638750821352,0.4928864538669586,0.5609471704810858,0.613443735986948,0.6366466525942087,0.6891457810997963,0.7723894044756889,0.8405124042183161,0.8490547277033329,0.9171469118446112,0.9862459301948547,7.409052923321724e-3,0.12189428322017193,0.1744072400033474,0.22688753344118595,0.29502829164266586,0.27329336665570736,0.3414011038839817,0.37829150445759296,0.44775657169520855,0.5443057864904404,0.6006928700953722,0.6814978308975697,0.737887954339385,0.6976059153676033,0.7622828707098961,0.8342937659472227,0.8985254727303982,0.9724919218569994,8.391769230365753e-2,1.4818167313933372e-2,0.1888825185596943,0.24331554397940636,0.17519287578761578,0.3492875024676323,0.29679072834551334,0.4533020444214344,0.40080306492745876,0.5905296057462692,0.5219334363937378,0.5465866755694151,0.7206516228616238,0.6828022692352533,0.8725522384047508,0.7565830703824759,0.9524216447025537,0.8960166834294796,9.76302158087492e-2,8.810803294181824e-2,1.6092436388134956e-2,0.2018892802298069,0.12987672351300716,0.36299572326242924,0.3066075071692467,0.47577585093677044,0.4193868599832058,0.39521189220249653]

30000 looks "better" - although if one were to sample the algorithm ten times faster I guess the same issue would appear:

*Test> fmap timeToRand $ fmap (/16) [0..64]
[0.0,5.2969591692090034e-2,0.10644272342324257,0.15890990756452084,0.21238190680742264,0.2804735545068979,0.31832335516810417,0.3859429322183132,0.4247638750821352,0.4928864538669586,0.5609471704810858,0.613443735986948,0.6366466525942087,0.6891457810997963,0.7723894044756889,0.8405124042183161,0.8490547277033329,0.9171469118446112,0.9862459301948547,7.409052923321724e-3,0.12189428322017193,0.1744072400033474,0.22688753344118595,0.29502829164266586,0.27329336665570736,0.3414011038839817,0.37829150445759296,0.44775657169520855,0.5443057864904404,0.6006928700953722,0.6814978308975697,0.737887954339385,0.6976059153676033,0.7622828707098961,0.8342937659472227,0.8985254727303982,0.9724919218569994,8.391769230365753e-2,1.4818167313933372e-2,0.1888825185596943,0.24331554397940636,0.17519287578761578,0.3492875024676323,0.29679072834551334,0.4533020444214344,0.40080306492745876,0.5905296057462692,0.5219334363937378,0.5465866755694151,0.7206516228616238,0.6828022692352533,0.8725522384047508,0.7565830703824759,0.9524216447025537,0.8960166834294796,9.76302158087492e-2,8.810803294181824e-2,1.6092436388134956e-2,0.2018892802298069,0.12987672351300716,0.36299572326242924,0.3066075071692467,0.47577585093677044,0.4193868599832058,0.39521189220249653]

So I guess 300 was probably something like a number that was sure to push this potential for short-term cyclic behaviour far out of salience?

Another thought might be to make this user configurable - a parameter that is read from the environment. If another parameter, some kind of offset,was also added so that there were two parameters controlling the generator that might retain the blinding speed of this algorithm, while also adding a somewhat more intuitive UI for having multiple random streams, while also addressing this issue (when it is an issue).

Re: the negative time issue... timeToRand seems to work fine with negative times, so I suspect it is something to do with the way it is currently integrated into rand:

rand = Pattern (\(State a@(Arc s e) _) -> [Event (Context []) Nothing a (realToFrac $ (timeToRand ((e + s)/2) :: Double))])

I am a bit suspicious of that double conversion in the middle of things there. Could that be doing weird things, and might changing it to Rational help?

[fbous]

I did a bit of digging last weekend
and I found repeating patterns everywhere,
on multiple scales.
My final conclusion is
that xorshift is not suitable
for the way we are trying to use it.
The problem is
that a random numbers based on xorshift are meant to be generated
by reappying xorshift consecutively, i.e.,

rnd = seed : xorshift seed : xorshift (xorshift seed) : xorshift^3 seed ...

while what we do is something like

rnd = [xorshift seed1, xorshift seed2, xorshift seed3, ...]

Unfortunately the xorshift does not scramble the bits enough
so when using similar numbers as seeds,
actually similar numbers come out after the first iteration of xorshift.

My suggestion is to use a hash function to randomise the time seed
instead of xorshift.
I looked around a bit and found murmur3 to be a suitable candidate
it is simple and fast.
It has a few more operations than xorshift
but I think it should be still simple enough
to not cause a performance bottleneck.
I tested the generated numbers a bit
by plotting different samplings of it
and it seems fine to me.

The implementation that is currently in pull request #942
has a period of 2^16 = 65536 cycles
and divides a cycle into 2^16 values,
this should be enough I think
(if someone were to play 10 cycles per second
it would still only repeat after almost 2 hours).

[dktr0]

This looks great to me. Thanks @fbous !!!