On Monday, October 12, 2015 at 6:59:58 AM UTC-4, Karl-Uwe Frank wrote:

ctr++;
ctr = RotL32(ctr, 29) + ctr;

(I probably won't post anything else on this, but the "counter" looked interesting.)

So now the "counter" serves to generate a keystream for the a,d,t generator. You might want to look for degenerate cycles of that keystream.

I took 1000 random starting values for ctr, and looked at what cycle they ended up in. Assuming I implemented the counter's update function correctly, 990 of them ended up in one of two different cycles with period 111924. It typically took on the
order of 18K steps before it entered the cycle. These cycles were reached with nearly equal probability.

Nine other starting values arrived at a cycle with period 6760.

The remaining starting value arrived at a cycle with period 4522.

Offhand, I think a random mapping over M is expected to reach cycles with length ≈sqrt(M), and 112K is about right. The fact that there are two cycles with the same period suggests the cycles may be correlated. And that suggests the mapping might
induce some simple relationship that partitions the domain.

The shorter cycles might be worrisome. There are likely to be even shorter ones but, in a probabilistic sense, they appear to be harder to reach.

Bob H

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

This is the successor of bcd32. The main difference is between bcd32 and bcd32_ctr the introduction of a counter. The reason for implementing
this counter is merely to enable the algorithm to produce a useful
output, even if the state variables a,b,c,d are seeded with all 0. If
seeded with all zero, the internal state is immediately in good
condition, so no need to drop any amount of the output. Additionally the counter can be seeded with a non-zero value.

The way how the counter bits are injected into a and d ensure that non
of the state variables will ever hold to many zero bits and furthermore preventing the PRNG from running into a loop. Of course this algorithm
also pass all statistical tests without failure and can be considered as unbiased. The formulae below passes Qualcomms's bias test, John Walker's
ENT, Maurer's Universal test for random bits, show a well uniform
distribution regarding Winston Rayburn's bit analysis and pass all tests
off Pierre L'Ecuyer test suite TestU01, which are SmallCrush, Crush and BigCrush.



This is the algorihtm

//--------------------------------------

#define RotL32(x, y) (((x) << (y)) | ((x) >> (32 - (y))))

static uint32_t a, b, c, d, t, ctr;

// The Seeding Function
void seed_bcd32_ctr(uint32_t seed[]) {
a = seed[0];
b = seed[1];
c = seed[2];
d = seed[3];

t = a + b + c + d;

ctr = seed[4];
}

// The PRNG Function
uint32_t bcd32_ctr() {
// update the counter first
ctr++;

ctr = RotL32(ctr, 29) + ctr;

a = a + (d >> 5) + (ctr << 23);
b = a + (b ^ c);
c = a + (b << 13);
d = a + (d ^ t) + (ctr >> 13);
t = a + t;

return (b ^ c ^ d);
}

//--------------------------------------

This is how the internal state looks like after seeding

a=b=c=d=0

n d t a b c | ctr ==> output
0) 00810000 00800000 00800000 00800000 00800000 | 20000001 ==>
00810000 = 8454144
1) 01882800 02040800 01840800 01840800 82840800 | 64000002 ==>
82882800 = 2189961216
2) 06a2ed40 05145140 03104940 86104940 0c384940 | d0800003 ==>
8c8aed40 = 2357914944
3) 08ff712a 0a59b1ea 054560aa 8f6d60aa b15aa0aa | 6a900004 ==>
36c8b12a = 919122218
4) 0ab4dc03 12670e1d 080d5c33 46451c33 ab93bc33 | 17e20005 ==>
e7627c03 = 3881991171
5) 243dac23 1dca1130 0b630313 f939a313 3fc56313 | dade4006 ==>
e2c16c23 = 3804326947
6) 4a035f57 2dcf01a4 1004f074 d701b074 46137074 | d63a0807 ==>
db119f57 = 3675365207
7) fea8f26b c4a40d12 96d50b6e 27e7cb6e 9042cb6e | f1014909 ==>
490df26b = 1225650795
8) ee59cb85 78ee6013 b44a5301 6bef5301 9eaa7301 | 4f21722b ==>
1b1ceb85 = 454880133
9) 8afb9520 6d2b8170 f43d215d e982415d 3c68c15d | d905a071 ==>
5f111520 = 1594955040
10) 2066b388 a5c07f76 3894fe06 0e7f7e06 2855be06 | 34265480 ==>
064c7388 = 105673608
11) 47c1d5f8 67d8b318 c21833a2 e842f3a2 208c73a2 | 5aab1f11 ==>
8f0f55f8 = 2400146936
12) 5e74d935 a62ef569 3e564251 0724c251 d6a06251 | a60082f4 ==>
8ff07935 = 2414901557
13) e326eb7a 90f8de83 eac9e91a bc4e891a bbed291a | 5ac09353 ==>
e4854b7a = 3833940858
14) 44c88733 61dbfef8 d0e32075 d886c075 a8f1c075 | e618a5be ==>
34bf8733 = 884967219
15) 3323f556 6fe563a6 0e0964ae 7e8064ae 1a9f24ae | e2dbba76 ==>
573cb556 = 1463596374
16) 4ef01501 6207e7fe f2228458 5641c458 2aad8458 | df3731c5 ==>
321c5501 = 840717569
17) 2097d0ef 55a1ecfe f39a0500 70864500 bc3a0500 | bb1e17fe ==>
ec2b90ef = 3962278127
18) e8da93a6 c940b085 739ec387 405b0387 d40fa387 | b281dafe ==>
7c8e33a6 = 2089694118
19) cb8501d7 732648a9 a9e59824 3e3a3824 f0ea1824 | a8d2165e ==>
055521d7 = 89465303
20) fde9f912 b86808db 4541c032 1411e032 81480032 | 9dec592a ==>
68b01912 = 1756371218
21) bab38f12 2d9918d5 75310ffa 0a8aeffa d3304ffa | 11a9e450 ==>
63092f12 = 1661546258
22) 7fb2e332 161fc547 e886ac72 c2414c72 1214ec72 | 33df20db ==>
afe74332 = 2951168818
23) d1b73cd8 7e2408d2 6804438b 3859e38b a475a38b | ba5b04f7 ==>
4d9b7cd8 = 1302035672



