Shop OBEX P1 Docs P2 Docs Learn Events
Random/LFSR on P2 - Page 80 — Parallax Forums

Random/LFSR on P2

1777880828392

Comments

  • TonyB_TonyB_ Posts: 2,190
    edited 2020-01-10 11:12
    I am glad you got it working to see what I was seeing.
    I was up till 4AM testing variations on this, but there is no simple way I can find that will get around the lsb issue (which likely is what also maintains the structural coherency).

    I've been looking at the final pfreq distribution and ignoring individual pair outputs. Just to clarify, the lsb issue is that the xored bit has lower quality than if no xor?

    Another issue for me with xoring the high word is that the low and high words are treated differently, with only the latter modified within the same pair. I think it might be better to xor the low word instead, but my current preference is adding 1 to the low word so that both words are one more than they would have been otherwise.

    The jump action then becomes clearer: rather than jumping after every double-iteration period, the jumping occurs after every double-iteration, thus the streams are interleaved not sequential. It is jumping that produces 2D equidistribution. (This will be obvious to you and is intended mainly for others who might be interested.)
    'xoroacc operation
    'result_out[15:0]  := prn[15:0]  + result_in[31:16] + 1
    'result_out[31:16] := prn[31:16] + result_out[15:0]
    
  • TonyB_TonyB_ Posts: 2,190
    edited 2020-01-13 14:14
    Code for testing:
    'XOROACC instruction pseudo-code:
    'result_out[15:0]  := result_in[31:16] + prn[15:0] + 1
    'result_out[31:16] := result_out[15:0] + prn[31:16]
    
    'P2 code equivalent
    'result[31:16] = current result word, result[15:0] = previous result word
    
    	xoro32	state			'update state, PRN in next S
    	mov	prn,0			'prn = XORO32 PRN
    	getword	tmp,prn,#0		'tmp = prn[15:0]
    	add	tmp,#1			'tmp = prn[15:0]+1
    	shl	tmp,#16			'tmp = {prn[15:0]+1,16'b0}
    	add	result,tmp		'result = {result[31:16]+prn[15:0]+1,16'bX}
    	movbyts	result,#%%3232		'result = {result[31:16]+prn[15:0]+1,
    					'result[31:16]+prn[15:0]+1}
    	setword	prn,tmp,#0		'prn = {prn[31:16],16'b0}
    	add	result,prn		'result = {result[31:16]+prn[15:0]+1+prn[31:16],
    					'result[31:16]+prn[15:0]+1}	
    state	long	1
    prn	long	0
    result	long	0
    tmp	long	0
    
    'In future hardware, the above code could be replaced by
    
    	xoro32	state
    	xoroacc	result,0		'preserve result[31:16] for next xoroacc
    	
    state	long	1
    result	long	0
    
  • TonyB_ wrote: »
    I've been looking at the final pfreq distribution and ignoring individual pair outputs. Just to clarify, the lsb issue is that the xored bit has lower quality than if no xor?
    No, the lsb is the only bit still tied entirely to the underlying xoroshiro++, which has a period of 2^32-1. Modulating that bit with xor in the described fashion should double the period, but not in a way that will subtantially affect randomness tests related to that bit.[/quote]
    TonyB_ wrote: »
    Another issue for me with xoring the high word is that the low and high words are treated differently, with only the latter modified within the same pair. I think it might be better to xor the low word instead, but my current preference is adding 1 to the low word so that both words are one more than they would have been otherwise.
    It is fine to modify the low word (instead of the high), but my testing has indicated that adding 1 (instead of xor) propagates in a way that exactly repeats every other word in the other half of the next stream. I will post my exact findings shortly.
  • TonyB_TonyB_ Posts: 2,190
    edited 2019-10-23 22:29
    TonyB_ wrote: »
    Another issue for me with xoring the high word is that the low and high words are treated differently, with only the latter modified within the same pair. I think it might be better to xor the low word instead, but my current preference is adding 1 to the low word so that both words are one more than they would have been otherwise.
    It is fine to modify the low word (instead of the high), but my testing has indicated that adding 1 (instead of xor) propagates in a way that exactly repeats every other word in the other half of the next stream. I will post my exact findings shortly.

    I prefer modifying the low word and I find it easier to visualize what is happening with +1, but if ^1 is better then no problem as changes to software or hardware are trivial. As mentioned, I haven't been studying pair values to spot undesirable patterns.
  • TonyB_TonyB_ Posts: 2,190
    edited 2019-10-24 00:34
    First few outputs for xoroshiro32++a[13,5,10,9]
    Initial state = 1, initial acc = 0
    +1 or ^1 applied to low word of acc
    
    Double-
    Iteration	State		PRN		Acc +1
    
     1 		84908405	62690201	646B0202
     2 		DFDA9401	12A2AE16	25241282
     3 		51BCEDD3	D7194AE8	4726700D
     4 		13CB03C2	984B0C52	EBC45379
     5 		45D4FD1B	743C1DF1	7DF209B6
     6 		BF81765E	BCC6DBA0	16595993
     7 		4D0FBE2D	746C34C9	BF8F4B23
     8 		AEAD221F	07FF3643	FDD2F5D3
     9 		0CD29B35	C642BBC0	7FD5B993
     10 		F918BAF2	594EAA85	83A92A5B
     11 		EF0352A5	701AD05A	C41E5404
     12 		10E75522	F3AEA328	5AF56747
     13 		5A8BCEEE	695A67EE	2C3EC2E4
     14 		255DA64A	93C6C140	8145ED7F
     15 		CBAC5BD5	4964F5E1	C08B7727
     16 		8B49F8A6	FC575E24	1B071EB0
    
    
    Double-
    Iteration	State		PRN		Acc ^1
    
     1 		84908405	62690201	64690200
     2 		DFDA9401	12A2AE16	25221280
     3 		51BCEDD3	D7194AE8	4724700B
     4 		13CB03C2	984B0C52	EBC25377
     5 		45D4FD1B	743C1DF1	7DEE09B2
     6 		BF81765E	BCC6DBA0	1655598F
     7 		4D0FBE2D	746C34C9	BF894B1D
     8 		AEAD221F	07FF3643	FDCAF5CB
     9 		0CD29B35	C642BBC0	7FCDB98B
     10 		F918BAF2	594EAA85	839F2A51
     11 		EF0352A5	701AD05A	C41453FA
     12 		10E75522	F3AEA328	5AEB673D
     13 		5A8BCEEE	695A67EE	2C34C2DA
     14 		255DA64A	93C6C140	813BED75
     15 		CBAC5BD5	4964F5E1	C07F771B
     16 		8B49F8A6	FC575E24	1AFB1EA4
    
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-24 14:30
    Just to back up a step and 'explore undesirable patterns', I want to illustrate some of the variants output from the small version. The data makes the case for xor... and further for using odd value > 1.
    Single-iterated streams of 65535 Bytes (small version xoroshiro[3,7,4,4] variants, seeds s0=0,s1=1,accH/L=0[b], first four bytes of each stream shown.[/b])
    Xoroshiro16++ (non-extended, no acc)
    First :  	10	9A	80	AE 
    Second:  	10	9A	80	AE 'repeats all bytes of previous and next stream
    Third :  	10	9A	80	AE
    Fourth:  	10	9A	80	AE
    ...
    3 Last: 	10	9A	80	AE
    2 Last: 	10	9A	80	AE
    Last  :  	10	9A	80	AE
    First :  	10	9A	80	AE
    
    Xoroshiro16++a +1L/+1H (original extended, w/acc)
    First :  	11	AC	2D	DC
    Second:  	10	AB	2C	DB 'correlated to previous and next stream
    Third :  	F	AA	2B	DA
    Fourth:  	E	A9	2A	D9
    ...
    3 Last: 	14	AF	30	DF
    2 Last: 	13	AE	2F	DE
    Last  :  	12	AD	2E	DD
    First :  	11	AC	2D	DC
    
    Xoroshiro16++a +1L/+0H (half-adding)
    First :  	11	AB	2C	DA
    Second:  	10	AB	2B	DA 'correlated and repeat
    Third :  	10	AA	2B	D9
    Fourth:  	F	AA	2A	D9
    ...
    3 Last: 	12	AD	2D	DC
    2 Last: 	12	AC	2D	DB
    Last  :  	11	AC	2C	DB
    First :  	11	AB	2C	DA
    
    Xoroshiro16++a ^1L/^0H (half-xoring)
    First :  	11	AB	2C	DA
    Second:  	C2	5D	DD	8C 'not obviously correlated to previous stream
    Third :  	10	AA	2B	D9 'correlated to first stream
    Fourth:  	C1	5C	DC	8B 'correlated to second stream
    ...
    3 Last: 	C4	5F	DF	8E
    2 Last: 	12	AC	2D	DB
    Last  :  	C3	5E	DE	8D
    First :  	11	AB	2C	DA
    
    Xoroshiro16++a +0x73L/+0H (half-adding >1 odd value)
    First :  	83	1D	10	BE
    Second:  	10	1D	9D	BE 'every output correlated to either previous or next stream
    Third :  	10	AA	9D	4B
    Fourth:  	9D	AA	2A	4B
    ...
    3 Last: 	F6	3	83	A4
    2 Last: 	F6	90	83	31
    Last  :  	83	90	10	31
    First :  	83	1D	10	BE
    
    Xoroshiro16++a ^0x73L/^0H (half-xoring >1 odd value)
    First :  	63	FD	F0	9E
    Second:  	3E	27	A7	84 'no obvious visual correlation to previous or next stream
    Third :  	F0	8A	7D	2B 
    Fourth:  	CB	B4	34	11
    ...
    3 Last: 	24	D	8D	6A
    2 Last: 	D6	70	63	11
    Last  :  	B1	9A	1A	F7
    First :  	63	FD	F0	9E
    
    If you can replicate the last one (xor of low half with 115 decimal / 0x73 hex) from what I have provided, I think it speaks for itself. Edit: Likely not necessary, as I verified exactly against your full-size output.

    All but the first two examples have the following remarkable distribution properties:
    1D-8  : 131070 : 256	131070 : 256 'all 256 byte values occur 131070 times
    1D-16 : 255 : 256	256 : 65280  '256 word values occur 255 times and 65280 word values occur 256 times
    2D-8  : 511 : 512	512 : 65024  '512 pairs of byte values occur 511 times and 65024 pairs of byte values occur 512 times
    

    Edit: Various changes for correctness and clarity.
  • TonyB_ wrote: »
    First few outputs for xoroshiro32++a[13,5,10,9]
    Initial state = 1, initial acc = 0
    +1 or ^1 applied to low word of acc
    My results exactly agree with yours... outstanding!
  • Abreviated PractRand results for xor 0x27D3 (an arbitrary odd number).

    Forward:
    rng=RNG_stdin, seed=unknown
    length= 16 gigabytes (2^34 bytes), time= 598 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low1/16]FPF-14+6/4:all           R=  -5.3  p =1-1.0e-4   unusual
      [Low1/16]Gap-16:A                 R= +69.9  p =  6.3e-61    FAIL !!!!
      [Low1/16]Gap-16:B                 R= +43.9  p =  1.7e-37    FAIL !!!
      [Low4/16]FPF-14+6/4:all           R=  -9.5  p =1-7.5e-9   very suspicious
      ...and 1636 test result(s) without anomalies
    
    Similar forward failures as compared to xor 1.

    Reverse (16-bits at a time):
    rng=RNG_stdin, seed=unknown
    length= 32 gigabytes (2^35 bytes), time= 967 seconds
      Test Name                         Raw       Processed     Evaluation
      Gap-16:A                          R=+553.9  p =  7.1e-366   FAIL !!!!!!!
      Gap-16:B                          R=+258.8  p =  3.2e-221   FAIL !!!!!!
      ...and 1716 test result(s) without anomalies
    
    The reverse failures are remarkably fewer as compared to xor 1 (which logged nearly 150 failures at 32GB).
  • TonyB_TonyB_ Posts: 2,190
    edited 2019-10-25 18:20
    Abbreviated PractRand results for xor 0x27D3 (an arbitrary odd number)...
    Thanks for the results.

    Inverting about half the bits of prn before the low accumulation looks optimal, based on nothing more than a gut feeling, and nine seems better than eight for a 16-bit output, which is true for 27D3h = 0010011111010011b. It does have a run of five 1s and is not prime, though.

    Are a few more PractRand tests worth doing?

    5E2Dh = 24109d = 0101111000101101b is prime, has nine 1s with a longest run of four and is very close to 65536 * 1/e (the expected number of 16-bit outputs that occur once or never for a random generator with period 2^16-1). A couple of other, more control-type xor values are 00FFh and 5555h.
    TonyB_ wrote: »
    First few outputs for xoroshiro32++a[13,5,10,9]
    Initial state = 1, initial acc = 0
    +1 or ^1 applied to low word of acc
    My results exactly agree with yours... outstanding!
    I used QuickBASIC, not the P2 code I posted!

    I intend to check xoroshiro16++a with xor value of 115d, on Friday with luck.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-25 16:58
    TonyB_ wrote: »
    Are a few more PractRand tests worth doing?

    5E2Dh = 24109d = 0101111000101101b is prime, has nine 1s with a longest run of four and is very close to 65536 * 1/e (the expected number of 16-bit outputs that occur once or never for a random generator with period 2^16-1). A couple of other, more control-type xor values are 00FFh and 5555h.
    I did some preliminary tests on those values (00FFh is comparatively horrible, BTW), and several things occurred to me while looking at the results:
    1. The low nibble of the xor value drives the forward failures, with perhaps 3 or 5 being optimal.
    2. Perhaps need to use a better seed set (i.e. I suspect than 1/0/0 is not representative enough).
    3. Should force-test forward up to 32GB, and reverse up to 64G, in order to provide more data points.
  • TonyB_TonyB_ Posts: 2,190
    edited 2019-10-26 17:04
    I recorded the first eight acc pair outputs at the start of each of the double-iteration periods or streams for xoroshiro16++a[3,7,4,4]:
    If
    i = double-iteration (0-65534)
    j = iteration period (0-255) 
    acc(i,j) = acc pair 
    x = xor value 
    then
    
    acc(i,j) - acc(i,j+1) = x * 256 + x or (x-1) * 256 + x
    

    Thus, low difference = x, high difference = x or x-1 and correlation between periods is obvious. I tested many values of x using xor and replacing it with add produced same results for the one or two I tested. initial pair values for each stream.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-26 03:53
    TonyB_ wrote: »
    Thus, low difference = x, high difference = x or x-1 and correlation between periods is obvious. I tested many values of x using xor and replacing it with add produced same results for the one or two I tested.
    The difference between +x or ^x is purely visual, regardless of whether x=1 or another odd value.
    In the the last of the example outputs I gave above:
    First :  	63	FD	F0	9E
    Second:  	3E	27	A7	84 'no obvious visual correlation to previous or next stream
    Third :  	F0	8A	7D	2B 
    Fourth:  	CB	B4	34	11
    
    ... It is clear that, for example Abs(FD-27)=Abs(8A-B4).
    The only questions are related to how desirable it is to have the correlation appear less obvious, and will it affect statistical use case scenarios?
    If the answer to either is 'yes', then xor seems to be the better choice.
    For example, is a single or double stream actually more random, since the flipped bits produce new carries into ACC?
    The answer seems to be 'yes' when looking at forward PractRand results at the 8GB mark where the xor >1 seems to help completion of the single stream without any suspicious results.
    However, my original statement on values >1 still partially stands (though could be more broadly applied to using sum, as well):
    This only visually dresses the subsequent stream pairs, so I am not convinced it is worth the effort over just xor 0/1... however, it is an option to consider...
    Regarding xor values, I have attached a file of results that gives a clue about PractRand's statistical power.
    Spoiler: 0x3725h would be the best constant I have tried (found by using an iterative technique to converge on a seemingly good value).
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-27 00:44
    For example, is a single or double stream actually more random, since the flipped bits produce new carries into ACC?
    The answer seems to be 'yes' when looking at forward PractRand results at the 8GB mark where the xor >1 seems to help completion of the single stream without any suspicious results.
    I've attached the full set of 16-bit rotations for xor 3725h, which sets the bar for 8GB performance (the point at which all subsequent output is provably correlated to previous output), which can be compared to previous results.
    I am using the arbitrary seeds (s0 = B49Fh, s1 = 888Eh, acc = 945Bh) for this and re-runs on +1 and ^1, which I will add here and summarize, for comparison.

    Tony, given everything we have looked at, let me know which additional data / summaries / BigCrush results, etc. that you need on any specific + or xor constants.

    Added more variants using above seeds.
  • TonyB_TonyB_ Posts: 2,190
    edited 2019-10-26 18:05
    For example, is a single or double stream actually more random, since the flipped bits produce new carries into ACC?
    The answer seems to be 'yes' when looking at forward PractRand results at the 8GB mark where the xor >1 seems to help completion of the single stream without any suspicious results.
    I've attached the full set of 16-bit rotations for xor 3725h, which sets the bar for 8GB performance (the point at which all subsequent output is provably correlated to previous output), which can be compared to previous results.
    I am using the arbitrary seeds (s0 = B49Fh, s1 = 888Eh, acc = 945Bh) for this and re-runs on +1 and ^1, which I will add here and summarize, for comparison.

    Tony, given everything we have looked at, let me know which additional data / summaries / BigCrush results, etc. that you need on any specific + or xor constants.

    Chris, thanks for the PractRand results.

    I can't replicate your outputs for xoroshiro16++a when xoring 73h and I see the same correlation between every adjacent stream, for 73h or any other value I tested.

    In the P2 hardware, there is enough time for only two cascaded 16-bit additions, where the result from the first adder is used in the second. +1 could be done by add with carry then add, but adding large(r) values would take too long. In contrast, xoring means just inverting some of the first adder inputs and any value would work.

    It is clear that +1 or ^1 are enough to hide the 1D equidistribution from PractRand so we get maximum scores, which we never achieved with xoroshiro32++. In theory, all the failures should be 16GB and I'm not sure why some are 32GB.

    Adjacent streams that differ by more than 1 make me feel better, even though they are just as correlated. I suggest BigCrush testing with +1 (but no more +), ^1, ^5E2Dh and other ^ you feel are worthwhile. That should be enough to finish ++a.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-26 20:30
    TonyB_ wrote: »
    I can't replicate your outputs for xoroshiro16++a when xoring 73h...
    I think we should be able to agree on this... note my inadvertent non-standard seeding (s0=0,s1=1,acc=0), and post your first several outputs from the first two streams of xor 1 and xor 73h.
    TonyB_ wrote: »
    ... In theory, all the failures should be 16GB and I'm not sure why some are 32GB.
    I believe PractRand is only fully able to consider the weak lsb in isolation on the forward non-rotated test, and has insufficient tests / statistical power to find the obvious issue on other variations (reverse and/or non-zero rotations).
    That is part of the reason why I consider the 8GB passing results for all variants on fwd/rev and rotations so important as a catch-all for pushing forward to BigCrush (which must find at least some issue(s) with any given variant, I presume).
    TonyB_ wrote: »
    Adjacent streams that differ by more than 1 make me feel better, even though they are just as correlated. I suggest BigCrush testing with +1 (but no more +), ^1, ^5E2Dh and other ^ you feel are worthwhile. That should be enough to finish ++a.
    I agree... will do.
  • TonyB_ wrote: »
    I can't replicate your outputs for xoroshiro16++a when xoring 73h...
    I think we should be able to agree on this... note my inadvertent non-standard seeding (s0=0,s1=1,acc=0), and post your first several outputs from the first two streams of xor 1 and xor 73h.

    I didn't notice s0 & s1 were swapped from the usual seed of 1. Also, my x86 code was calculating PRN after the state iteration. Both now fixed, I can match your data and see the problem. The period is 65535 * 2 as we are dealing with pairs and the start of your third stream is actually start of the second.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-27 03:01
    I have added various attachments to the post several back: forums.parallax.com/discussion/comment/1480581/#Comment_1480581.
    TonyB_ wrote: »
    I didn't notice s0 & s1 were swapped from the usual seed of 1. Also, my x86 code was calculating PRN after the state iteration. Both now fixed, I can match your data and see the problem. The period is 65535 * 2 as we are dealing with pairs and the start of your third stream is actually start of the second.
    Correct, the stream orientation was for comparison forward from the base non-extended xoroshiro stream to illustrate the progression.

    I need to write an accurate XOROACC module for BigCrush... must be XOROACC, since the 32-bit format is required.
    Actually, the analysis is mostly 30-bit, which will certainly put an interesting spin on most of the results.
    Created and running attached '+ 1' code, following Lemire's convention for testing.
    Note: There is no mention of ++a, as the transition directly from ++ to XOROACC is cleaner to code in C, as no xor toggled state variable is required to apply e to every other ++ iteration.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-30 00:28
    TestU01 BigCrush results, w/cloud meta-analysis summary plot, are attached for 4 variants.
    Lemire's naming convention:
    -b   = Forward bits
    -r-b = Reverse bytes
    -z-b = Reverse bits
    
    Any plot result that is entirely within +/- 4 Sigma, with the vast majority of points within +/- 3 Sigma, is considered normal and acceptable...
    ^1 and +1 did not pass BigCrush, with +1 clearly being the better of the two.
    ^3725h and ^5E2Dh did pass BigCrush, with ^5E2Dh being marginally better (enough to be recommended).
  • ^1 and +1 did not pass BigCrush, with +1 clearly being the better of the two.
    ^3725h and ^5E2Dh did pass BigCrush, with ^5E2Dh being marginally better (enough to be recommended).

    Many thanks for running the BigCrush tests. The 48 logs are for 3 tests x 16 rotations? The filenames are rather cryptic. xoroshiro32++[13,5,10,9] does not pass all of BigCrush. I'm pleased that ^5E2Dh does and is the best of those tested.

    I haven't looked at '2D-8' for xoroshiro16++a yet. Another thing I'm wondering about is how many iterations must be done to output all possible acc pairs.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-10-30 22:14
    TonyB_ wrote: »
    Many thanks for running the BigCrush tests. The 48 logs are for 3 tests x 16 rotations? The filenames are rather cryptic. xoroshiro32++[13,5,10,9] does not pass all of BigCrush. I'm pleased that ^5E2Dh does and is the best of those tested.

    I haven't looked at '2D-8' for xoroshiro16++a yet. Another thing I'm wondering about is how many iterations must be done to output all possible acc pairs.
    I am very pleased also... throwing 48 bits of state at the problem would be almost a wasted effort if it could not pass BigCrush, which requires a minimum of about 35 or 36 state bits (if all bits are used optimally)..

    I ran 16 seed sets (provided by SplitMix and starting seed documented in the filename) for each of forward bits, reverse bits, and reverse bytes, in order to look for p-value bias... so no rotations.
    With about 30 of the p-values, I have applied corrections (to compensate for defects in TestU01). However, only a few of those corrections would be required when looking at only 48 BigCrush runs.
    When processed through meta-analysis (required to compete with PractRand), abnormal bias was noticed in only a few of the passing p-values, mostly when the bits were reversed.
    P-value # 50 (of 254 total) was the most notable offender, but only when bits were reversed: sknuth_CouponCollector: N=1,n=200000000,r=0,d=8

    If you feel you must steer other aspects of the distribution (without disrupting the existing equidistribution or randomness quality) and find you cannot do so when trying other odd constants, then try this:
    1. Add 1 to the second xoroshiro iteration result AND
    2. Use an even xor constant on the first xoroshiro iteration (e.g. 5E2Ch)

    I am happy to run a few more PractRand/BigCrush, if you have specific changes / constants in mind.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-11-01 20:46
    Tony, you asked "Would it be best to output acc with bits reversed?"... it did not occur to me to reverse the xoroshiro32++ result bits prior to applying the xor (on first iteration) and subsequent sum with the accumulator (on both iterations). So I ran a quick PractRand on 5E2Dh using reverse-result-bits... remember that the lsb is the master clock, and now that lsb has the highest linear complexity, so its carry is no longer discarded. Have a look at the results:
    PractRand Forward XOROACC bits:
    rng=RNG_stdin, seed=unknown
    length= 16 gigabytes (2^34 bytes), time= 572 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low1/16]Gap-16:A                 R= +68.2  p =  1.7e-59    FAIL !!!!
      [Low1/16]Gap-16:B                 R= +44.0  p =  1.4e-37    FAIL !!!
      ...and 1636 test result(s) without anomalies
    
    Practrand Reverse XOROACC bits:
    rng=RNG_stdin, seed=unknown
    length= 32 gigabytes (2^35 bytes), time= 943 seconds
      Test Name                         Raw       Processed     Evaluation
      Gap-16:A                          R=+553.3  p =  1.9e-365   FAIL !!!!!!!
      Gap-16:B                          R=+256.6  p =  2.4e-219   FAIL !!!!!!
      [Low4/16]FPF-14+6/16:all          R=  -5.4  p =1-6.9e-5   unusual
      [Low4/16]FPF-14+6/4:all           R=  -7.9  p =1-2.7e-7   suspicious
      ...and 1715 test result(s) without anomalies
    
    FPs disappeared from forward XOROACC, but popped-up on reverse XOROACC... better overall, though.

    Then I got bold and tried the same reverse-result-bits experiment, combined with using the methodology described in my previous post, with 5E2Ch (an even xor value) on the first iteration and +1 on the second iteration:
    PractRand Forward XOROACC bits:
    rng=RNG_stdin, seed=unknown
    length= 16 gigabytes (2^34 bytes), time= 581 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low1/16]Gap-16:A                 R= +68.2  p =  1.7e-59    FAIL !!!!
      [Low1/16]Gap-16:B                 R= +44.0  p =  1.4e-37    FAIL !!!
      ...and 1636 test result(s) without anomalies
    
    Practrand Reverse XOROACC bits:
    rng=RNG_stdin, seed=unknown
    length= 32 gigabytes (2^35 bytes), time= 943 seconds
      Test Name                         Raw       Processed     Evaluation
      Gap-16:A                          R=+558.7  p =  4.9e-369   FAIL !!!!!!!
      Gap-16:B                          R=+262.3  p =  3.4e-224   FAIL !!!!!!
      ...and 1715 test result(s) without anomalies
    
    Suddenly all FP issues at the failure point for the forward and reverse XOROACC bits have nearly evaporated (though one or two 'unusual' might 'randomly' pop in at ~5e-5 on either forward at 16GB or reverse at 32GB, with some initial seeds).
    This leaves only the endemic GAP issue (which likely has no simplistic solution).

    Sorry to drag this out... but often these kinds of seemingly incremental (pun not originally intended) improvements positively impact other aspects of the distribution properties that you may find desirable.
    Attached PractRand rotations and will attach BigCrush results of the latter modification that uses [reverse ++, e= ^5E2Ch, f = +1.] Edit: BigCrush results on these variants is a step backward, so will not post.
    Will do reverse ++, e= ^5E2Dh, f = 0 also... Attached, and also looks very good (e.g. the zip file is even smaller, indicating fewer total failures).
    Edited multiple times for clarity (and humorous effect).
  • xoroshironotxoroshironot Posts: 309
    edited 2019-11-02 14:58
    The above testing was a step backward based on BigCrush results, but there is one variation to try before calling ^5E2Dh,0 good enough...
    This leaves only the endemic GAP issue (which likely has no simplistic solution).
    GAP issue is deferred to > 16GB PractRand failure by:
    Accumulate forward bits of xoroshiro++ result Xor'd with 5E2Dh on first iteration (i.e. normal) and then accumulate reverse bits of xoroshiro++ result on second iteration. Same equidistribution properties.

    I will post all PractRand and BigCrush results on this variant tomorrow, then I am finally done playing with this.
    Edit: PractRand results posted... looks very good!
    Edit: BigCrush results posted... looks good, with nearly ideal failure rate (i.e. about half of all runs on a good PRNG should show 1 fail). However, meta-analysis shows p-value #50 bias is now visible in both forward and reverse bits (but not reverse bytes).
  • Accumulate forward bits of xoroshiro++ result Xor'd with 5E2Dh on first iteration (i.e. normal) and then accumulate reverse bits of xoroshiro++ result on second iteration. Same equidistribution properties.

    I will post all PractRand and BigCrush results on this variant tomorrow, then I am finally done playing with this.
    Edit: PractRand results posted... looks very good!
    Thanks for the results. They do look good, 32GB across the board.
    TonyB_ wrote: »
    Another thing I'm wondering about is how many iterations must be done to output all possible acc pairs.
    I haven't had time to look at this yet for xoroshiro16++a, perhaps over the weekend. I don't have enough RAM to test xoroshiro32++a[13,5,10,9] but is it possible that different variants might need different numbers of iterations before all 2^32 outputs occur? If so, the lower the better?
  • xoroshironotxoroshironot Posts: 309
    edited 2019-11-06 02:06
    TonyB_ wrote: »
    ... I don't have enough RAM to test xoroshiro32++a[13,5,10,9] but is it possible that different variants might need different numbers of iterations before all 2^32 outputs occur? If so, the lower the better?
    I am not sure the answer, but regarding RAM, several weeks ago I did a 32-bit distribution test that simply accumulated counts in the ranges 0x00000000-0x0000FFFF and the same range again after rotating 16 bits... I guessed that this was a good proxy for the full distribution.

    Edit: My intuition says: If 1 full stream is 2^32 double-iterations (16GB), then each stream should accomplish 50% coverage of the unsampled 32-bit values, which should deplete, on average, by the 33rd stream. Therefore, in my example above, complete coverage of 2^17 specific 32-bit values should occur in about 18 streams.
    My intuition is obviously wrong... decimation of unsampled values is by 1/e, so complete depletion should occur by about the 23rd stream, so therefore complete coverage of 2^16 specific values should occur in about 12 streams.
    I tested this logic out on the small version and it works as expected (at about 12 and 6 streams respectively, in that case).
  • xoroshironotxoroshironot Posts: 309
    edited 2019-11-04 03:44
    Attached is one final submission: e=0x5E13,f=RevBits(0). Includes PractRand rotations, BigCrush results w/meta-analysis plot. 5E13h is a prime.

    The PractRand results have no mod3n artifact at 32GB fail on Fwd00, and the BigCrush meta-analysis is the first one I have found for f=Revbits where the p-value #50 bias is only on reversed bits and is minimized to the point where it does not manifest in the full meta-analysis of combined forward, reverse-bits and reverse-bytes.

    This might be a keeper... too many primes to test for e. Final hex digit of 3 or 5 seems to minimize most artifacts, if I were to try more.
  • TonyB_TonyB_ Posts: 2,190
    edited 2019-11-04 02:44
    TonyB_ wrote: »
    ... I don't have enough RAM to test xoroshiro32++a[13,5,10,9] but is it possible that different variants might need different numbers of iterations before all 2^32 outputs occur? If so, the lower the better?
    I am not sure the answer, but regarding RAM, several weeks ago I did a 32-bit distribution test that simply accumulated counts in the ranges 0x00000000-0x0000FFFF and the same range again after rotating 16 bits... I guessed that this was a good proxy for the full distribution.

    Edit: My intuition says: If 1 full stream is 2^32 double-iterations (16GB), then each stream should accomplish 50% coverage of the unsampled 32-bit values, which should deplete, on average, by the 33rd stream. Therefore, in my example above, complete coverage of 2^17 specific 32-bit values should occur in about 18 streams.

    Rather than one word constant, I think the 64K outputs with both words the same would be better, as it would test the immediate effect of the xor and bit reversal in all of these outputs. I'll make some time this week and also check the equidistribution of low and high bytes separately for xoroshiro16++a to see whether they are the same. Some time ago Evan ran some PractRand tests of xoroshiro32++ with every other word skipped, which is how XORO32 or XOROACC might be used.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-11-06 02:59
    Corrected above information and generated evidence that supports the idea that XOROACC32 should generally perform as well as XOROACC16 actually does in producing all possible outputs.
    Edit: My intuition says: If 1 full stream is 2^32 double-iterations (16GB), then each stream should accomplish 50% coverage of the unsampled 32-bit values, which should deplete, on average, by the 33rd stream. Therefore, in my example above, complete coverage of 2^17 specific 32-bit values should occur in about 18 streams.
    My intuition is obviously wrong... decimation of unsampled values is by 1/e, so complete depletion should occur by about the 23rd stream, so therefore complete coverage of 2^16 specific values should occur in about 12 streams.
    I tested this logic out on the small version and it works as expected (at about 12 and 6 streams respectively, in that case).
    Obviously there will be some variation among candidates, but they all should be in the vicinity of being statistically plausible. In any case, should be explicitly tested (since PractRand nor BigCrush will find that information).
    TonyB_ wrote: »
    ...with every other word skipped, which is how XORO32 or XOROACC might be used.
    Do you mean with every other dword skipped (as I can't visualize how an individual word could be skipped in the actual output, since I assumed that only fully processed pairs of words are available to be read from XOROACC by the end user)?

    Edited for clarity.
  • TonyB_ wrote: »
    ...with every other word skipped, which is how XORO32 or XOROACC might be used.
    Do you mean with every other dword skipped (as I can't visualize how an individual word could be skipped in the actual output, since I assumed that only fully processed pairs of words are available to be read from XOROACC by the end user)?

    It's possible the end user might ignore the low or high word of every XORO32/XOROACC output and the randomness of this could be tested by skipping every other word in PractRand or BigCrush, 2^33-2 iterations producing 2^32-1 used words. Instead of being interleaved, the even and odd words would be separated by a full single-iteration period.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-11-17 20:28
    TonyB_ wrote: »
    It's possible the end user might ignore the low or high word of every XORO32/XOROACC output and the randomness of this could be tested by skipping every other word in PractRand or BigCrush, 2^33-2 iterations producing 2^32-1 used words. Instead of being interleaved, the even and odd words would be separated by a full single-iteration period.
    Of course... did some quick non-rotational tests: High and low words each fail (with no precursor issues) in PractRand on GAP at 16GB, regardless of whether revbits was used on the 2nd xoroshiro++ iteration.

    This makes some sense, as every other word benefits from the bit-mixing of the unused word, but still races twice as fast toward failure. However, I would expect BigCrush would notice more issues with the non-revbits version that PractRand somehow missed.

    Edit: Instead of BigCrush, I ran gjrand on 32GB of the various combinations of both/high/low words, forward/reverse output bits, and forward/reverse 2nd iteration using ^5E13. Results attached, w/readme.
    There really is not much very exciting (i.e. statistically differentiating) going on with any of the results of gjrand or BigCrush, other than the conclusion that only PractRand seems to be aware that an improvement occurred (within its statistical purview) with GAP on 32-bit outputs (regarding only the lsb) when only the 2nd xoroshiro++ iteration result bits are reversed. My best guess is that reversing the bits of the 2nd iteration is a good thing (beyond the lsb improvement), but it is also a fine point that would not necessarily be relevant in a purely software implementation.

    Additionally, by random trial I have demonstrated that there are some odd values of e that might be very slightly better than ^5E13h, but many more that are substantially worse.
    Some of those e values are so bad they cause abort issues to occur in PractRand pre0.95 (and might actually trigger a NaN lock-up in 0.94), which I am beta testing only in the random e trial.

    Edit: Readme file in attachment mistakenly mentions (twice) 'reversed before xor', which should instead read 'reversed before sum'.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-11-09 03:08
    My best guess is that reversing the bits of the 2nd iteration is a good thing (beyond the lsb improvement), but it is also a fine point that would not necessarily be relevant in a purely software implementation.
    Probably true, but I have discovered that reversing the bits is not exactly what creates the perceived improvement, but more specifically it is the introduction of the msb into the lsb position...
    Using ROL16(xoroshiro32++, 1) instead of RevBits16(xoroshiro32++) in the second iteration would accomplish the same goal and be more explicitly compatible/performant with a software only implementation, if desired.

    More later, plus I will attach high and low word rotations once I have re-vetted some of the xor constants using this approach, which will take some time.
Sign In or Register to comment.