• 32 bit PRNG using only cheap operations

From Bob H@21:1/5 to Karl-Uwe Frank on Fri Oct 2 18:12:22 2015
On Friday, October 2, 2015 at 5:51:16 AM UTC-4, Karl-Uwe Frank wrote:
c = a + (b << 13);

Is that correct, or should it be c = a + (c << 13) ?

Bob H

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to Bob H on Sun Oct 4 17:53:04 2015
On 03.10.15 03:12, Bob H wrote:
On Friday, October 2, 2015 at 5:51:16 AM UTC-4, Karl-Uwe Frank wrote:
c = a + (b<< 13);

Is that correct, or should it be c = a + (c<< 13) ?

Bob H
Yes c = a + (b << 13); is correct. The reason is that I like to
calculate the new values of each internal state variable by mixing the
bits from previous and new calculated values - but only some kind of "criss-cross" between b an c.

Do you suppose that it should be always the previous value that is used
to calculate the new one?

Cheers,
Karl-Uwe

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From rsharris.bx.psu.edu@gmail.com@21:1/5 to Karl-Uwe Frank on Mon Oct 5 12:08:27 2015
On Sunday, October 4, 2015 at 11:53:07 AM UTC-4, Karl-Uwe Frank wrote:
... Do you suppose that it should be always the previous value that is used to calculate the new one?

No, I just wanted to be sure. The updates for the other variables all involve their previous value.

What I was actually looking at was to try to describe/categorize the degenerate states. The zero state is one but there are others.

And I was trying to convince myself whether the state-to-state function is invertible or not.

So, a, d, and t form their own generator, with no involvement of b and c. The updates of b and c are derived from part of the state of that generator (only from a). The a,d,t generator is invertible. For some reason I'm having a hard time wrapping my
head around whether the b,c part can be inverted.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Tue Oct 6 19:44:50 2015
On 06.10.15 19:25, rsharris.bx.psu.edu@gmail.com wrote:
On 05.10.15 21:08, I wrote:
What I was actually looking at was to try to describe/categorize the degenerate
states. The zero state is one but there are others.

On Tuesday, October 6, 2015 at 1:04:44 PM UTC-4, Karl-Uwe Frank wrote:
That's something very interesting to me. So, would you mind sharing some
of these degenerate states (other than zero)?

I haven't spent much time on it yet, but I did find a few other degenerate states.

I consider this as a two level generator, where a,d,t is one generator, and a is used like a keystream for the b,c generator. If a,d,t reach zero, they will stay there. This can happen in your initialization if a=d=0 and b+c=0. FWIW, in this case
the b,c generator is invertible.

(Unless I am wrong) The a,d,t generator is invertible. So it can't reach zero unless it starts at zero.

I don't have access at the moment to some of the other states I tried. IIRC, I tried a=b=c=d=0 and t=1, and it did something interesting. But I might be wrong.

I also think you could kick the thing out of any zero state by adding a constant somewhere. But I have no idea what that will do to your randomness.

Bob H

Thanks a lot for your rely. I will have a closer look at that a=b=c=d=0
and t=1 state.

As you mentioned the possibility of degenerate states other than zero in
smallest constant in order to prevent the internal state falling flat.
Now I need to figure out if it's sufficient and as you said how this
will influence the randomness.

Cheers,
Karl-Uwe

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Tue Oct 6 19:04:42 2015
On 05.10.15 21:08, rsharris.bx.psu.edu@gmail.com wrote:
On Sunday, October 4, 2015 at 11:53:07 AM UTC-4, Karl-Uwe Frank wrote:
... Do you suppose that it should be always the previous value that is used >> to calculate the new one?

No, I just wanted to be sure. The updates for the other variables all involve their previous value.

What I was actually looking at was to try to describe/categorize the degenerate states. The zero state is one but there are others.

That's something very interesting to me. So, would you mind sharing some
of these degenerate states (other than zero)?

And I was trying to convince myself whether the state-to-state function is invertible or not.

So, a, d, and t form their own generator, with no involvement of b and c. The updates of b and c are derived from part of the state of that generator (only from a). The a,d,t generator is invertible. For some reason I'm having a hard time wrapping
my head around whether the b,c part can be inverted.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From rsharris.bx.psu.edu@gmail.com@21:1/5 to Karl-Uwe Frank on Tue Oct 6 10:25:29 2015
On 05.10.15 21:08, I wrote:
What I was actually looking at was to try to describe/categorize the degenerate
states. The zero state is one but there are others.

On Tuesday, October 6, 2015 at 1:04:44 PM UTC-4, Karl-Uwe Frank wrote:
That's something very interesting to me. So, would you mind sharing some
of these degenerate states (other than zero)?

I haven't spent much time on it yet, but I did find a few other degenerate states.

I consider this as a two level generator, where a,d,t is one generator, and a is used like a keystream for the b,c generator. If a,d,t reach zero, they will stay there. This can happen in your initialization if a=d=0 and b+c=0. FWIW, in this case the
b,c generator is invertible.

(Unless I am wrong) The a,d,t generator is invertible. So it can't reach zero unless it starts at zero.

I don't have access at the moment to some of the other states I tried. IIRC, I tried a=b=c=d=0 and t=1, and it did something interesting. But I might be wrong.

I also think you could kick the thing out of any zero state by adding a constant somewhere. But I have no idea what that will do to your randomness.

Bob H

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From rsharris.bx.psu.edu@gmail.com@21:1/5 to Karl-Uwe Frank on Tue Oct 6 12:37:52 2015
On Tuesday, October 6, 2015 at 1:44:54 PM UTC-4, Karl-Uwe Frank wrote:
Thanks a lot for your rely. I will have a closer look at that a=b=c=d=0
and t=1 state.

See table below, but (for the moment) ignore the b and c columns. The a=b=c=d=0 t=1 state just alternates d between 0 and 1 (assuming my quick python implementation is correct). In fact a=b=c=d=0 t<32 will exhibit similar behavior.

Now if we also start with c=1, we get an idea of what can happen with b,c when a stays at zero. It quickly degenerates to a period-4 loop. We reach the same loop if we begin with b=1 instead. If I start with B=37 I fall into another period-4 loop.

n d t a b c
0 00000000 00000001 00000000 00000000 00000001 (values here are in hex)
1 00000001 00000001 00000000 00000001 00002000
2 00000000 00000001 00000000 00002001 04002000
3 00000001 00000001 00000000 04000001 00002000
4 00000000 00000001 00000000 04002001 04002000
5 00000001 00000001 00000000 00000001 00002000

Bob H

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Tue Oct 6 22:32:12 2015
On 06.10.15 21:37, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 1:44:54 PM UTC-4, Karl-Uwe Frank wrote:
Thanks a lot for your rely. I will have a closer look at that a=b=c=d=0
and t=1 state.

See table below, but (for the moment) ignore the b and c columns. The a=b=c=d=0 t=1 state just alternates d between 0 and 1 (assuming my quick python implementation is correct). In fact a=b=c=d=0 t<32 will exhibit similar behavior.

Now if we also start with c=1, we get an idea of what can happen with b,c when a stays at zero. It quickly degenerates to a period-4 loop. We reach the same loop if we begin with b=1 instead. If I start with B=37 I fall into another period-4 loop.

n d t a b c
0 00000000 00000001 00000000 00000000 00000001 (values here are in hex)
1 00000001 00000001 00000000 00000001 00002000
2 00000000 00000001 00000000 00002001 04002000
3 00000001 00000001 00000000 04000001 00002000
4 00000000 00000001 00000000 04002001 04002000
5 00000001 00000001 00000000 00000001 00002000

Bob H

I just posted my answer after I was off-line for a short period not
reading this post of yours first. Hope that's okay for you.