a = 0x2F9364B3, b = 0x75B83C2B, c = 0x1276676E, d = 0x1B80703A, ctr =
0x153FFCB
n d t a b c | ctr ==> output
0) dbb57ce3 e631e0ba 12ef6834 7abdc379 cb5e8834 | 817e7fc5 ==>
6a5637ae = 1784035246
1) 36543de6 defef4d5 f8cd141b aab05f68 04ba141b | 51ae4fbe ==>
985e7695 = 2556327573
2) be2c5e5d b47eaadf d57fb60a 838a017d 15af560a | 3be419b6 ==>
2809092a = 671680810
3) 5c452882 066fc3db 51f118fc e8167073 1fff78fc | 23609ced ==>
abac200d = 2880184333
4) f4856bfe a0c3061b 9a534240 923c4acf 23ad2240 | e7ccb08b ==>
45140371 = 1158939505
5) 44c201b6 913a73ba f0776d9f a208d62e 0b3d2d9f | 84c6469d ==>
edf7fa07 = 3992451591
6) 81189ab0 3c57f166 ab1d7dac 5453795d 1a491dac | 555f0f71 ==>
cf02fe41 = 3473079873
7) 1c7aaeae 9b7e33e7 5f264281 ad40a772 74148281 | a00af160 ==>
c52e8b5d = 3308161885
8) ad9555a1 c2084bdd 268a17f6 ffde3de9 ee4737f6 | d40c4f8d ==>
bc0c5fbe = 3154927550
9) 5b19558d ad7f0e80 eb76c2a3 fd0fccc2 e50f02a3 | ae8dd97f ==>
43199bec = 1125751788
10) 3cbc0b58 f3ce9bcf 464f8d4f 5e505bb0 51c58d4f | c45f94b0 ==>
3329dda7 = 858381735
11) bb2fe59c df840978 ebb56da9 fb4b44a8 544a6da9 | fceb8747 ==>
142ecc9d = 338611357
12) 6ebbbe00 e992f64d 0a0eecd5 b91015d6 0cc9acd5 | 1c88f831 ==>
db620703 = 3680634627
13) 30b113e2 9317c112 a984cac5 5f5e83c8 79fdcac5 | 601a1738 ==>
16125aef = 370301679
14) 5eb5873e 4e221476 bb0a5364 e1ad9c71 6e987364 | 8c1d5a20 ==>
d180682b = 3514853419
15) 811d7fed bea21413 707fff9d ffb5eeb2 2e563f9d | bda10565 ==>
50feaec2 = 1358868162
16) bd4d0243 3c2affaf 7d88eb9c 4f6cbccb 15224b9c | 95552612 ==>
e703f514 = 3875796244
17) 6f5b9198 2a1e535d edf353ae 48424b05 3753f3ae | 07ffcad5 ==>
104a2933 = 273295667
18) 4eba3afd 338c8397 096e303a 887fe8e5 068ad03a | c8ffc430 ==>
c04f0222 = 3226403362
19) e49acc78 9af085a8 67640211 f6593af0 8ec20211 | 021fbcb7 ==>
9c01f499 = 2617373849
20) 14733561 30f95e1c 9608d874 0ea41155 18337874 | 0263b44f ==>
02e45c40 = 48520256
21) 2836f31d 34a5d03b 03ac721f 1a43db40 7f14721f | 02b02ada ==>
4d615a42 = 1298225730
22) 3c84650e 5493f9f2 1fee29b7 8545d316 da50e9b7 | 63063036 ==>
63915faf = 1670471599
23) a86c6512 94e646d1 40524cdf 9f678780 31424cdf | 4f66f63d ==>
0649ae4d = 105492045


