calling a function in a FOR loop. the function has the following
lines:
clock_gettime(CLOCK_REALTIME, &time_stamp);
srand(time_stamp.tv_nsec);
the idea is each time it is called the random number generator is
seeded with the current nanosecond counter.
the program causes a seg fault when running in linux after 2 loops,
but not in cygwin. when the two lines are commented out, the code runs
fine in both.
any ideas why? or could the problem actually be somewhere else?
thanks!
johnty
Try adding a srand(1) to the program after the call to srand. That
will help to keep the program deterministic, which might uncover the
problem.
However the root of the problem might be elsewhere. Once you have a
loose pointer, anything can happen. Commenting out the code could
change the layout of variables in memory so the losse pointer hits
something different, which doesn't raise the segfault.
I can't reproduce your segfault on linux (Ubuntu, 2.6.31, SMP). Your
problem probably lies somewhere else. A complete snippet and/or a
relevant backtrace/error log would be more helpful.
I hope that in your actual code you cast the long value to unsigned in
the srand() call above.
> the idea is each time it is called the random number generator is
> seeded with the current nanosecond counter.
>
> the program causes a seg fault when running in linux after 2 loops,
> but not in cygwin. when the two lines are commented out, the code runs
> fine in both.
>
> any ideas why? or could the problem actually be somewhere else?
With the information given, one can't really say. Can you provide a
minimal program that exhibits your problem? Or atleast the full source
for the function that contains the above loop?
> i'm facing a rather baffling problem:
>
> calling a function in a FOR loop. the function has the following
> lines:
>
> clock_gettime(CLOCK_REALTIME, &time_stamp);
> srand(time_stamp.tv_nsec);
The tv_nsec field is a long, but srand() expects an int; that may matter
on a 64-bit system if the prototype for srand() isn't in scope (although
it's unlikely to result in a segfault).
OTOH, if the prototype for srand() is in scope, you should have gotten a
warning. Turn up the compiler's warning level (use at least -Wall) and
ensure that the program compiles without warnings.
> or could the problem actually be somewhere else?
Quite possibly.
man its really early in the morning... i didn't quite say it right.
(but have a feeling the replies are pointing in the right direction)
instead of:
>the program causes a seg fault when running in linux after 2 loops,
>but not in cygwin. when the two lines are commented out, the code runs
>fine in both.
what i meant to say was:
in linux, the seg fault happens when the lines are COMMENTED OUT,
while in windows it can run with or without it.
i'm also using the same two lines of code elsewhere without problems.
so it makes me think it could be a loose pointer somewhere else...
> clock_gettime(CLOCK_REALTIME, &time_stamp);
> srand(time_stamp.tv_nsec);
>
> the idea is each time it is called the random number generator is
> seeded with the current nanosecond counter.
This is a bad idea. Basically this resets the seed to a predictable value,
which makes the generated numbers as well predictable. This is also clearly
stated in the documentation:
man clock_getres(3)
| The resolution of clocks depends on the implementation and cannot be
| configured by a particular process. If the time value pointed to by the
| argument tp of clock_settime() is not a multiple of res, then it is
| truncated to a multiple of res.
Or in other words: The entropy of the RT clock is to be considered low.
The standard PRNG that comes with most C standard libraries isn't very good,
but even a PRNG suitable for cryptographic applications would produce very
low quality randomnes if used that way.
> the program causes a seg fault when running in linux after 2 loops,
> but not in cygwin. when the two lines are commented out, the code runs
> fine in both.
Hard to tell without a look at the full code. It might be anything and not
be related to the query of the RT clock at all. A little bit more of
context, i.e. some working (or in this case breaking) minimal full program
source would help.
> or could the problem actually be somewhere else?
Possibly.
Wolfgang
> The standard PRNG that comes with most C standard libraries isn't very good,
odd isn't it? I'm told in another thread that the typical C library
is of such high quality that I'd be mad to use anything else. Whilst
here I'm told the PRNGs of the typical C library are poor. Is the
definition of srand/rand too restrictive?
Depends on the implementation on your C library, and you'd be mad to
use the one in the C library unless you understood its properties, and
the precise problem you're trying to solve.
As an example, many implementations aren't even suitable for simulating
the shuffling of a deck of cards.
B.
> i'm facing a rather baffling problem:
>
> calling a function in a FOR loop. the function has the following
> lines:
>
> clock_gettime(CLOCK_REALTIME, &time_stamp);
> srand(time_stamp.tv_nsec);
>
> the idea is each time it is called the random number generator is
> seeded with the current nanosecond counter.
Just a heads up: this is often the wrong way to use an RNG -- seeding
it once is usually the right thing to do. If the RNG is designed
well, that gives you the best period and the best chance of a good
distribution of results. Most RNGs are not designed to perform well
if they are repeatedly seeded with a monotone sequence like this
though it is possible that your application does not care, or that
your RNG happens to be one that is un-phased by this re-seeding.
> the program causes a seg fault when running in linux after 2 loops,
> but not in cygwin. when the two lines are commented out, the code runs
> fine in both.
>
> any ideas why? or could the problem actually be somewhere else?
It's impossible to say (at least for me). I'd use valgrind if you are
able to. If the code is shortish (and you are permitted to show it)
posting it here might help.
--
Ben.
srand() takes an unsigned int, not an int.
> OTOH, if the prototype for srand() is in scope, you should have gotten a
> warning. Turn up the compiler's warning level (use at least -Wall) and
> ensure that the program compiles without warnings.
With a prototype in scope, the long value is converted to
unsigned int "as if by assignment." No diagnostic is required,
although (as always) the compiler is free to issue whatever
non-required diagnostics it wants to. The gcc compiler version
on my system does not issue diagnostics for this situation even
with -Wall; you need -Wconversion or -Wsign-conversion to get one.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Since the sequence generated by rand() depends entirely
on the seed provided by srand(), and since the argument to
srand() is an unsigned int, it follows that rand() can produce
no more than UINT_MAX+1 different sequences. That could be as
few as 65536, or more typically 4294967295.
Four billion sequences may sound like a lot, but consider:
You can shuffle a deck of fifty-two cards in 52! ~= 8e67 ways,
which is 2e58 times four billion ... Heck, you can shuffle
the thirteen cards of just one suit in more than four billion
ways.
--
Eric Sosman
eso...@ieee-dot-org.invalid
> odd isn't it? I'm told in another thread that the typical C library
> is of such high quality that I'd be mad to use anything else.
The C standard library covers a wide field: Memory management, basic
algorithms, string manipulation, math functions.
It's also important to define the metric by which you measure quality. Is it
quality of the code, the overall implementation or the used algorithms.
IMHO the API of the standard libarary is quite poor. If you worked with
things like libowfat/libdjb then everytime you got to use the "normal"
functions is a really painful time (but that's really IMHO).
> Whilst here I'm told the PRNGs of the typical C library are poor. Is the
> definition of srand/rand too restrictive?
If you just need a small set of arbitrarily looking numbers or simply some
random 15 bits to select an IP source port, then srand/rand will do fine. As
soon you need a few thousand bits of randomnes for cryptography, numerical
simulation, something like that, then your typical C standard library PRNG
just sucks.
Wolfgang
That's a great example, actually. Just to add to that, rand() is also
not reentrant or thread-safe, and it's documented (at least on Linux
and BSD) to provide lower-order bits of less randomness than the high-
order bits.
The problem is in using words with very little absolute meaning, such as
"good" and "poor" and trying to derive meaning from the surrounding words.
One person's good is another persons poor.
In the case of PRNGs in particular this is compounded by a lot of war
stories on the subject. I personally experienced one of the bad ones quite
some time back and it gave me fits in a simulation I was writing. . I don't
condemn modern cars because of some of the hideous things that happened to
me over the years with old cars, likewise I don't automatically condemn
PRNGs.
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?
--
Bartc
> 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?
Something like that yes. What you do is concatenating the bits of the
repeated output of, say a 32 bit PRNG. This introduces some tricky part...
The quality of a PRNG is measured by its
* periodicy, that is the number of taken values until it's repeating
totally. Be aware that there is no /theoretical/ upper limit to this.
No matter if the numbers generated are 8, 256, 1024 or any other number
of bits; one may think the single numbers as just being sub-bits of a
really huge random number being generated, each iteration adding bits.
In practice every PRNG has a periodicy, determined by its algorithm.
* Uniformity of output distribution.
* Clustering (depending on the application one may want strong
clustering or none at all).
and
* dimensionality
The last part is the tricky one. A PRNG that creates a seemingly good
looking distribution in a single dimension may show some clear patterns or
clusters when collating a given number of sequential outputs into a vector.
The dimensionality of a PRNG is the minimal sequence length/vector dimension
for patterns/clusters showing up - ideally this would be infinite.
So far all C standard library PRNGs I encountered were quite limited,
showing patterns as early as 3 to 5 dimensions.
Wolfgang
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!
--
Ben.
Not really. It's just a historical quirk, partially added to by the fact
that C89's spec was misunderstood by some people to recommend a particularly
weak PRNG.
The key is that it's not that you should always use library functions, but
that you should rarely write your own when they exist. Sometimes you should,
however, get another library. :)
-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
Why? If <time.h> has been #included, the conversion will be done
implicitly.
[...]
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
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.)
...296, obviously. Sorry about that.
>> What's the answer then, use a 230-bit PRNG?
>
> 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.
--
Eric Sosman
eso...@ieee-dot-org.invalid
> 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
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.
--
Eric Sosman
eso...@ieee-dot-org.invalid
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
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.
[...]
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.
--
Eric Sosman
eso...@ieee-dot-org.invalid
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.)
<snip>
> "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
> On 2/10/2010 11:38 AM, Ben Bacarisse wrote:
>> "bartc"<ba...@freeuk.com> writes:
>>
>>> "Eric Sosman"<eso...@ieee-dot-org.invalid> wrote
>>>
>>>> Since the sequence generated by rand() depends entirely
>>>> on the seed provided by srand(), and since the argument to
>>>> srand() is an unsigned int, it follows that rand() can produce
>>>> no more than UINT_MAX+1 different sequences. That could be as
>>>> few as 65536, or more typically 4294967295.
>
> ...296, obviously. Sorry about that.
>
>>> What's the answer then, use a 230-bit PRNG?
>>
>> 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.
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.
--
Ben.
If you mean which episode, I have no idea; I've never actually seen
the show.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
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
> William Hughes <wpih...@hotmail.com> writes:
> > On Feb 10, 6:27 pm, Keith Thompson <ks...@mib.org> wrote:
> [...]
> >> "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?
>
> 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
"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'."
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
And if you like Nigel Hawthorn, get a hold the 79 TV movie
"The Knowledge".
--
Peter
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.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
Yup. Sorry.
<snip>
Thanks - William Hughes
or Canadian politics, (or I suspect anywhere with a
British Parliamentary tradition), or if you like
incredibly good comedies,
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.