If the initial value b is set to b=37 how about a,c and d than?

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Tue Oct 6 22:37:41 2015
On 06.10.15 21:37, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 1:44:54 PM UTC-4, Karl-Uwe Frank wrote:
Thanks a lot for your rely. I will have a closer look at that a=b=c=d=0
and t=1 state.

See table below, but (for the moment) ignore the b and c columns. The a=b=c=d=0 t=1 state just alternates d between 0 and 1 (assuming my quick python implementation is correct). In fact a=b=c=d=0 t<32 will exhibit similar behavior.

Now if we also start with c=1, we get an idea of what can happen with b,c when a stays at zero. It quickly degenerates to a period-4 loop. We reach the same loop if we begin with b=1 instead. If I start with B=37 I fall into another period-4 loop.

n d t a b c
0 00000000 00000001 00000000 00000000 00000001 (values here are in hex)
1 00000001 00000001 00000000 00000001 00002000
2 00000000 00000001 00000000 00002001 04002000
3 00000001 00000001 00000000 04000001 00002000
4 00000000 00000001 00000000 04002001 04002000
5 00000001 00000001 00000000 00000001 00002000

Bob H

By the way, if the setup is like below we can see that the output will
quickly recover into a useful state

a=t=1, b=c=d=0

02 20 00 00 01 00 00 04 03 20 00 04 08 00 00 00
0E 20 00 00 09 00 00 04 0F 20 00 04 08 00 00 00
02 20 00 00 09 00 00 04 03 20 00 04 10 00 00 00
1E 20 00 00 11 00 00 04 1F 20 00 04 10 00 00 00
02 20 00 00 11 00 00 04 03 20 00 04 18 00 00 00
0E 20 00 00 19 00 00 04 0F 20 00 04 18 00 00 00
02 20 00 00 19 00 00 04 03 20 00 04 20 00 00 00
3F 40 00 00 23 20 00 08 05 A0 00 0C 27 20 00 18
12 80 00 1C 42 20 00 0C 7D C0 00 08 50 80 01 10
21 00 00 20 7D A0 01 20 33 A0 03 14 6E 80 01 60
25 00 03 50 CB A0 01 30 7E C0 02 04 DB 00 01 5C
5E 80 05 7C 81 41 01 CC DC 00 07 E4 B9 01 00 04
71 A0 08 04 F3 A1 01 10 28 44 0B 24 C9 46 04 4C
E6 84 11 C4 4E 28 0B F4 51 CD 29 90 5B EA 19 A8
2A 8F 23 94 41 0A 6A E4 08 C4 39 A4 7F 0C 6E 9C
19 00 0A 5C D2 37 8E 18 FA C5 35 D8 60 1F D4 64
DF 24 F5 E1 8F F3 B0 40 2C AF E9 5D D9 79 61 6C

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Tue Oct 6 22:26:17 2015
On 06.10.15 19:25, rsharris.bx.psu.edu@gmail.com wrote:
On 05.10.15 21:08, I wrote:
What I was actually looking at was to try to describe/categorize
the degenerate states. The zero state is one but there are
others.

On Tuesday, October 6, 2015 at 1:04:44 PM UTC-4, Karl-Uwe Frank
wrote:
That's something very interesting to me. So, would you mind sharing
some of these degenerate states (other than zero)?

I haven't spent much time on it yet, but I did find a few other
degenerate states.

You're for sure not talking about the degenerate states like

b=t=1, a=c=d=0
c=t=1, a=b=d=0
d=t=1, a=b=c=0

are you?

Of course all of them will produce a constant flat and alternating
output like

b=t=1, a=c=d=0

c=t=1, a=b=d=0

00 20 00 00 01 00 00 04 00 20 00 04 01 00 00 00
00 20 00 00 01 00 00 04 00 20 00 04 01 00 00 00
00 20 00 00 01 00 00 04 00 20 00 04 01 00 00 00
00 20 00 00 01 00 00 04 00 20 00 04 01 00 00 00
00 20 00 00 01 00 00 04 00 20 00 04 01 00 00 00

d=t=1, a=b=c=0

00 00 00 00 01 00 00 00 00 00 00 00 01 00 00 00
00 00 00 00 01 00 00 00 00 00 00 00 01 00 00 00
00 00 00 00 01 00 00 00 00 00 00 00 01 00 00 00
00 00 00 00 01 00 00 00 00 00 00 00 01 00 00 00
00 00 00 00 01 00 00 00 00 00 00 00 01 00 00 00

I consider this as a two level generator, where a,d,t is one
generator, and a is used like a keystream for the b,c generator. If
a,d,t reach zero, they will stay there. This can happen in your initialization if a=d=0 and b+c=0. FWIW, in this case the b,c
generator is invertible.

For that reason I stated in the source code that the variables a,b,c,d
should not be initialised with all zero and should at least differ by 1
bit. Perhaps forgot to mention this in my initial posting.

(Unless I am wrong) The a,d,t generator is invertible. So it can't
reach zero unless it starts at zero.

It is interesting if there might be such a combination of initial values
that will lead a,d,t reaching all zero somehow, but currently can't
think of any such possibility how that could happen if the variables are properly initialise by 1 bit difference.

I don't have access at the moment to some of the other states I
tried. IIRC, I tried a=b=c=d=0 and t=1, and it did something
interesting. But I might be wrong.

Apparently I can't imagine how this state could ever be reached, but
obviously it will lead to an continuous output of all 1.

I also think you could kick the thing out of any zero state by adding
a constant somewhere. But I have no idea what that will do to your randomness.

As mentioned earlier this could be just adding 1 or perhaps the "golden
ratio" 0x9E3779B9

Bob H

Cheers,
Karl-Uwe

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Wed Oct 7 01:42:02 2015
On 06.10.15 19:25, rsharris.bx.psu.edu@gmail.com wrote:
On 05.10.15 21:08, I wrote:
What I was actually looking at was to try to describe/categorize
the degenerate states. The zero state is one but there are
others.

On Tuesday, October 6, 2015 at 1:04:44 PM UTC-4, Karl-Uwe Frank
wrote:
That's something very interesting to me. So, would you mind sharing
some of these degenerate states (other than zero)?

I haven't spent much time on it yet, but I did find a few other
degenerate states.

I consider this as a two level generator, where a,d,t is one
generator, and a is used like a keystream for the b,c generator. If
a,d,t reach zero, they will stay there. This can happen in your initialization if a=d=0 and b+c=0. FWIW, in this case the b,c
generator is invertible.

(Unless I am wrong) The a,d,t generator is invertible. So it can't
reach zero unless it starts at zero.

Now let's think a bit further. As you named it so brilliantly /a/ is
used as the keystream generator for the output.

But instead of only adding a constant it would be rather more
interesting adding a 32bit counter somewhere as well. And obviously this counter value would be added to /a/.

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

uint32_t bcd32ctr(){

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

ctr++;

return (b ^ c ^ d);
}

If we seed the PRNG with 160bit of entropy, where 4 x 32bit are used for
the internal state vars a,b,c,d and 1 x 32bit is used to initialise the
counter ctr the whole output will stay unbiased for sure. Moreover as
the initial value of the counter is unknown so is the point when it will
roll over to 0.

This way the internal state will stay unpredictable as well as the
output and it does not loose any entropy.

Just a quick thought which I need to verify.

Cheers,
Karl-Uwe

I don't have access at the moment to some of the other states I
tried. IIRC, I tried a=b=c=d=0 and t=1, and it did something
interesting. But I might be wrong.

I also think you could kick the thing out of any zero state by adding
a constant somewhere. But I have no idea what that will do to your randomness.

Bob H

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From rsharris.bx.psu.edu@gmail.com@21:1/5 to Karl-Uwe Frank on Tue Oct 6 19:13:46 2015
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank wrote:
You're for sure not talking about the degenerate states like
b=t=1, a=c=d=0
c=t=1, a=b=d=0
d=t=1, a=b=c=0
are you?