Example implemantation and test routines can be found here

http://www.freecx.co.uk/bcd32_ctr/

Cheers,
Karl-Uwe



--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 12.10.15 21:40, rsharris.bx.psu.edu@gmail.com wrote:

On Monday, October 12, 2015 at 6:59:58 AM UTC-4, Karl-Uwe Frank
wrote:

ctr++; ctr = RotL32(ctr, 29) + ctr;

(I probably won't post anything else on this, but the "counter"
looked interesting.)

So now the "counter" serves to generate a keystream for the a,d,t
generator.. You might want to look for degenerate cycles of that
keystream.

I took 1000 random starting values for ctr, and looked at what cycle
they ended up in. Assuming I implemented the counter's update
function correctly, 990 of them ended up in one of two different
cycles with period 111924. It typically took on the order of 18K
steps before it entered the cycle. These cycles were reached with
nearly equal probability.

Nine other starting values arrived at a cycle with period 6760.

The remaining starting value arrived at a cycle with period 4522.

Offhand, I think a random mapping over M is expected to reach cycles
with length ≈sqrt(M), and 112K is about right. The fact that there
are two cycles with the same period suggests the cycles may be
correlated. And that suggests the mapping might induce some simple relationship that partitions the domain.

The shorter cycles might be worrisome. There are likely to be even
shorter ones but, in a probabilistic sense, they appear to be harder
to reach.

Bob H

The only solution I can currently think of is having one additional
variable as bit mixer plus the counter

//--------------------------------------
static uint32_t a, b, c, d, t, ctr, mix;

// The Seeding Function
void seed_bcd32_ctr(uint32_t seed[]) {
a = seed[0];
b = seed[1];
c = seed[2];
d = seed[3];

t = a + b + c + d;

ctr = seed[4];
}

// The PRNG Function
uint32_t bcd32_ctr() {
// update the counter first
ctr++;

// bit injector
mix ^= RotL32(mix, 29) + ctr;

a = a + (d >> 5) + (mix << 23);
b = a + (b ^ c);
c = a + (b << 13);
d = a + (d ^ t) + (mix >> 13);
t = a + t;

return (b ^ c ^ d);
}
//--------------------------------------

This modification does produce some same values to appear twice, as far
as I know how to check for this. But every repeating value just appear
two times so far in my test routine.

You may wonder why I not just simply add the counter? This is because I
like to have as much bits as possible in the most significant bits as
possible right after initialisation.

Cheers,
Karl-Uwe


--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 13.10.15 00:10, Karl-Uwe Frank wrote:

The only solution I can currently think of is having one additional
variable as bit mixer plus the counter

//--------------------------------------
static uint32_t a, b, c, d, t, ctr, mix;

// The Seeding Function
void seed_bcd32_ctr(uint32_t seed[]) {
a = seed[0];
b = seed[1];
c = seed[2];
d = seed[3];

t = a + b + c + d;

ctr = seed[4];
}

// The PRNG Function
uint32_t bcd32_ctr() {
// update the counter first
ctr++;

// bit injector
mix ^= RotL32(mix, 29) + ctr;

a = a + (d >> 5) + (mix << 23);
b = a + (b ^ c);
c = a + (b << 13);
d = a + (d ^ t) + (mix >> 13);
t = a + t;

return (b ^ c ^ d);
}
//--------------------------------------

Bad, bad, bad, bad ... the quality of randomness is getting more an more
worse the more complex the PRNG function...

What really is interesting though is that, even with a looping counter
the output passed all tests for randomness. From my point of view this
can only mean that the originally posted first version bcd32 is reliable
in itself, because it's still the core of bcd32_ctr and is stabilising
the output. Need to reflex on that ...



--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 12.10.15 21:40, rsharris.bx.psu.edu@gmail.com wrote:

On Monday, October 12, 2015 at 6:59:58 AM UTC-4, Karl-Uwe Frank wrote:

ctr++;
ctr = RotL32(ctr, 29) + ctr;

