Page 1 of 3
RKISS
Posted: Sat Jan 01, 2011 10:39 pm
by Gerd Isenberg
Hi,
First a happy new computer chess year to all!
Just had a look to the new RKISS prng under GPL used in Stockfish 2.0.
Interesting code, the rotates are all primes. But sub, xor, add looks a bit arbitrary.
Code: Select all
static u64 a,b,c,d;
u64 e;
e = a - (b rol 7);
a = b ^ (c rol 13);
b = c + (d rol 37);
d = e + a;
return d;
Is there any theory about that bit-twiddling available on-line? Or is such stuff more empirical trial and error?
Cheers,
Gerd
Re: RKISS
Posted: Sat Jan 01, 2011 11:01 pm
by Gerd Isenberg
oups, forgot one line c = d + e:
Code: Select all
static u64 a,b,c,d;
u64 e;
e = a - (b rol 7);
a = b ^ (c rol 13);
b = c + (d rol 37);
c = d + e;
d = e + a;
return d;
Re: RKISS
Posted: Sat Jan 01, 2011 11:43 pm
by mcostalba
Gerd Isenberg wrote:
Is there any theory about that bit-twiddling available on-line? Or is such stuff more empirical trial and error?
This code was kindly donated to us by Heinz van Saanen that allowed us to license under GPL so to be merged in SF.
We just tested that it works and is 100% an alternative to mersenne.
I don't think it is just trial and error, as reported in the header:
Code: Select all
** A small "keep it simple and stupid" RNG with some fancy merits:
**
** Quite platform independent
** Passes ALL dieharder tests! Here *nix sys-rand() e.g. fails miserably:-)
** ~12 times faster than my *nix sys-rand()
** ~4 times faster than SSE2-version of Mersenne twister
** Average cycle length: ~2^126
** 64 bit seed
** Return doubles with a full 53 bit mantissa
** Thread safe
And here is the dieharder tests reports:
Code: Select all
heinz@linux:~/junk/junk> ./a.out | dieharder -g 200 -a
#=============================================================================#
# dieharder version 3.29.4beta Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name |rands/second| Seed |
stdin_input_raw| 2.13e+07 |4282743765|
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.14890455| PASSED
diehard_operm5| 5| 1000000| 100|0.02837678| PASSED
diehard_rank_32x32| 0| 40000| 100|0.63612384| PASSED
diehard_rank_6x8| 0| 100000| 100|0.78258674| PASSED
diehard_bitstream| 0| 2097152| 100|0.73291748| PASSED
diehard_opso| 0| 2097152| 100|0.36677569| PASSED
diehard_oqso| 0| 2097152| 100|0.35635353| PASSED
diehard_dna| 0| 2097152| 100|0.40227206| PASSED
diehard_count_1s_str| 0| 256000| 100|0.15631848| PASSED
diehard_count_1s_byt| 0| 256000| 100|0.02576356| PASSED
diehard_parking_lot| 0| 12000| 100|0.33868706| PASSED
diehard_2dsphere| 2| 8000| 100|0.61107903| PASSED
diehard_3dsphere| 3| 4000| 100|0.37099325| PASSED
diehard_squeeze| 0| 100000| 100|0.56722772| PASSED
diehard_sums| 0| 100| 100|0.04022953| PASSED
diehard_runs| 0| 100000| 100|0.39906252| PASSED
diehard_runs| 0| 100000| 100|0.26776626| PASSED
diehard_craps| 0| 200000| 100|0.74060276| PASSED
diehard_craps| 0| 200000| 100|0.43273086| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.38433496| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.21739434| PASSED
sts_monobit| 1| 100000| 100|0.13931802| PASSED
sts_runs| 2| 100000| 100|0.51329448| PASSED
sts_serial| 1| 100000| 100|0.39968488| PASSED
sts_serial| 2| 100000| 100|0.20801423| PASSED
sts_serial| 3| 100000| 100|0.22648504| PASSED
sts_serial| 3| 100000| 100|0.79553793| PASSED
sts_serial| 4| 100000| 100|0.13889241| PASSED
sts_serial| 4| 100000| 100|0.35689448| PASSED
sts_serial| 5| 100000| 100|0.32907831| PASSED
sts_serial| 5| 100000| 100|0.96425371| PASSED
sts_serial| 6| 100000| 100|0.29429007| PASSED
sts_serial| 6| 100000| 100|0.67547393| PASSED
sts_serial| 7| 100000| 100|0.27652533| PASSED
sts_serial| 7| 100000| 100|0.43773829| PASSED
sts_serial| 8| 100000| 100|0.00589920| PASSED
sts_serial| 8| 100000| 100|0.00606073| PASSED
sts_serial| 9| 100000| 100|0.36759888| PASSED
sts_serial| 9| 100000| 100|0.41487400| PASSED
sts_serial| 10| 100000| 100|0.85082078| PASSED
sts_serial| 10| 100000| 100|0.25805178| PASSED
sts_serial| 11| 100000| 100|0.52837124| PASSED
sts_serial| 11| 100000| 100|0.05334055| PASSED
sts_serial| 12| 100000| 100|0.67688469| PASSED
sts_serial| 12| 100000| 100|0.84215568| PASSED
sts_serial| 13| 100000| 100|0.99153787| PASSED
sts_serial| 13| 100000| 100|0.76515469| PASSED
sts_serial| 14| 100000| 100|0.26573843| PASSED
sts_serial| 14| 100000| 100|0.26842956| PASSED
sts_serial| 15| 100000| 100|0.45104274| PASSED
sts_serial| 15| 100000| 100|0.40600808| PASSED
sts_serial| 16| 100000| 100|0.50489227| PASSED
sts_serial| 16| 100000| 100|0.65051872| PASSED
rgb_bitdist| 1| 100000| 100|0.90681142| PASSED
rgb_bitdist| 2| 100000| 100|0.58916697| PASSED
rgb_bitdist| 3| 100000| 100|0.65855068| PASSED
rgb_bitdist| 4| 100000| 100|0.98371981| PASSED
rgb_bitdist| 5| 100000| 100|0.32509053| PASSED
rgb_bitdist| 6| 100000| 100|0.41816883| PASSED
rgb_bitdist| 7| 100000| 100|0.13625306| PASSED
rgb_bitdist| 8| 100000| 100|0.98116523| PASSED
rgb_bitdist| 9| 100000| 100|0.09052981| PASSED
rgb_bitdist| 10| 100000| 100|0.71922521| PASSED
rgb_bitdist| 11| 100000| 100|0.39864600| PASSED
rgb_bitdist| 12| 100000| 100|0.88463093| PASSED
rgb_minimum_distance| 2| 10000| 1000|0.49191929| PASSED
rgb_minimum_distance| 3| 10000| 1000|0.34086770| PASSED
rgb_minimum_distance| 4| 10000| 1000|0.67634721| PASSED
rgb_minimum_distance| 5| 10000| 1000|0.90504426| PASSED
rgb_permutations| 2| 100000| 100|0.53206606| PASSED
rgb_permutations| 3| 100000| 100|0.93990686| PASSED
rgb_permutations| 4| 100000| 100|0.93641573| PASSED
rgb_permutations| 5| 100000| 100|0.33006306| PASSED
rgb_lagged_sum| 0| 1000000| 100|0.78918620| PASSED
rgb_lagged_sum| 1| 1000000| 100|0.49537040| PASSED
rgb_lagged_sum| 2| 1000000| 100|0.84078182| PASSED
rgb_lagged_sum| 3| 1000000| 100|0.08149632| PASSED
rgb_lagged_sum| 4| 1000000| 100|0.53883616| PASSED
rgb_lagged_sum| 5| 1000000| 100|0.18996191| PASSED
rgb_lagged_sum| 6| 1000000| 100|0.97313817| PASSED
rgb_lagged_sum| 7| 1000000| 100|0.43472782| PASSED
rgb_lagged_sum| 8| 1000000| 100|0.32097682| PASSED
rgb_lagged_sum| 9| 1000000| 100|0.34552567| PASSED
rgb_lagged_sum| 10| 1000000| 100|0.80184011| PASSED
rgb_lagged_sum| 11| 1000000| 100|0.21385126| PASSED
rgb_lagged_sum| 12| 1000000| 100|0.41010174| PASSED
rgb_lagged_sum| 13| 1000000| 100|0.92351903| PASSED
rgb_lagged_sum| 14| 1000000| 100|0.97133192| PASSED
rgb_lagged_sum| 15| 1000000| 100|0.72265136| PASSED
rgb_lagged_sum| 16| 1000000| 100|0.27598576| PASSED
rgb_lagged_sum| 17| 1000000| 100|0.80165934| PASSED
rgb_lagged_sum| 18| 1000000| 100|0.53501980| PASSED
rgb_lagged_sum| 19| 1000000| 100|0.16149694| PASSED
rgb_lagged_sum| 20| 1000000| 100|0.62232179| PASSED
rgb_lagged_sum| 21| 1000000| 100|0.63703547| PASSED
rgb_lagged_sum| 22| 1000000| 100|0.74027501| PASSED
rgb_lagged_sum| 23| 1000000| 100|0.48693243| PASSED
rgb_lagged_sum| 24| 1000000| 100|0.52278818| PASSED
rgb_lagged_sum| 25| 1000000| 100|0.37765179| PASSED
rgb_lagged_sum| 26| 1000000| 100|0.17398545| PASSED
rgb_lagged_sum| 27| 1000000| 100|0.91595733| PASSED
rgb_lagged_sum| 28| 1000000| 100|0.21368217| PASSED
rgb_lagged_sum| 29| 1000000| 100|0.15273232| PASSED
rgb_lagged_sum| 30| 1000000| 100|0.04442107| PASSED
rgb_lagged_sum| 31| 1000000| 100|0.43887837| PASSED
rgb_lagged_sum| 32| 1000000| 100|0.35777050| PASSED
rgb_kstest_test| 32| 10000| 1000|0.41686471| PASSED
So I don't think is just random stuff (pun intended
) and if Heinz would like to add some comments he can for sure explain better then me.
Re: RKISS
Posted: Mon Jan 17, 2011 2:50 pm
by Don
I don't see any reference to RKISS on the web. I see lots of references to Marsaglia and KISS in general, but not specifically RKISS.
Who is Heinz van Saanen? I also question whether it's possible to copyright 3 or 4 lines of code that is based on well known heuristics.
I took a look at the generator and unless I missed something it is intialized in a completely deterministic way. I did not look to see how it's used in stockfish so perhaps this is what is intended. But if were used for getting a book move it will always play the same book move after the program is initialized.
Code: Select all
void raninit() {
s.a = 0xf1ea5eed;
s.b = s.c = s.d = 0xd4e12c77;
for (int i = 0; i < 73; i++)
rand64();
}
This just doesn't seem right to me. Instead of looping 73 times it would be more efficient to just set the 4 variables ONE time to the values they are guaranteed to take anyway? Of course I assume that is done only once but I don't see the point of it.
mcostalba wrote:Gerd Isenberg wrote:
Is there any theory about that bit-twiddling available on-line? Or is such stuff more empirical trial and error?
This code was kindly donated to us by Heinz van Saanen that allowed us to license under GPL so to be merged in SF.
We just tested that it works and is 100% an alternative to mersenne.
I don't think it is just trial and error, as reported in the header:
Code: Select all
** A small "keep it simple and stupid" RNG with some fancy merits:
**
** Quite platform independent
** Passes ALL dieharder tests! Here *nix sys-rand() e.g. fails miserably:-)
** ~12 times faster than my *nix sys-rand()
** ~4 times faster than SSE2-version of Mersenne twister
** Average cycle length: ~2^126
** 64 bit seed
** Return doubles with a full 53 bit mantissa
** Thread safe
And here is the dieharder tests reports:
Code: Select all
heinz@linux:~/junk/junk> ./a.out | dieharder -g 200 -a
#=============================================================================#
# dieharder version 3.29.4beta Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name |rands/second| Seed |
stdin_input_raw| 2.13e+07 |4282743765|
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.14890455| PASSED
diehard_operm5| 5| 1000000| 100|0.02837678| PASSED
diehard_rank_32x32| 0| 40000| 100|0.63612384| PASSED
diehard_rank_6x8| 0| 100000| 100|0.78258674| PASSED
diehard_bitstream| 0| 2097152| 100|0.73291748| PASSED
diehard_opso| 0| 2097152| 100|0.36677569| PASSED
diehard_oqso| 0| 2097152| 100|0.35635353| PASSED
diehard_dna| 0| 2097152| 100|0.40227206| PASSED
diehard_count_1s_str| 0| 256000| 100|0.15631848| PASSED
diehard_count_1s_byt| 0| 256000| 100|0.02576356| PASSED
diehard_parking_lot| 0| 12000| 100|0.33868706| PASSED
diehard_2dsphere| 2| 8000| 100|0.61107903| PASSED
diehard_3dsphere| 3| 4000| 100|0.37099325| PASSED
diehard_squeeze| 0| 100000| 100|0.56722772| PASSED
diehard_sums| 0| 100| 100|0.04022953| PASSED
diehard_runs| 0| 100000| 100|0.39906252| PASSED
diehard_runs| 0| 100000| 100|0.26776626| PASSED
diehard_craps| 0| 200000| 100|0.74060276| PASSED
diehard_craps| 0| 200000| 100|0.43273086| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.38433496| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.21739434| PASSED
sts_monobit| 1| 100000| 100|0.13931802| PASSED
sts_runs| 2| 100000| 100|0.51329448| PASSED
sts_serial| 1| 100000| 100|0.39968488| PASSED
sts_serial| 2| 100000| 100|0.20801423| PASSED
sts_serial| 3| 100000| 100|0.22648504| PASSED
sts_serial| 3| 100000| 100|0.79553793| PASSED
sts_serial| 4| 100000| 100|0.13889241| PASSED
sts_serial| 4| 100000| 100|0.35689448| PASSED
sts_serial| 5| 100000| 100|0.32907831| PASSED
sts_serial| 5| 100000| 100|0.96425371| PASSED
sts_serial| 6| 100000| 100|0.29429007| PASSED
sts_serial| 6| 100000| 100|0.67547393| PASSED
sts_serial| 7| 100000| 100|0.27652533| PASSED
sts_serial| 7| 100000| 100|0.43773829| PASSED
sts_serial| 8| 100000| 100|0.00589920| PASSED
sts_serial| 8| 100000| 100|0.00606073| PASSED
sts_serial| 9| 100000| 100|0.36759888| PASSED
sts_serial| 9| 100000| 100|0.41487400| PASSED
sts_serial| 10| 100000| 100|0.85082078| PASSED
sts_serial| 10| 100000| 100|0.25805178| PASSED
sts_serial| 11| 100000| 100|0.52837124| PASSED
sts_serial| 11| 100000| 100|0.05334055| PASSED
sts_serial| 12| 100000| 100|0.67688469| PASSED
sts_serial| 12| 100000| 100|0.84215568| PASSED
sts_serial| 13| 100000| 100|0.99153787| PASSED
sts_serial| 13| 100000| 100|0.76515469| PASSED
sts_serial| 14| 100000| 100|0.26573843| PASSED
sts_serial| 14| 100000| 100|0.26842956| PASSED
sts_serial| 15| 100000| 100|0.45104274| PASSED
sts_serial| 15| 100000| 100|0.40600808| PASSED
sts_serial| 16| 100000| 100|0.50489227| PASSED
sts_serial| 16| 100000| 100|0.65051872| PASSED
rgb_bitdist| 1| 100000| 100|0.90681142| PASSED
rgb_bitdist| 2| 100000| 100|0.58916697| PASSED
rgb_bitdist| 3| 100000| 100|0.65855068| PASSED
rgb_bitdist| 4| 100000| 100|0.98371981| PASSED
rgb_bitdist| 5| 100000| 100|0.32509053| PASSED
rgb_bitdist| 6| 100000| 100|0.41816883| PASSED
rgb_bitdist| 7| 100000| 100|0.13625306| PASSED
rgb_bitdist| 8| 100000| 100|0.98116523| PASSED
rgb_bitdist| 9| 100000| 100|0.09052981| PASSED
rgb_bitdist| 10| 100000| 100|0.71922521| PASSED
rgb_bitdist| 11| 100000| 100|0.39864600| PASSED
rgb_bitdist| 12| 100000| 100|0.88463093| PASSED
rgb_minimum_distance| 2| 10000| 1000|0.49191929| PASSED
rgb_minimum_distance| 3| 10000| 1000|0.34086770| PASSED
rgb_minimum_distance| 4| 10000| 1000|0.67634721| PASSED
rgb_minimum_distance| 5| 10000| 1000|0.90504426| PASSED
rgb_permutations| 2| 100000| 100|0.53206606| PASSED
rgb_permutations| 3| 100000| 100|0.93990686| PASSED
rgb_permutations| 4| 100000| 100|0.93641573| PASSED
rgb_permutations| 5| 100000| 100|0.33006306| PASSED
rgb_lagged_sum| 0| 1000000| 100|0.78918620| PASSED
rgb_lagged_sum| 1| 1000000| 100|0.49537040| PASSED
rgb_lagged_sum| 2| 1000000| 100|0.84078182| PASSED
rgb_lagged_sum| 3| 1000000| 100|0.08149632| PASSED
rgb_lagged_sum| 4| 1000000| 100|0.53883616| PASSED
rgb_lagged_sum| 5| 1000000| 100|0.18996191| PASSED
rgb_lagged_sum| 6| 1000000| 100|0.97313817| PASSED
rgb_lagged_sum| 7| 1000000| 100|0.43472782| PASSED
rgb_lagged_sum| 8| 1000000| 100|0.32097682| PASSED
rgb_lagged_sum| 9| 1000000| 100|0.34552567| PASSED
rgb_lagged_sum| 10| 1000000| 100|0.80184011| PASSED
rgb_lagged_sum| 11| 1000000| 100|0.21385126| PASSED
rgb_lagged_sum| 12| 1000000| 100|0.41010174| PASSED
rgb_lagged_sum| 13| 1000000| 100|0.92351903| PASSED
rgb_lagged_sum| 14| 1000000| 100|0.97133192| PASSED
rgb_lagged_sum| 15| 1000000| 100|0.72265136| PASSED
rgb_lagged_sum| 16| 1000000| 100|0.27598576| PASSED
rgb_lagged_sum| 17| 1000000| 100|0.80165934| PASSED
rgb_lagged_sum| 18| 1000000| 100|0.53501980| PASSED
rgb_lagged_sum| 19| 1000000| 100|0.16149694| PASSED
rgb_lagged_sum| 20| 1000000| 100|0.62232179| PASSED
rgb_lagged_sum| 21| 1000000| 100|0.63703547| PASSED
rgb_lagged_sum| 22| 1000000| 100|0.74027501| PASSED
rgb_lagged_sum| 23| 1000000| 100|0.48693243| PASSED
rgb_lagged_sum| 24| 1000000| 100|0.52278818| PASSED
rgb_lagged_sum| 25| 1000000| 100|0.37765179| PASSED
rgb_lagged_sum| 26| 1000000| 100|0.17398545| PASSED
rgb_lagged_sum| 27| 1000000| 100|0.91595733| PASSED
rgb_lagged_sum| 28| 1000000| 100|0.21368217| PASSED
rgb_lagged_sum| 29| 1000000| 100|0.15273232| PASSED
rgb_lagged_sum| 30| 1000000| 100|0.04442107| PASSED
rgb_lagged_sum| 31| 1000000| 100|0.43887837| PASSED
rgb_lagged_sum| 32| 1000000| 100|0.35777050| PASSED
rgb_kstest_test| 32| 10000| 1000|0.41686471| PASSED
So I don't think is just random stuff (pun intended
) and if Heinz would like to add some comments he can for sure explain better then me.
Re: RKISS
Posted: Mon Jan 17, 2011 3:27 pm
by UncombedCoconut
Don wrote:I don't see any reference to RKISS on the web. I see lots of references to Marsaglia and KISS in general, but not specifically RKISS.
My experience is about the same; Googling, say, the coefficients doesn't find that exact RNG. (Googling the author does give lots of hits, however.
He's credited in bitboard.cpp as well, so I guess the SF team knows him.)
I took a look at the generator and unless I missed something it is intialized in a completely deterministic way. I did not look to see how it's used in stockfish so perhaps this is what is intended. But if were used for getting a book move it will always play the same book move after the program is initialized.
That part's OK; the Book::Book() constructor calls the RNG a system-time-dependent number of times. I agree the initial fixed loop is a little strange.
Re: RKISS
Posted: Mon Jan 17, 2011 3:49 pm
by bob
The PRNG I use (from the book "Numerical Recpies") uses an array of numbers that get twisted in odd ways. But a PRNG is _supposed_ to produce the same string of numbers each time it is initialized.
The easiest way to select random book moves is to use the PRNG to initialize everything, then obtain the system time in microseconds or something that is high-resolution, extract the rightmost N bits, and loop calling the PRNG that many times before you start to play the game. Then you start the same PRNG sequence as the PRNG is supposed to deliver, but you skip N numbers before using them for book.
These types of PRNGs are harder to "seed", although one can (in the PRNG I use) alter the initial values of the two array indices, which will certainly change the sequence. But the released version has been tested quite thoroughly, and such a change might easily shorten the PRNG period or randomness, which is undesirable.
Re: RKISS
Posted: Mon Jan 17, 2011 4:01 pm
by Don
UncombedCoconut wrote:Don wrote:I don't see any reference to RKISS on the web. I see lots of references to Marsaglia and KISS in general, but not specifically RKISS.
My experience is about the same; Googling, say, the coefficients doesn't find that exact RNG. (Googling the author does give lots of hits, however.
He's credited in bitboard.cpp as well, so I guess the SF team knows him.)
I took a look at the generator and unless I missed something it is intialized in a completely deterministic way. I did not look to see how it's used in stockfish so perhaps this is what is intended. But if were used for getting a book move it will always play the same book move after the program is initialized.
That part's OK; the Book::Book() constructor calls the RNG a system-time-dependent number of times. I agree the initial fixed loop is a little strange.
I guess it works, but it seems like a very ugly hack. Is the point that the RNG cannot be initialized with just any constant?
The proper initialization should be inside the class, not outside of it. Even if all it does is to make a zillion calls of the RNG the ugliness could be isolated inside the class.
Anyway, I'm just nit-picking - I have uglier things in my own code.
Don
Re: RKISS
Posted: Mon Jan 17, 2011 4:17 pm
by UncombedCoconut
Don wrote:I guess it works, but it seems like a very ugly hack. Is the point that the RNG cannot be initialized with just any constant?
As Bob points out, fiddling with the initial internal state can turn a well-tested RNG into an untested RNG. Time-shifting its output sequence cannot. So the "roll a zillion dice" idea is at least a good convention.
The proper initialization should be inside the class, not outside of it. Even if all it does is to make a zillion calls of the RNG the ugliness could be isolated inside the class.
Stockfish uses this RNG twice: once to pick openings (should be random), once to pick Zobrist keys (should "look random" but be the same every time). How best to achieve this is a matter of taste, but I don't think SF's is bad. Even pre-computing the effect of raninit() (an idea I like) is roughly a break-even in terms of code beauty.
Re: RKISS
Posted: Mon Jan 17, 2011 4:36 pm
by Don
bob wrote:The PRNG I use (from the book "Numerical Recpies") uses an array of numbers that get twisted in odd ways. But a PRNG is _supposed_ to produce the same string of numbers each time it is initialized.
The easiest way to select random book moves is to use the PRNG to initialize everything, then obtain the system time in microseconds or something that is high-resolution, extract the rightmost N bits, and loop calling the PRNG that many times before you start to play the game. Then you start the same PRNG sequence as the PRNG is supposed to deliver, but you skip N numbers before using them for book.
That seems incredible inefficient if you want to have more than a few possible seed states but if your software only initializes the RNG once at program startup (which most but not all software needs to do) and speed is not an issue, you could probably still have at least a few thousands states without increasing startup time by more than a fraction of a second.
For selecting opening book moves only, this is not an issue of course. But it makes the generator impractical as a general purpose RNG.
It makes me wonder even more how a few lines of code like this can be copyrighted, when it's not even a very usable general purpose RNG if it cannot be initialized in constant time and it can only be initialized to a point very close to the beginning of it's enormous period length. O(n) puts a severe limit on the number of practical starting states you can have and it's not even distributed over the entire sequence or period of the generator!
In any application requiring a significant number of RNG calls it's going to always visit the same sequences once you are beyond first few thousand that you initialized it with. Here is an example:
Suppose I wanted to simulate 100 billion dice throws and I use the slow O(n) initializer to provide 1 million starting states. No matter how many times I run the simulation, I'm STILL going to generate almost the same results - the only difference being the tiny fraction of differences caused by where I start and end in the sequence.
Anyway, don't get me wrong - I'm not being critical, now that I understand it I can see that it's practical and fine for what it's being used for.
These types of PRNGs are harder to "seed", although one can (in the PRNG I use) alter the initial values of the two array indices, which will certainly change the sequence. But the released version has been tested quite thoroughly, and such a change might easily shorten the PRNG period or randomness, which is undesirable.
Re: RKISS
Posted: Mon Jan 17, 2011 4:44 pm
by mcostalba
UncombedCoconut wrote: Even pre-computing the effect of raninit() (an idea I like) is roughly a break-even in terms of code beauty.
I agree, because you break the symmetry:
A code beautification could be instead:
but, as reported above you get un untested PRNG instead of a well tested and proved one.