Yeah, why wouldn't I? (The question is rhetorical)

For that reason I stated in the source code that the variables a,b,c,d should not be initialised with all zero and should at least differ by 1
bit. Perhaps forgot to mention this in my initial posting.

On a related note, I had this experience about 20 years ago where I wrote a tool and a coworker complained it didn't work right when he used it. I noticed he was using it for a situation it didn't support, and I said "it says right in the source code it
doesn't work for that". Then it dawned on me that the source code is just about the last place I should expect him to go to find out what's supported and what isn't.

By the way, if the setup is like below we can see that the output will quickly recover into a useful state
a=t=1, b=c=d=0

I don't understand the table of bytes you printed out. Maybe you are only looking at the output? But that can't be it, because your first post said it was a 32-bit generator.

What I see for that initial state ... after 40 steps what I see is that b and c are beginning to look random to the eyeball. But d,t,a have managed to hold onto most of the zeros. Looks like it takes around 150 steps to get a 1 into the most
significant bit of a.

n d t a b c
0 00000000 00000000 00000001 00000001 00000000
...
40 000004F5 000003A8 000000B0 8025E405 BC80A0B0

[If we make these cool changes to the algorithm, and] if we seed the
PRNG [in some cool way] the whole output will stay unbiased for sure.

You might want to consider a more formal mathematical proof for whether "the whole output will stay unbiased". Or that might depend on what you want from this generator and how confident you are that, in the absence of any mathematical analysis, it will
stay unbiased for sure.

In any case, thanks for posting what became a nice little puzzle for me. Good luck with it.

Bob H

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Wed Oct 7 00:35:05 2015
On 06.10.15 19:25, rsharris.bx.psu.edu@gmail.com wrote:

I also think you could kick the thing out of any zero state by adding
a constant somewhere. But I have no idea what that will do to your randomness.

When changing the algorithm by adding 1 as constant

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

return (b ^ c ^ d);

the internal state will always recover even when forcing /a/ down to
zero which I have just verified (but didn't check the quality of
randomness yet)

// force a down to zero
if ((b ^ c ^ d) > 1024057) a = 0;

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

Nonetheless the original formulae quickly get into a reasonable state
even if a=t=1, b=c=d=0 as a bit analysis show

Test No.: 1
----------------------------------------------------
stdin contains 1024 bytes (8192 bits)

BIT ANALYSIS

Value Count Percentage
----- ----- ----------
one 3508 42.822266
zero 4684 57.177734

Bit Count Percentage
--- ----- ----------
msb 7 428 41.796875
6 414 40.429688
5 440 42.968750
4 449 43.847656
3 453 44.238281
2 461 45.019531
1 408 39.843750
lsb 0 455 44.433594

1/0 ratio 0.748933
Deviance from unity -0.251067

====================================================

Test No.: 1
----------------------------------------------------
stdin contains 4096 bytes (32768 bits)

BIT ANALYSIS

Value Count Percentage
----- ----- ----------
one 15827 48.300171
zero 16941 51.699829

Bit Count Percentage
--- ----- ----------
msb 7 1943 47.436523
6 1992 48.632812
5 1995 48.706055
4 1986 48.486328
3 1974 48.193359
2 2030 49.560547
1 1929 47.094727
lsb 0 1978 48.291016

1/0 ratio 0.934242
Deviance from unity -0.065758

====================================================

Test No.: 1
----------------------------------------------------
stdin contains 16384 bytes (131072 bits)

BIT ANALYSIS

Value Count Percentage
----- ----- ----------
one 65012 49.600220
zero 66060 50.399780

Bit Count Percentage
--- ----- ----------
msb 7 8127 49.603271
6 8104 49.462891
5 8082 49.328613
4 8169 49.859619
3 8024 48.974609
2 8181 49.932861
1 8106 49.475098
lsb 0 8219 50.164795

1/0 ratio 0.984136
Deviance from unity -0.015864

====================================================

Test No.: 1
----------------------------------------------------
stdin contains 32768 bytes (262144 bits)

BIT ANALYSIS

Value Count Percentage
----- ----- ----------
one 130647 49.837875
zero 131497 50.162125

Bit Count Percentage
--- ----- ----------
msb 7 16357 49.917603
6 16433 50.149536
5 16316 49.792480
4 16303 49.752808
3 16195 49.423218
2 16360 49.926758
1 16302 49.749756
lsb 0 16381 49.990845

1/0 ratio 0.993536
Deviance from unity -0.006464

====================================================

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Wed Oct 7 22:10:15 2015
On 07.10.15 04:13, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank
wrote:
You're for sure not talking about the degenerate states like b=t=1,
a=c=d=0 c=t=1, a=b=d=0 d=t=1, a=b=c=0 are you?

Yeah, why wouldn't I? (The question is rhetorical)

For that reason I stated in the source code that the variables
a,b,c,d should not be initialised with all zero and should at least
differ by 1 bit. Perhaps forgot to mention this in my initial
posting.

On a related note, I had this experience about 20 years ago where I
wrote a tool and a coworker complained it didn't work right when he
used it. I noticed he was using it for a situation it didn't
support, and I said "it says right in the source code it doesn't work
for that". Then it dawned on me that the source code is just about
the last place I should expect him to go to find out what's supported
and what isn't.

Just came across this comment regarding the Mersenne-Twister

"Finally, MT had some problems when badly initialized: it tended to draw
lots of 0, leading to bad quality random numbers. This problem could
last up to 700,000 draws before being compensated by the recurrence of
the algorithm."

And on WikiPedia it reads that, if the MT is badly initialised

"It can take a long time to start generating output that passes
randomness tests, if the initial state is highly non-random -
particularly if the initial state has many zeros."

and

"It passes most, but not all, of the stringent TestU01 randomness tests."

On the German WikiPedia it reads that it's recommended to drop the first 800,000 outputs if the MT is initialised with only 1 bit and all the
rest zero.

In contrast my first posted algorithm will recover far more quickly, if initialised with a=1, b=c=d=0.

My question now: is there any known RNG around that passes all TestU01 randomness test and which can be seeded with all zero?

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From William Unruh@21:1/5 to Karl-Uwe Frank on Thu Oct 8 10:53:19 2015
On 2015-10-07, Karl-Uwe Frank <karl.frank@freecx.co.uk> wrote:
On 07.10.15 04:13, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank
wrote:
You're for sure not talking about the degenerate states like b=t=1,
a=c=d=0 c=t=1, a=b=d=0 d=t=1, a=b=c=0 are you?

Yeah, why wouldn't I? (The question is rhetorical)

For that reason I stated in the source code that the variables
a,b,c,d should not be initialised with all zero and should at least
differ by 1 bit. Perhaps forgot to mention this in my initial
posting.

On a related note, I had this experience about 20 years ago where I
wrote a tool and a coworker complained it didn't work right when he
used it. I noticed he was using it for a situation it didn't
support, and I said "it says right in the source code it doesn't work
for that". Then it dawned on me that the source code is just about
the last place I should expect him to go to find out what's supported
and what isn't.

Just came across this comment regarding the Mersenne-Twister

"Finally, MT had some problems when badly initialized: it tended to draw
lots of 0, leading to bad quality random numbers. This problem could
last up to 700,000 draws before being compensated by the recurrence of
the algorithm."

And on WikiPedia it reads that, if the MT is badly initialised

"It can take a long time to start generating output that passes
randomness tests, if the initial state is highly non-random -
particularly if the initial state has many zeros."

and

"It passes most, but not all, of the stringent TestU01 randomness tests."

On the German WikiPedia it reads that it's recommended to drop the first 800,000 outputs if the MT is initialised with only 1 bit and all the
rest zero.

