seg fault in linux but not cygwin

[Keith Thompson]

It's also 2e48 times 18 trillion (that's the old trillion). So even 64-bits
doesn't 'cut' it.

What's the answer then, use a 230-bit PRNG?

There are PRNGs that have at least that much state. (I seem to recall
that the Mersenne Twister is a pretty good one, but I don't know the
details.)

 

[Eric Sosman]

...296, obviously. Sorry about that.

You may be conflating the number of initial states (and to some extent
the period) with the number of bits of output. A sequence of numbers
just 6 bits wide is adequate for shuffling a 52 card deck, but there
has to be sufficient initial state to be able to seed all (or at least
a good proportion of) the possible shuffles.

It is possible to have a 32-bit PRNG with thousands of bytes of state
and a huge period. Of course, the large state does not always
correspond to an equally huge set of possible sequences, but the two
are strongly correlated!

You may be conflating the size of the PRNG's expression of
its state with the "diversity" of that state. After srand(S)
for some value S, you can call rand() a bunch of times and get
some sequence of values. If you call srand(S) a second time,
rand() must then produce the same sequence of values again. That
is, there can be no more distinct rand() sequences than there can
be S values. It doesn't matter how many bits rand()/srand() use
internally: they can have no more than lg( | { all S } | ) bits
of independent information. (Well, rand() *can* keep bits that
don't derive from S -- but they mustn't affect the output.)

It is, indeed, possible for a small-state PRNG to have an
enormous period. But for rand(), the number of sequences --
and the number of starting points in the enormous periods --
cannot exceed 1+UINT_MAX. Even if the algorithm could do more
(given suitable seeds), the fact that srand() governs rand()
puts a hard limit on what can be done.

 

[William Hughes]

     It is, indeed, possible for a small-state PRNG to have an
enormous period.  But for rand(), the number of sequences --
and the number of starting points in the enormous periods --
cannot exceed 1+UINT_MAX.  Even if the algorithm could do more
(given suitable seeds), the fact that srand() governs rand()
puts a hard limit on what can be done.

There is a limit, but it is not hard. E.g.: Choose randomly
(e.g. seed your random number generator) some number, N,
of iterations. Now (independently) seed the random number
generator and run it kN times before using.
Then, assuming your generator
has sufficient state, you get more than 1+UINT_MAX
sequences. Of course if the sequences are longer than k
they will overlap (this may or may not be a problem). You can
"easily" add about 10 bits, after this time is a problem.
This is not a very practical solution, if you need more than
1+UINT_MAX starting points, do not use srand()/rand()

- William Hughes

 

[Eric Sosman]

There is a limit, but it is not hard. E.g.: Choose randomly
(e.g. seed your random number generator) some number, N,
of iterations. Now (independently) seed the random number
generator and run it kN times before using.

I'm having trouble understanding your suggestion. What
does it mean to seed "some number [...] of iterations?"
Maybe a few lines of pseudocode would clarify your meaning.

Then, assuming your generator
has sufficient state, you get more than 1+UINT_MAX
sequences.

Perhaps you and I mean different things by "sequences
generated by rand()." In my view, you call srand() and then
start calling rand() repeatedly, writing down all the numbers
rand() returns to you. The sequence is periodic (because our
computers can manage only a finite amount of state), even if
it may be extremely long. That's one "sequence," in my view,
and I still maintain there can be no more than 1+UINT_MAX of
them. srand() instructs rand() what sequence to deliver, and
srand() can only issue 1+UINT_MAX different instructions.

 

[William Hughes]

There is a limit, but it is not hard.  E.g.: Choose randomly
(e.g. seed your random number generator) some number, N,
of iterations.  Now (independently) seed the random number
generator and  run it kN times before using.

     I'm having trouble understanding your suggestion.  What
does it mean to seed "some number [...] of iterations?"
Maybe a few lines of pseudocode would clarify your meaning.

Then, assuming your generator
has sufficient state, you get more than 1+UINT_MAX
sequences.

     Perhaps you and I mean different things by "sequences
