c = a + (b << 13);
On Friday, October 2, 2015 at 5:51:16 AM UTC-4, Karl-Uwe Frank wrote:Yes c = a + (b << 13); is correct. The reason is that I like to
c = a + (b<< 13);
Is that correct, or should it be c = a + (c<< 13) ?
Bob H
... Do you suppose that it should be always the previous value that is used to calculate the new one?
On 05.10.15 21:08, I wrote:the b,c generator is invertible.
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
(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
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.my head around whether the b,c part can be inverted.
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
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)?
Thanks a lot for your rely. I will have a closer look at that a=b=c=d=0
and t=1 state.
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
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
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
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
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?
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.
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
[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.
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.
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.
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 FrankJust came across this comment regarding the Mersenne-Twister
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.
"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 ---
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 forMany thanks for having a look at the algorithm and sharing your
me. Good luck with it.
Bob H
On Tuesday, October 6, 2015 at 4:26:20 PM UTC-4, Karl-Uwe Frank wrote:only looking at the output? But that can't be it, because your first
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
What I see for that initial state ... after 40 steps what I see isthat 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
n d t a b c
0 00000000 00000000 00000001 00000001 00000000
....
40 000004F5 000003A8 000000B0 8025E405 BC80A0B0
Now if we also start with c=1, we get an idea of what can happenb,c when a stays at zero. It quickly degenerates to a period-4 loop. We
with
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
[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.
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
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
[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.
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 FrankJust came across this comment regarding the Mersenne-Twister
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.
"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?
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);
}
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;
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 293 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 227:26:16 |
| Calls: | 6,624 |
| Calls today: | 6 |
| Files: | 12,171 |
| Messages: | 5,318,856 |