In contrast my first posted algorithm will recover far more quickly, if initialised with a=1, b=c=d=0.

My question now: is there any known RNG around that passes all TestU01 randomness test and which can be seeded with all zero?

Does MT work with all 1 bits? In which case the algorithm could be
MT with the seed being BITWISENOT of the entered seed. Of couser that
would then be bad for all 1 entered:-)
Ie, you need to specify what you need better. You want something with no
week keys, or is all 0 somehow special for you?

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Wed Oct 7 11:02:22 2015
On 07.10.15 04:13, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank
wrote:
You're for sure not talking about the degenerate states like b=t=1,
a=c=d=0 c=t=1, a=b=d=0 d=t=1, a=b=c=0 are you?

Yeah, why wouldn't I? (The question is rhetorical)

For that reason I stated in the source code that the variables
a,b,c,d should not be initialised with all zero and should at least
differ by 1 bit. Perhaps forgot to mention this in my initial
posting.

On a related note, I had this experience about 20 years ago where I
wrote a tool and a coworker complained it didn't work right when he
used it. I noticed he was using it for a situation it didn't
support, and I said "it says right in the source code it doesn't work
for that". Then it dawned on me that the source code is just about
the last place I should expect him to go to find out what's supported
and what isn't.

Yes, you're absolutely right, there is a chance that the user might
initialise it not properly and will end up with an alternating output.

As mentioned in my initial post ,the xorshift128 was basically
inspiring, where a proper seeding is essential too - but of course I
will keep in mind your experience.

By the way, if the setup is like below we can see that the output
will quickly recover into a useful state a=t=1, b=c=d=0

I don't understand the table of bytes you printed out. Maybe you are
only looking at the output? But that can't be it, because your first
post said it was a 32-bit generator.

What I see for that initial state ... after 40 steps what I see is
that b and c are beginning to look random to the eyeball. But d,t,a
have managed to hold onto most of the zeros. Looks like it takes
around 150 steps to get a 1 into the most significant bit of a.

n d t a b
c 0 00000000 00000000 00000001 00000001 00000000 .... 40 000004F5
000003A8 000000B0 8025E405 BC80A0B0

And you're right here again, I am only looking at the output and never
checked how the internal state evolve. This is namely because the output
is what I can test for randomness and what will be used for whatever
purpose. For example one thought was using the output consecutively as
128bit IV or counter for a cipher algorithm. But clearly, anyone who is
prone in breaking the algorithm might be more interested in the internal
state behaviour, getting some idea how he can revert the output in order
to get hands on the internal state or the seed perhaps.

[If we make these cool changes to the algorithm, and] if we seed
the PRNG [in some cool way] the whole output will stay unbiased for
sure.

You might want to consider a more formal mathematical proof for
whether "the whole output will stay unbiased". Or that might depend
on what you want from this generator and how confident you are that,
in the absence of any mathematical analysis, it will stay unbiased
for sure.

Obviously the algorithm needed a tweak, just in case it would
accidentally be seeded with all zero initially. Unfortunately currently
I can't submit any formal mathematical proof. I am looking at the whole
thing from a logical standpoint and check the correctness by long runs
of different empirical statistical test tools. But of course, as in a
saying from Albert Einstein "No amount of experimentation can ever prove
me right, but a single experiment can prove me wrong.", there might be
that particular initial state (appart from all zero) or that particular combination of a,b,c,d and t, while running, which will flatten the
output, but I can't imagine one. When designing the algorithm I first
had some extra lines of code implemented that I removed later before
publishing

a = rand();
b = rand();
c = rand();
d = rand();

if (a==0) a = 1;
if (b==0) b = a+2;
if (c==0) c = a+3;
if (d==0) d = a+4;

t = a + b + c + d;

This was basically to keep the 1 bit distance between all vars after initialisation. Then I thought, like for xorshift128, it might be
sufficient to point out in the source code that a,b,c,d should not be
seeded with all zero and that there should be the 1 bit distance.
Clearly a mistake.

better solution to keep /a/ away from getting into zero while running.
The additional counter might improve the output even more - not to
mention the greater secret internal state. I think it is legitimate to
improve an algorithm all the way if improvement is necessary.

In any case, thanks for posting what became a nice little puzzle for
me. Good luck with it.

Bob H
Many thanks for having a look at the algorithm and sharing your
professional knowledge. For me the designing in the first place was just
a quick hack out of curiosity, in order to find a nice formulae that
will pass all statistical test and keep the internal state unknown.

Cheers,
Karl-Uwe

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Thu Oct 8 18:48:57 2015
On 07.10.15 04:13, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank wrote:

By the way, if the setup is like below we can see that the output will
quickly recover into a useful state
a=t=1, b=c=d=0

I don't understand the table of bytes you printed out. Maybe you are
only looking at the output? But that can't be it, because your first
post said it was a 32-bit generator.

What I see for that initial state ... after 40 steps what I see is
that b and c are beginning to look random to the eyeball. But d,t,a have managed to hold onto most of the zeros. Looks like it takes around 150
steps to get a 1 into the most significant bit of a.

n d t a b c
0 00000000 00000000 00000001 00000001 00000000
....
40 000004F5 000003A8 000000B0 8025E405 BC80A0B0

I like to apologise for not understanding the importance of looking at
the internal state, as you pointed out here. Obviously this reveals a
certain possibility that the output is not of good quality if the PRNG
is not seeded properly. Which of course can happen, if for example the
user just seed the PRNG with >0 <32bit only, or for real even with 0 -
what really seems to happen, as I have read in some forums discussions.

Now if we also start with c=1, we get an idea of what can happen
with
b,c when a stays at zero. It quickly degenerates to a period-4 loop. We
fall into another period-4 loop.

n d t a b c
0 00000000 00000001 00000000 00000000 00000001 (values here are in hex)
1 00000001 00000001 00000000 00000001 00002000
2 00000000 00000001 00000000 00002001 04002000
3 00000001 00000001 00000000 04000001 00002000
4 00000000 00000001 00000000 04002001 04002000
5 00000001 00000001 00000000 00000001 00002000

Regarding a=c=d=0, b=t=1 I can confirm the loop, but with a=c=d=0,b=t=37
it recovers after round about 100 draws

n d t a b c ==> output
0) 00000000 00000037 00000000 00000037 00000000 ==> 0006e000
1) 00000037 00000037 00000000 00000037 0006e000 ==> dc01e038
2) 00000001 00000038 00000001 0006e038 dc070001 ==> e006a001
3) 0000003a 00000039 00000001 dc01e03a 3c074001 ==> 3401003a
4) 00000005 0000003b 00000002 e006a03d d407a002 ==> 14092003
5) 00000040 0000003d 00000002 34010041 20082002 ==> 3001c0c2
6) 00000081 00000041 00000004 14092047 2408e004 ==> 0808a08b
...
24) 00000470 000005db 0000011d 08f285ea 50bd411d ==> a089259c
25) 000002eb 0000071b 00000140 584fc637 f8c6e140 ==> 8590eede
26) 00000747 00000872 00000157 a08928ce 2519c157 ==> 98f5ba7d
27) 000010c6 00000a03 00000191 8590eb2a 1d654191 ==> 2d6ff219
28) 00001cdc 00000c1a 00000217 98f5acd2 b59a4217 ==> d357a0fc
29) 000013c3 00000f17 000002fd 2d6ff1c2 fe3842fd ==> 258cd52e
30) 0000206f 000012b2 0000039b d357b6da f6db439b ==> bab72a3a
...
96) 3d54cb08 28229aba 059af1db 460ab472 5c2931db ==> 1613ec0a
97) 1cfbe9e5 2fa832ed 07859833 21a91ddc 2b411833 ==> 908fb879
98) 3bc1528a 3815aa6f 086d7782 13557d71 b81b9782 ==> ec56b5e4
99) 0e207afb 42612c85 0a4b8216 b59a6d09 57eca216 ==> ce908c8a
100) 56fddc6b 4d1db272 0abc85ed ed33550c 755e05ed ==> ca9fb388
101) 2954e2e9 5a922742 0d7474d0 a5e1c5b1 462a94d0 ==> 2c67973d
102) 8285e192 69514329 0ebf1be7 f28a6d48 5c681be7 ==> f415a6ff
103) fea7edae 7c248e1c 12d34af3 c1b5c1a2 cb078af3 ==> cd4f91c3
104) 9d4bee12 96ed187c 1ac88a60 257ad5b1 757eaa60 ==> 4809804f
105) 2b59e03e b6a0024c 1fb2e9d0 6fb769a1 0ce709d0 ==> df6c7ad0
106) bf079b43 d7adbb1d 210db8d1 845e1942 e435f8d1 ==> 692c749c