(I probably won't post anything else on this, but the "counter" looked interesting.)

So now the "counter" serves to generate a keystream for the a,d,t generator.. You might want to look for degenerate cycles of that keystream.

I took 1000 random starting values for ctr, and looked at what cycle they ended up in. Assuming I implemented the counter's update function correctly, 990 of them ended up in one of two different cycles with period 111924. It typically took on the

order of 18K steps before it entered the cycle. These cycles were reached with nearly equal probability.

Nine other starting values arrived at a cycle with period 6760.

The remaining starting value arrived at a cycle with period 4522.

Offhand, I think a random mapping over M is expected to reach cycles with length ≈sqrt(M), and 112K is about right. The fact that there are two cycles with the same period suggests the cycles may be correlated. And that suggests the mapping might

induce some simple relationship that partitions the domain.

The shorter cycles might be worrisome. There are likely to be even shorter ones but, in a probabilistic sense, they appear to be harder to reach.

Bob H

Thanks for your response and the testing. I can confirm the looping of
the counter after a quick test

a=b=c=d=0, ctr=1 ==> loop = 29566

n d t a b c | ctr ==> output
22436) f9fe36f9 b1449ca0 1ae47bfd 670e5bfd e6641bfd | 00011a83 ==>
789476f9 = 2022995705
52002) 57c3a435 68ee7509 ca0adcd3 5144dcd3 65a53cd3 | 00011a83 ==>
63224435 = 1663190069
81568) 6f5c20dd 0741c076 c3fa14f5 76e334f5 2a98b4f5 | 00011a83 ==>
3327a0dd = 858235101
111134) d5a50220 1633fd42 147fb95b 06a9995b 47ab195b | 00011a83 ==>
94a78220 = 2494005792
140700) 00cab502 10100f6f 7e198227 54874227 665e6227 | 00011a83 ==>
32139502 = 840144130
170266) a22514bf 6ad8f7bd 57a77260 75bc9260 e9f37260 | 00011a83 ==>
3e6af4bf = 1047196863
199832) 5898cf2e a37eb804 c0166e2b 8a674e2b a9dbce2b | 00011a83 ==>
7b244f2e = 2065977134
229398) 1c8cefb2 d78ae3db 1f13f320 99ef9320 1177f320 | 00011a83 ==>
94148fb2 = 2484375474


a=b=c=d=0, ctr=2 ==> loop = 29566

n d t a b c | ctr ==> output
12761) 76ce5cce 8fd3a593 c1b25a20 87f2ba20 18f65a20 | 00011a83 ==>
e9cabcce = 3922377934
42327) 25983eed 7e2ae10a d4f8112f 1ba7f12f d31df12f | 00011a83 ==>
ed223eed = 3978444525
71893) be4dc4e5 010fac2b 1d8332c3 9d9772c3 0bdb92c3 | 00011a83 ==>
280124e5 = 671163621
101459) a438af59 bdfe10cd 4ff8281b ce7e681b 1cfb881b | 00011a83 ==>
76bd4f59 = 1992118105
131025) fc1bac13 c2ddb9da 90895968 dcd49968 23b65968 | 00011a83 ==>
03796c13 = 58289171
160591) acb93316 65580cdd 963de89d 4879689d c351889d | 00011a83 ==>
2791d316 = 663868182
190157) 18fc3402 e4762031 098496fc 3f9436fc 906416fc | 00011a83 ==>
b70c1402 = 3071022082
219723) 1e158e4d 24213b83 d8fafeda a6a21eda 1cd63eda | 00011a83 ==>
a461ae4d = 2757865037


a=b=c=d=0, ctr = 5 ==> loop = 29566

n d t a b c | ctr ==> output
55389) ab3d1391 de5b56ff c5fb95e6 7fe1b5e6 fcb855e6 | 00011a83 ==>
2864f391 = 677704593
84955) 45318fc4 acbe24bb 4e1506a3 398fc6a3 46e966a3 | 00011a83 ==>
3a572fc4 = 978792388
114521) 392cc122 cfa74c1f ede80013 8b5b4013 55ea6013 | 00011a83 ==>
e79de122 = 3885883682
144087) 8a9c116e 008cbde1 00577284 68b89284 12a7f284 | 00011a83 ==>
f083716e = 4035146094
173653) 82f9133d da592e9b 74d4acfc 5912ccfc ce742cfc | 00011a83 ==>
159ff33d = 362804029
203219) f92acaf6 a1926d4c fa032c46 6e8bec46 778bec46 | 00011a83 ==>
e02acaf6 = 3760900854
232785) 822edb0f 80b9f969 37662443 a5222443 7bee8443 | 00011a83 ==>
5ce27b0f = 1558346511
262351) 6aa5891a 5b5bbed6 7eafc337 b1ba2337 c316a337 | 00011a83 ==>
1809091a = 403245338


How did you initialise a,b,c and d?

In fact the loop might occur because the counter value never reach the
full 32bit but instead is truncated by the RotL call. Clearly a
different approach is needed to inject the counter bits and prevent
those loops of the counter.


--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)