generated by rand()."  In my view, you call srand() and then
start calling rand() repeatedly, writing down all the numbers
rand() returns to you.  The sequence is periodic (because our
computers can manage only a finite amount of state), even if
it may be extremely long.  That's one "sequence," in my view,
and I still maintain there can be no more than 1+UINT_MAX of
them.  srand() instructs rand() what sequence to deliver, and
srand() can only issue 1+UINT_MAX different instructions.

Well, you only have one periodic sequence (though this
period may be very long) and 1+UINT_MAX different starting
points. You can get more than 1+UINT_MAX starting points
by starting at some "random" offset.

volatile temp;
long x;
uint ent1,ent2;
long k = 1000;

/*fill ent1 and ent2 independently*/

srand(ent1);
x=rand()%1000;

srand(ent2);
for(i=0;i< k*x; i++){
temp=rand();
}

/*now start using rand()*/

This sucks moonrocks, but it does get more than
1+UINT_MAX starting points from srand()/rand().
Of course you cant get very far until your busy
loop consumes too much time.

- William Hughes

 

[Keith Thompson]

Well, you only have one periodic sequence (though this
period may be very long) and 1+UINT_MAX different starting
points.

Not necessarily. There could be multiple independent sequences,
and the value passed to srand() chooses which of up to 1+UINT_MAX
sequences you're going to use. In a sufficiently insane
implementation, the seed could choose one of 1+UINT_MAX algorithms.

This would mean that the total cycle length is less than
2**STATE_BITS, and might even vary depending on which cycle you
choose, but that doesn't violate any requirements.

[...]

 

[Eric Sosman]

[...]
Well, you only have one periodic sequence (though this
period may be very long) and 1+UINT_MAX different starting
points. You can get more than 1+UINT_MAX starting points
by starting at some "random" offset.

volatile temp;
long x;
uint ent1,ent2;
long k = 1000;

/*fill ent1 and ent2 independently*/

srand(ent1);
x=rand()%1000;

srand(ent2);
for(i=0;i< k*x; i++){
temp=rand();
}

/*now start using rand()*/

This sucks moonrocks, but it does get more than
1+UINT_MAX starting points from srand()/rand().
Of course you cant get very far until your busy
loop consumes too much time.

Aha! Thanks for the clarification -- but it's hardly
surprising that srand()/rand() plus an additional source of
entropy ("fill ent1 and ent2 independently") can do more than
the functions unaided.

 

[William Hughes]

[...]

Well, you only have one periodic sequence (though this
period may be very long) and 1+UINT_MAX different starting
points.

Not necessarily.  There could be multiple independent sequences,
and the value passed to srand() chooses which of up to 1+UINT_MAX
sequences you're going to use.  In a sufficiently insane
implementation, the seed could choose one of 1+UINT_MAX algorithms.

Indeed. (Put differently, a random number generator
must repeat after 2**STATE_BITS steps, but might have
a much shorter period, and may have multiple independent
series.)

"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

I love this quote. Which show is it from?

- William Hughes

 

[Ben Bacarisse]

...296, obviously. Sorry about that.


You may be conflating the size of the PRNG's expression of
its state with the "diversity" of that state.

I don't think I am though, as always, I think I could have been
clearer. In particular I was talking about PRNGs in general, not
simply those limited to the srand interface. A PRNG with a large
state and narrow seed interface (like srand) is an example of the
exceptions described by the last sentence. The trailing "but the two
are strongly correlated!" is unhelpful and I should have stopped 5
words sooner.

After srand(S)
for some value S, you can call rand() a bunch of times and get
some sequence of values. If you call srand(S) a second time,
rand() must then produce the same sequence of values again. That
is, there can be no more distinct rand() sequences than there can
be S values. It doesn't matter how many bits rand()/srand() use
internally: they can have no more than lg( | { all S } | ) bits
of independent information. (Well, rand() *can* keep bits that
don't derive from S -- but they mustn't affect the output.)

Yes, I get that. Well most of it. The very last part I am not sure
about. Reading 7.20.2.2 p2 closely reveals what may be a deliberate
loophole:

"The srand function uses the argument as a seed for a new sequence
of pseudo-random numbers to be returned by subsequent calls to
rand."

OK, that does not say the seed entirely determines the sequence, just
that it is used as a seed in some (as yet unspecified) way. Let's
imagine an srand that pulls in more random bits from a hardware source
and uses both the supplied seed and the extra bits for the internal
state of the PRNG. The paragraph continues:

"If srand is then called with the same seed value, the sequence of
pseudo-random numbers shall be repeated."

This is odd wording. The "then", "same" and "repeated" suggests that
the requirement to duplicate the sequence applies only to seeds used
previously. If so, srand needs only to store the random bit pulled in
for each seed used so far and it can meet this requirement while using
more bits than were supplied in the seed. Finally:

"If rand is called before any calls to srand have been made, the
same sequence shall be generated as when srand is first called with
a seed value of 1."

I think this means that a seed of 1 fully determines the sequence so
we have to special-case this seed -- no extra bits can be used.

It is, indeed, possible for a small-state PRNG to have an
enormous period. But for rand(), the number of sequences --
and the number of starting points in the enormous periods --
cannot exceed 1+UINT_MAX. Even if the algorithm could do more
(given suitable seeds), the fact that srand() governs rand()
puts a hard limit on what can be done.

Such an srand could get round the hard limit, but would it be
conforming? I would not bet the house on it, but it seems to fit the
letter of the standard.

 

[Michael Foukarakis]

It's also 2e48 times 18 trillion (that's the old trillion). So even 64-bits
doesn't 'cut' it.

What's the answer then, use a 230-bit PRNG?

Possible ways to shuffle a deck = 52! ~= 8 * 10^67 ~= 2^3 × 2^3*67 ~=
2^603

 

[Moi]

Possible ways to shuffle a deck = 52! ~= 8 * 10^67 ~= 2^3 × 2^3*67 ~=
2^603

~= 2^220

3.x bits are needed per decade.
Other method: count in binary.

counting bits to encode the deck:

52 .. 32 : 6 bits * 21 items 126
31 .. 16 : 5 bits * 16 items 80
16 .. 8 : 4 bits * 8 items 32
8 .. 4 : 3 bits * 4 items 12
4 .. 2 : 2 bits * 2 items 4
2 .. 1 : 1 bits * item 1 (redundant!)

Total: 254 bits

HTH,
AvK

 

[Richard Bos]

If you mean which episode, I have no idea; I've never actually seen
the show.

If you are at all interested in British politics - or even in Great
Britain, or in politics - do so as soon as you can.

Richard

 

[Peter Nilsson]

If you are at all interested in British politics - or even
in Great Britain, or in politics - do so as soon as you can.

And if you like Nigel Hawthorn, get a hold the 79 TV movie
"The Knowledge".

 

[Keith Thompson]

"Yes Prime Minister", Series Two, Episode 5, "Power to the People".

Sir Arnold Robinson: "He's suffering from politicians' logic."
Sir Humphrey Appleby: "'Something must be done; this is something;
therefore, we must do it'."

You mean I've had the quote wrong all these years?

Initially I didn't have an attribution, because I wasn't sure
where it came from; I had just heard it somewhere. It's possible
I got it from somewhere else, and the writers of "Yes Minister"
either adapted it from the same source or came up with something
similar independently.

 

[William Hughes]

"Yes Prime Minister", Series Two, Episode 5, "Power to the People".

Thanks - William Hughes

 

[William Hughes]

If you are at all interested in British politics

or Canadian politics, (or I suspect anywhere with a
British Parliamentary tradition), or if you like
incredibly good comedies,

 

[Nick Keighley]

If you are at all interested in British politics - or even in Great
Britain, or in politics - do so as soon as you can.

apparently both Margaret Thatcher (right wing politician) and Tony
Benn (left wing politician) who had both tangled with the foot
dragging ways of the British civil service thought that the program
was great and very true to life. It has also exported remarkably well.