[If we make these cool changes to the algorithm, and] if we seed the
PRNG [in some cool way] the whole output will stay unbiased for sure.

Clearly the algorithm need a tweak to cope with an improper seeding.

What I have done now is changing the code slightly this way

a = seed[0];
b = seed[1];
c = seed[2];
d = seed[3];

// a precaution for improper seeding
if (a==0) a = 2654435769;
if (b==0) b = a + (a<<27);
if (c==0) c = b + (b<<29);
if (d==0) d = c + (c<<31);

t = a + b + c + d;

If we start looking at the internal state and output after seeding with a=1,b=c=d=0 we can realise that it recovers very quickly

n d t a b c ==> output
0) a8000001 d8000004 00000001 08000001 28000001 ==> 55402006
1) 75400006 dd400005 05400001 25400001 05402001 ==> d4ea0004
2) b0ea0004 e62a0006 08ea0001 28ea2001 4cea2001 ==> 2f317003
3) 65315003 f49b5007 0e715001 72715001 38717001 ==> 8834da85
4) a344da85 06362a88 119ada81 5b9afa81 70eafa81 ==> 48dd5162
5) bc27f162 1ceb2bdd 16b50155 42250155 b6dfa155 ==> 9441bb9f
6) bd631b9f 39816cbd 1c9640e0 1190e0e0 38b240e0 ==> 4d78f0de
7) a763d0de 5c02c679 228159bc 4ba3f9bc a1b8d9bc ==> 280eaee9
8) 231d8ee9 83bf3ebb 27bc7842 11d79842 1ac4b842 ==> c3fc150b
9) c978150b ac94a374 28d564b9 33e884b9 396c84b9 ==> 7f65bbe0
10) 950ddbe0 dbb5c8d5 2f212561 39a52561 d3cd4561 ==> eee1c775
11) 8281a775 0f7f5d15 33c99440 1e31f440 72519440 ==> 99ef9bdb
12) c5dc9bdb 475cfe90 37dda17b a43e017b f80d017b ==> 7464cba4
13) c08ceba4 856984e9 3e0c8659 9a3f8659 2ed7a659 ==> 14c8fd03
14) 89f65d03 c97a729f 4410edb6 f8f90db6 65c7adb6 ==> 5d07f03a

Now a seeding with a=b=c=d=0 will give us

n d t a b c ==> output
0) 063779b9 90dde6e4 9e3779b9 663779b9 863779b9 ==> 8e2314e3
1) 3553d4e3 2f471c6a 9e693586 7e693586 c519f586 ==> d3357cb6
2) ba289cb6 cf5af097 a013d42d 5b84942d 3299742d ==> 11522533
3) 1b578533 754009a9 a5e51912 0f02f912 05075912 ==> f17521d5
4) 14d761d5 1bffdee4 a6bfd53b b0c5753b 5567353b ==> fae82f7a
5) b68f4f7a c3666f2d a7669049 8d08d049 c16fb049 ==> 20f5cb1b
6) 23042b1b 708179f1 ad1b0ac4 f9826ac4 fa738ac4 ==> fc2bdf06
7) 01b87f06 1eb4a60d ae332c1c b2250c1c 4fb6ac1c ==> 26da291f
8) cd4dc91f ccf59621 ae40f014 abd49014 40437014 ==> 0a565d9a
9) b663bd9a 81a0f47d b4ab5e5c a0433e5c 1c76de5c ==> c152e62f
10) f221c62f 3bff70c5 ba5e7c48 76945c48 45e77c48 ==> 69924163
11) 8bce4163 fdeefb3e c1ef8a79 f562aa79 173eaa79 ==> 911936e1
12) 3c6eb6e1 c43cf7c2 c64dfc84 a8a9fc84 05de7c84 ==> 5353935e
13) c083b35e 8c6e69fd c831723b 75a8f23b e678d23b ==> fd16ea78
14) 1b236a78 5aa3f9d2 ce358fd5 6205afd5 84302fd5 ==> f1b8bed2
...
24) 6a0ce114 ff1f2aab f0ca1236 bf1df236 af10d236 ==> 6a4be4fd
25) 892e44fd f339a3e9 f41a793e 0427993e e742393e ==> 8062d279
26) 727bd279 eb9d8f4e f863eb65 dbc98b65 29d08b65 ==> 6ef8272f
27) 95de272f e7955946 fbf7c9f8 ee10c9f8 1536c9f8 ==> 1132599a
28) 72f2399a e83c1477 00a6bb31 fbccbb31 980cdb31 ==> 212f3aea
29) 9f0c7aea ec7a6174 043e4cfd 67feacfd d9ddecfd ==> fca40c72
30) 7caccc72 f5b11248 0936b0d4 c759f0d4 475130d4 ==> b31fd571
31) 9639f571 02cd297f 0d1c1737 8d24d737 a802f737 ==> 029ce2f0
32) a6c2c2f0 149b1061 11cde6e2 36f406e2 92aa26e2 ==> 289ccf8a
33) c95dcf8a 2b9f0d5a 1703fcf9 bb621cf9 5aa31cf9 ==> e5a3ce45
34) 0011ae45 48edf8cf 1d4eeb75 ff0feb75 1abd8b75 ==> 3d264f71
35) 664bcf71 663d71b6 1d4f78e7 0301d8e7 586c58e7 ==> 5079d629
36) 20f89629 86bf4918 2081d762 7bef5762 0b6e1762 ==> 28d05b44
37) c7d17b44 a848e52b 21899c13 920adc13 7d0bfc13 ==> d16d465c
38) 9761c65c d0110d18 27c827ed 16c947ed 50c5c7ed ==> 223ca163
39) 73f40163 fc944337 2c83361f 728fb61f 2347161f ==> a080787e
40) bf83187e 2cb71961 3022d62a 81eb762a 9ee8162a ==> e38c300c

But also what catches my eye now is that /a/ is alternating somehow on
the most significant bit.

Well this change of the seeding has no negative effect on the randomness
and the output still passes off test without failure.

negative effect on the output.

Cheers,
Karl-Uwe

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to rsharris.bx.psu.edu@gmail.com on Thu Oct 8 18:56:20 2015
On 07.10.15 04:13, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank wrote:

Sorry for the scattered posting, my news client messed it up somehow.
Here it comes again, hopefully intact no.

-----------------------------------------------

By the way, if the setup is like below we can see that the output will
quickly recover into a useful state
a=t=1, b=c=d=0

I don't understand the table of bytes you printed out. Maybe you are
only looking at the output? But that can't be it, because your first
post said it was a 32-bit generator.

What I see for that initial state ... after 40 steps what I see is
that b and c are beginning to look random to the eyeball. But d,t,a
have managed to hold onto most of the zeros. Looks like it takes around 150
steps to get a 1 into the most significant bit of a.

