bug-apl
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-apl] Bad quality of the roll function


From: Juergen Sauermann
Subject: Re: [Bug-apl] Bad quality of the roll function
Date: Fri, 22 Aug 2014 15:01:39 +0200
User-agent: Mozilla/5.0 (X11; Linux i686; rv:31.0) Gecko/20100101 Thunderbird/31.0

Hi Kacper,

thanks a lot, included in SVN 442.

/// Jürgen


On 08/22/2014 12:03 AM, Kacper Gutowski wrote:
I don't think there is anything to gain by changing the main LCG part
given the constraints.  I don't know how good are the parameters used by
GNU APL but they should be okay since those are the ones proposed by Knuth.

LCGs have a number of well known weaknesses, one of which is that their
less significant bits are not so random, and so if you simply mod range
it, the results will be poor (and if range divides LCG's modulus it will
fail spectacularly as it did for me).  But it still has a full 64-bit
period and good spectral properties so it's good enough for updating ⎕RL
state and its quality can be improved by adding output transformation,
exactly as you did in r439.

As I see, your transformation is simply a bit reversal.  It fixes my case.
Too bad compiler does NOT optimize out that loop!  It generates a loop
with a conditional move inside.  Yuck, that's awfully slow.  Bit reversal
can be done *much* more efficiently with [1].  However, reversing bits is
generally more expensive than needed and it might make serial correlation
even worse.  Following the recommendation from Numerical Recipes, I would
suggest permuting output with a single iteration of xorshift instead of
bit reversal.  It would be much faster and much better at the same time.


On 2014-08-20 19:32:34, Juergen Sauermann wrote:
Any suggestions are welcome for this topic.
The only issue left is bias resulting from reducing the range from
original 2⋆64 to some desired one.  The simplest idea is to multiply
the random value by the target range divided by the generator's range.
This spreads out bias evenly (rather than making low values more probable
than high as in the case of modulo size, it makes every some-th value
have different probability than others) and is often assumed to be good
enough for non-cryptographic purposes (and roll is obviously not suitable
for those anyway).  We can easily do better, though.

Other strategy — and it's the only one that guaranties result to have
uniform distribution — is to re-roll if random value is outside of
the range.  If you decide to follow my suggestion of using xorshift
to improve LCG's output, re-rolling can be done very easily without
disturbing ⎕RL simply by further iterating xorshift (which is a good
random generator by itself).

I attached a patch that implements the above.  Please review it, and
feel free to use it. (Sorry if it doesn't match your coding style;
I wasn't sure how to properly indent brackets.)



As a historical curiosity, recently I have read in [2] that APL\360
and its descendants used MINSTD generator and then derived results
by multiplying with range divided by modulus.  APL2 manual shows some
sequences that confirm it also implemented it exactly the same way and
I just checked that Dyalog also uses the same algorithm.  This is also
related to the choice of ⎕RL←16807 as a starting point that was
brought up there on the list last month.


[1] http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel
[2] https://web.archive.org/web/20120226063645/www.sigapl.org/qqv8n3p42.htm


-k


reply via email to

[Prev in Thread] Current Thread [Next in Thread]