n d t a b c
0 00000000 00000000 00000001 00000001 00000000
....
40 000004F5 000003A8 000000B0 8025E405 BC80A0B0

I like to apologise for not understanding the importance of looking at
the internal state, as you pointed out here. Obviously this reveals a
certain possibility that the output is not of good quality if the PRNG
is not seeded properly. Which of course can happen, if for example the
user just seed the PRNG with >0 <32bit only, or for real even with 0 -
what really seems to happen, as I have read in some forums discussions.

Now if we also start with c=1, we get an idea of what can happen
with b,c when a stays at zero. It quickly degenerates to a period-4 > loop. We
fall into another period-4 loop.

n d t a b c
0 00000000 00000001 00000000 00000000 00000001 (values here are in hex)
1 00000001 00000001 00000000 00000001 00002000
2 00000000 00000001 00000000 00002001 04002000
3 00000001 00000001 00000000 04000001 00002000
4 00000000 00000001 00000000 04002001 04002000
5 00000001 00000001 00000000 00000001 00002000

Regarding a=c=d=0, b=t=1 I can confirm the loop, but with a=c=d=0,b=t=37
it recovers after round about 100 draws

n d t a b c ==> output
0) 00000000 00000037 00000000 00000037 00000000 ==> 0006e000
1) 00000037 00000037 00000000 00000037 0006e000 ==> dc01e038
2) 00000001 00000038 00000001 0006e038 dc070001 ==> e006a001
3) 0000003a 00000039 00000001 dc01e03a 3c074001 ==> 3401003a
4) 00000005 0000003b 00000002 e006a03d d407a002 ==> 14092003
5) 00000040 0000003d 00000002 34010041 20082002 ==> 3001c0c2
6) 00000081 00000041 00000004 14092047 2408e004 ==> 0808a08b
...
24) 00000470 000005db 0000011d 08f285ea 50bd411d ==> a089259c
25) 000002eb 0000071b 00000140 584fc637 f8c6e140 ==> 8590eede
26) 00000747 00000872 00000157 a08928ce 2519c157 ==> 98f5ba7d
27) 000010c6 00000a03 00000191 8590eb2a 1d654191 ==> 2d6ff219
28) 00001cdc 00000c1a 00000217 98f5acd2 b59a4217 ==> d357a0fc
29) 000013c3 00000f17 000002fd 2d6ff1c2 fe3842fd ==> 258cd52e
30) 0000206f 000012b2 0000039b d357b6da f6db439b ==> bab72a3a
...
96) 3d54cb08 28229aba 059af1db 460ab472 5c2931db ==> 1613ec0a
97) 1cfbe9e5 2fa832ed 07859833 21a91ddc 2b411833 ==> 908fb879
98) 3bc1528a 3815aa6f 086d7782 13557d71 b81b9782 ==> ec56b5e4
99) 0e207afb 42612c85 0a4b8216 b59a6d09 57eca216 ==> ce908c8a
100) 56fddc6b 4d1db272 0abc85ed ed33550c 755e05ed ==> ca9fb388
101) 2954e2e9 5a922742 0d7474d0 a5e1c5b1 462a94d0 ==> 2c67973d
102) 8285e192 69514329 0ebf1be7 f28a6d48 5c681be7 ==> f415a6ff
103) fea7edae 7c248e1c 12d34af3 c1b5c1a2 cb078af3 ==> cd4f91c3
104) 9d4bee12 96ed187c 1ac88a60 257ad5b1 757eaa60 ==> 4809804f
105) 2b59e03e b6a0024c 1fb2e9d0 6fb769a1 0ce709d0 ==> df6c7ad0
106) bf079b43 d7adbb1d 210db8d1 845e1942 e435f8d1 ==> 692c749c

[If we make these cool changes to the algorithm, and] if we seed the
PRNG [in some cool way] the whole output will stay unbiased for sure.

Clearly the algorithm need a tweak to cope with an improper seeding.

What I have done now is changing the code slightly this way

a = seed[0];
b = seed[1];
c = seed[2];
d = seed[3];

// a precaution for improper seeding
if (a==0) a = 2654435769;
if (b==0) b = a + (a<<27);
if (c==0) c = b + (b<<29);
if (d==0) d = c + (c<<31);

t = a + b + c + d;

If we start looking at the internal state and output after seeding with a=1,b=c=d=0 we can realise that it recovers very quickly

n d t a b c ==> output
0) a8000001 d8000004 00000001 08000001 28000001 ==> 55402006
1) 75400006 dd400005 05400001 25400001 05402001 ==> d4ea0004
2) b0ea0004 e62a0006 08ea0001 28ea2001 4cea2001 ==> 2f317003
3) 65315003 f49b5007 0e715001 72715001 38717001 ==> 8834da85
4) a344da85 06362a88 119ada81 5b9afa81 70eafa81 ==> 48dd5162
5) bc27f162 1ceb2bdd 16b50155 42250155 b6dfa155 ==> 9441bb9f
6) bd631b9f 39816cbd 1c9640e0 1190e0e0 38b240e0 ==> 4d78f0de
7) a763d0de 5c02c679 228159bc 4ba3f9bc a1b8d9bc ==> 280eaee9
8) 231d8ee9 83bf3ebb 27bc7842 11d79842 1ac4b842 ==> c3fc150b
9) c978150b ac94a374 28d564b9 33e884b9 396c84b9 ==> 7f65bbe0
10) 950ddbe0 dbb5c8d5 2f212561 39a52561 d3cd4561 ==> eee1c775
11) 8281a775 0f7f5d15 33c99440 1e31f440 72519440 ==> 99ef9bdb
12) c5dc9bdb 475cfe90 37dda17b a43e017b f80d017b ==> 7464cba4
13) c08ceba4 856984e9 3e0c8659 9a3f8659 2ed7a659 ==> 14c8fd03
14) 89f65d03 c97a729f 4410edb6 f8f90db6 65c7adb6 ==> 5d07f03a

Now a seeding with a=b=c=d=0 will give us

n d t a b c ==> output
0) 063779b9 90dde6e4 9e3779b9 663779b9 863779b9 ==> 8e2314e3
1) 3553d4e3 2f471c6a 9e693586 7e693586 c519f586 ==> d3357cb6
2) ba289cb6 cf5af097 a013d42d 5b84942d 3299742d ==> 11522533
3) 1b578533 754009a9 a5e51912 0f02f912 05075912 ==> f17521d5
4) 14d761d5 1bffdee4 a6bfd53b b0c5753b 5567353b ==> fae82f7a
5) b68f4f7a c3666f2d a7669049 8d08d049 c16fb049 ==> 20f5cb1b
6) 23042b1b 708179f1 ad1b0ac4 f9826ac4 fa738ac4 ==> fc2bdf06
7) 01b87f06 1eb4a60d ae332c1c b2250c1c 4fb6ac1c ==> 26da291f
8) cd4dc91f ccf59621 ae40f014 abd49014 40437014 ==> 0a565d9a
9) b663bd9a 81a0f47d b4ab5e5c a0433e5c 1c76de5c ==> c152e62f
10) f221c62f 3bff70c5 ba5e7c48 76945c48 45e77c48 ==> 69924163
11) 8bce4163 fdeefb3e c1ef8a79 f562aa79 173eaa79 ==> 911936e1
12) 3c6eb6e1 c43cf7c2 c64dfc84 a8a9fc84 05de7c84 ==> 5353935e
13) c083b35e 8c6e69fd c831723b 75a8f23b e678d23b ==> fd16ea78
14) 1b236a78 5aa3f9d2 ce358fd5 6205afd5 84302fd5 ==> f1b8bed2
...
24) 6a0ce114 ff1f2aab f0ca1236 bf1df236 af10d236 ==> 6a4be4fd
25) 892e44fd f339a3e9 f41a793e 0427993e e742393e ==> 8062d279
26) 727bd279 eb9d8f4e f863eb65 dbc98b65 29d08b65 ==> 6ef8272f
27) 95de272f e7955946 fbf7c9f8 ee10c9f8 1536c9f8 ==> 1132599a
28) 72f2399a e83c1477 00a6bb31 fbccbb31 980cdb31 ==> 212f3aea
29) 9f0c7aea ec7a6174 043e4cfd 67feacfd d9ddecfd ==> fca40c72
30) 7caccc72 f5b11248 0936b0d4 c759f0d4 475130d4 ==> b31fd571
31) 9639f571 02cd297f 0d1c1737 8d24d737 a802f737 ==> 029ce2f0
32) a6c2c2f0 149b1061 11cde6e2 36f406e2 92aa26e2 ==> 289ccf8a
33) c95dcf8a 2b9f0d5a 1703fcf9 bb621cf9 5aa31cf9 ==> e5a3ce45
34) 0011ae45 48edf8cf 1d4eeb75 ff0feb75 1abd8b75 ==> 3d264f71
35) 664bcf71 663d71b6 1d4f78e7 0301d8e7 586c58e7 ==> 5079d629
36) 20f89629 86bf4918 2081d762 7bef5762 0b6e1762 ==> 28d05b44
37) c7d17b44 a848e52b 21899c13 920adc13 7d0bfc13 ==> d16d465c
38) 9761c65c d0110d18 27c827ed 16c947ed 50c5c7ed ==> 223ca163
39) 73f40163 fc944337 2c83361f 728fb61f 2347161f ==> a080787e
40) bf83187e 2cb71961 3022d62a 81eb762a 9ee8162a ==> e38c300c

But also what catches my eye now is that /a/ is alternating somehow on
the most significant bit.

Well this change of the seeding has no negative effect on the randomness
and the output still passes off test without failure.

negative effect on the output.

Cheers,
Karl-Uwe

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to William Unruh on Thu Oct 8 14:42:21 2015
On 08.10.15 12:53, William Unruh wrote:
On 2015-10-07, Karl-Uwe Frank<karl.frank@freecx.co.uk> wrote:
On 07.10.15 04:13, rsharris.bx.psu.edu@gmail.com wrote:
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank
wrote:
You're for sure not talking about the degenerate states like b=t=1,
a=c=d=0 c=t=1, a=b=d=0 d=t=1, a=b=c=0 are you?

Yeah, why wouldn't I? (The question is rhetorical)

For that reason I stated in the source code that the variables
a,b,c,d should not be initialised with all zero and should at least
differ by 1 bit. Perhaps forgot to mention this in my initial
posting.

On a related note, I had this experience about 20 years ago where I
wrote a tool and a coworker complained it didn't work right when he
used it. I noticed he was using it for a situation it didn't
support, and I said "it says right in the source code it doesn't work
for that". Then it dawned on me that the source code is just about
the last place I should expect him to go to find out what's supported
and what isn't.

Just came across this comment regarding the Mersenne-Twister

"Finally, MT had some problems when badly initialized: it tended to draw
lots of 0, leading to bad quality random numbers. This problem could
last up to 700,000 draws before being compensated by the recurrence of
the algorithm."

And on WikiPedia it reads that, if the MT is badly initialised

"It can take a long time to start generating output that passes
randomness tests, if the initial state is highly non-random -
particularly if the initial state has many zeros."

and

"It passes most, but not all, of the stringent TestU01 randomness tests."

On the German WikiPedia it reads that it's recommended to drop the first
800,000 outputs if the MT is initialised with only 1 bit and all the
rest zero.

In contrast my first posted algorithm will recover far more quickly, if
initialised with a=1, b=c=d=0.

My question now: is there any known RNG around that passes all TestU01
randomness test and which can be seeded with all zero?

Does MT work with all 1 bits? In which case the algorithm could be
MT with the seed being BITWISENOT of the entered seed. Of couser that
would then be bad for all 1 entered:-)
Ie, you need to specify what you need better. You want something with no
week keys, or is all 0 somehow special for you?

I suppose what is meant in the German WikiPedia article is that, if 623 elements of the array for the state vector N are set to zero and only
the first to 1 MT needs a huge amount of circles in order to produce a
useful output.

What I am looking for is, if it is possible to initialise any known good
PRNG with all seed variables = 0? I suppose this might be impossible.
Also, like for MT, seeding a PRNG with only one seed var with 1 and the
rest with 0 might not produce a useful output right away.

0 is somehow special, because I try to improve my current algorithm the
way that even if seeded with a=b=c=d=0 it should recover fast. At the
moment I'm verifying such a simple improvement and post the results
alter today.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to Karl-Uwe Frank on Sun Oct 11 01:17:29 2015
On 09.10.15 00:33, Karl-Uwe Frank wrote:

Because I like to have a jump start of the PRNG right away after seeding
I'm currently considering and testing a new version this way

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 = 0;
}

// The PRNG Function
uint32_t bcd32_ctr() {
a = a + (d >> 5) + (ctr ^ 2654435769);
b = a + (b ^ c);
c = a + (b << 13);
d = a + (d ^ t);
t = a + t;
ctr++;

return (b ^ c ^ d);
}

Nope, this version fail on smallcrush, Crush and BigCrush. Just two examples

a = 798188723, b = 1975008299, c = 309749614, d = 461402170, t =
3544348806, ctr = 0

========= Summary results of Crush =========

Version: TestU01 1.2.3
Generator: bcd32 32-bit
Number of statistics: 144
Total CPU time: 01:23:11.18
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):

Test p-value
----------------------------------------------
35 Run of U01, r = 0 0.9992
----------------------------------------------
All other tests were passed

a = 798188723, b = 1975008299, c = 309749614, d = 461402170, t =
3544348806, ctr = 222821873

========= Summary results of BigCrush =========

Version: TestU01 1.2.3
Generator: bcd32 32-bit
Number of statistics: 160
Total CPU time: 09:34:54.83
The following tests gave p-values outside [0.001, 0.9990]:
(eps means a value < 1.0e-300):
(eps1 means a value < 1.0e-15):

Test p-value
----------------------------------------------
41 Permutation, t = 5 5.8e-4
----------------------------------------------
All other tests were passed

Currently testing a slightly different version.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to Karl-Uwe Frank on Fri Oct 9 00:33:33 2015
On 08.10.15 18:56, Karl-Uwe Frank wrote:

Clearly the algorithm need a tweak to cope with an improper seeding.

What I have done now is changing the code slightly this way

a = seed[0];
b = seed[1];
c = seed[2];
d = seed[3];

// a precaution for improper seeding
if (a==0) a = 2654435769;
if (b==0) b = a + (a<<27);
if (c==0) c = b + (b<<29);
if (d==0) d = c + (c<<31);

t = a + b + c + d;

Apparently this tweak of the seeding routine does not solve the problem
when seeded with values like a=1, b=2, c=3, d=4

n d t a b c ==> output
0) 00000004 0000000a 00000001 00000002 00000003 ==> 0000400c
1) 0000000f 0000000b 00000001 00000002 00004001 ==> 0800c000
2) 00000005 0000000c 00000001 00004004 08008001 ==> 1000000d
3) 0000000a 0000000d 00000001 0800c006 1800c001 ==> 10010001
4) 00000008 0000000e 00000001 10000008 00010001 ==> 3000400c
5) 00000007 0000000f 00000001 1001000a 20014001 ==> 3801c004
6) 00000009 00000010 00000001 3000400c 08018001 ==> 00000015
7) 0000001a 00000011 00000001 3801c00e 3801c001 ==> 0002001d
8) 0000000c 00000012 00000001 00000010 00020001 ==> 4000400c
9) 0000001f 00000013 00000001 00020012 40024001 ==> 4802c018
10) 0000000d 00000014 00000001 40004014 08028001 ==> 1000000d
11) 0000001a 00000015 00000001 4802c016 5802c001 ==> 10030009
12) 00000010 00000016 00000001 10000018 00030001 ==> 7000401c

nor does it solve the alternating of the most significant bit of /a/

Because I like to have a jump start of the PRNG right away after seeding
I'm currently considering and testing a new version this way

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 = 0;
}

// The PRNG Function
uint32_t bcd32_ctr() {
a = a + (d >> 5) + (ctr ^ 2654435769);
b = a + (b ^ c);
c = a + (b << 13);
d = a + (d ^ t);
t = a + t;
ctr++;

return (b ^ c ^ d);
}

Which gives with a=1, b=2, c=3, d=4

n d t a b c ==> output
0) 00000004 0000000a 00000001 00000002 00000003 ==> 8d6ed9c9
1) 9e3779c8 9e3779c4 9e3779ba 9e3779bb 8d6ed9ba ==> 9e922f4d
2) 4160af4c df982904 4160af40 54ba4f41 8b48cf40 ==> d67ff4be
3) 809bb4bd c13b5779 e1a32e75 c195ae76 9771ee75 ==> e3d9c99b
5) a8ddb7b2 6d5de02a 284302dd 4e9ca2e0 bc9f02dd ==> 4197012b
6) 9141c1ee 391f4a80 cbc16a56 bdc50a93 6d13ca56 ==> 8d58dd5f
7) 16e17d92 a7a23ca4 6e82f224 3f59b2e9 a4e01224 ==> 671b7651
8) beb4b904 b513b472 0d7177ce a92b189b 7084d7ce ==> 4879d566
9) bd45a4bd 66b24bb9 b19e9747 8b4e669c 7e721747 ==> 90fb9ccb
10) 31b82d20 bc7289d5 55c03e1c 4afcaff7 ebbf1e1c ==> 0f70ec36
11) 83501e2d b1f8030d f5857938 96c92b23 1ae9d938 ==> 4d11c6d6
12) ca7f90fb 49cf76e8 97d773db 23f865f6 a49633db ==> 67a9fa79

and with a=0, b=0, c=0, d=0

n d t a b c ==> output
0) 00000000 00000000 00000000 00000000 00000000 ==> 8d6e99b9
1) 9e3779b9 9e3779b9 9e3779b9 9e3779b9 8d6e99b9 ==> 86924f3e
2) 4160af3e df9828f7 4160af3e 54ba8f3e 93486f3e ==> 8a7cd63b
3) 809bb63b c13b5769 e1a32e72 a9960e72 a3716e72 ==> 2bdda72f
4) c580672f 451add46 83df85dd 8ec6e5dd 609b25dd ==> fee01d3c
5) a8ddbd3c 6d5de019 284302d3 16a0c2d3 409d62d3 ==> 1daea79d
6) 9141c79d 391f4a91 cbc16a78 21ff0a78 ad106a78 ==> 55427f7f
7) 16e17f7f a7a23d04 6e82f273 fb725273 b8d15273 ==> 73d63aa7
8) beb4baa7 b513b530 0d71782c 5114782c 9c76f82c ==> 16d06749
9) bd45a749 66b24ce2 b19e97b2 7f0117b2 d494d7b2 ==> 257e6a47
10) 31b82a47 bc728b7e 55c03e9c 0155fe9c 1593be9c ==> e5a23ada
11) 83501ada b1f8051f f58579a1 0a4bb9a1 6cb999a1 ==> feea93ee
12) ca7f93ee 49cf7948 97d77429 fec99429 ca5c9429 ==> 8956b523

Furthermore it eliminate the annoying alternating of the most
significant bit of /a/.

And for real, I like it better it the user can decide how he seed the
PRNG. As for the statistical tests, it behaves quite very well all the way.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Karl-Uwe Frank@21:1/5 to All on Fri Oct 2 11:51:13 2015
Out of curiosity and inspired by a recent question here on sci.crypt.random-numbers I tried to design a 32 bit PRNG that only uses
cheap operations like bitwise shift operations, additions and XOR. It
should also, in contrast to xorshift128, pass all statistical tests
without failure and should be 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 testsuite TestU01, which are SmallCrush, Crush and BigCrush.

One further difference to xorshift128 is, that the internal state of 160
bit will stay unknown after seeding with 128 bit.

This is the formulae as ANSI-C snippet
[code]uint32_t a, b, c, d, t;

a = 1747968903;
b = 537061761;
c = 523248786;
d = 296811837

t = a + b + c + d;

uint32_t bcd32() {

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

return (b ^ c ^ d);
}[/code]

Some test results

[code]
a = 1, b = 2, c = 3, d = 4

# Testsize 2**30 bit (128 MB)

./bcd32_BitStat 30 0 | BitStatistic/ent
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 536870912 byte file by 0 percent.

Chi square distribution for 536870912 samples is 270.82, and randomly
would exceed this value 23.70 percent of the times.

Arithmetic mean value of data bytes is 127.5036 (127.5 = random).
Monte Carlo value for Pi is 3.141336781 (error 0.01 percent).
Serial correlation coefficient is -0.000000 (totally uncorrelated = 0.0).

-----------------------------------------------------------------------------------

a = 219324720, b = 1108630788, c = 1189532544, d = 1548197085

# Testsize 2**30 bit (128 MB)

./bcd32_BitStat 30 65432912 | BitStatistic/ent
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 536870912 byte file by 0 percent.

Chi square distribution for 536870912 samples is 245.69, and randomly
would exceed this value 65.08 percent of the times.

Arithmetic mean value of data bytes is 127.5015 (127.5 = random).
Monte Carlo value for Pi is 3.141296860 (error 0.01 percent).
Serial correlation coefficient is -0.000033 (totally uncorrelated = 0.0).

-----------------------------------------------------------------------------------

# Seed = 3674308604 | a = 1064954296, b = 1558138774, c = 1222783100, d
= 2044543557, t = 1595452431

nice -n 19 ./TestU01_bcd32 -c 0xdb017ffc 3>&1 2>&3- | tee Crush.txt

========= Summary results of Crush =========

Version: TestU01 1.2.3
Generator: bcd32 32-bit
Number of statistics: 144
Total CPU time: 01:17:23.18

All tests were passed

# Seed = 167813656 | a = 798087881, b = 280156805, c = 1311267411, d
= 994191163, t = 3383703260

nice -n 19 ./TestU01_bcd32 -c 0x0a00a218 3>&1 2>&3- | tee Crush.txt

========= Summary results of Crush =========

Version: TestU01 1.2.3
Generator: bcd32 32-bit
Number of statistics: 144
Total CPU time: 01:13:08.81

All tests were passed

# Seed = 2028375283 | a = 1747968903, b = 537061761, c = 523248786, d
= 296811837, t = 3105091287

nice -n 19 ./TestU01_bcd32 -c 0x78e68cf3 3>&1 2>&3- | tee Crush.txt

========= Summary results of Crush =========

Version: TestU01 1.2.3
Generator: bcd32 32-bit
Number of statistics: 144
Total CPU time: 01:12:32.73

All tests were passed

nice -n 19 ./TestU01_bcd32 -b 0x78e68cf3 3>&1 2>&3- | tee BigCrush.txt

========= Summary results of BigCrush =========

Version: TestU01 1.2.3
Generator: bcd32 32-bit
Number of statistics: 160
Total CPU time: 08:26:48.66

All tests were passed[/code]

The source code for these tests can be found here [url]http://www.freecx.co.uk/bcd32/[/url]

Cheers,
Karl-Uwe

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

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