faqcat1067.html

this is a mirrored site c-faq. thought might need offline

	tm2.tm_mon = 3 - 1;
	tm2.tm_mday = 1;
	tm2.tm_year = 2000 - 1900;
	tm2.tm_hour = tm2.tm_min = tm2.tm_sec = 0;
	tm2.tm_isdst = -1;

	t1 = mktime(&tm1);
	t2 = mktime(&tm2);
	
	if(t1 == -1 || t2 == -1)
		fprintf(stderr, "mktime failed\n");
	else {
		long d = (difftime(t2, t1) + 86400L/2) / 86400L;
		printf("%ld\n", d);
	}
</pre>
(The addition of <TT>86400L/2</TT> rounds the difference to the 
nearest day;
see also question <a href="faqcat973e.html?sec=fp#round">14.6</a>.)
</p><p>Another approach to both problems,
which will work over a much wider range of dates,
is to use
``Julian day numbers''.
A
Julian day number is the



number of days since January 1, 4013 BC.

<a href="../../lib/julepoch.html" rel=subdocument>[footnote]</a>
Given <TT>ToJul</TT> and <TT>FromJul</TT> routines
declared as
<pre>
/* returns Julian for month, day, year */
long ToJul(int month, int day, int year);

/* returns month, day, year for jul */
void FromJul(long jul, int *monthp, int *dayp, int *yearp);
</pre>
adding <TT>n</TT> days to a date can be implemented as
<pre>
	int n = 90;
	int month, day, year;
	FromJul(ToJul(10, 24, 1994) + n, &amp;month, &amp;day, &amp;year);
</pre>
and the number of days between two dates is
<pre>
	ToJul(3, 1, 2000) - ToJul(2, 28, 2000)
</pre>
Code for handling
Julian day numbers
can be found in
the Snippets collection
(see question <a href="faqcatccbd.html?sec=resources#miscsrcs">18.15c</a>),
the Simtel/Oakland archives
(file JULCAL10.ZIP,
see question <a href="faqcatccbd.html?sec=resources#sources">18.16</a>),
and
the ``Date conversions'' article mentioned in the References.
</p><p>See also questions
<a href="faqcat1067.html?sec=lib#mktime">13.13</a>,
<a href="faqcat38c2.html?sec=misc#zeller">20.31</a>,
and
<a href="faqcat38c2.html?sec=misc#leapyear">20.32</a>.
</p><p>Additional links:
<br>
<br>




<a href="../../lib/yesterday.msb.html">further explanation</a> by Mark Brader
<br>
<br>




<a href="../../lib/calendar.br.html">more code</a>
for date-difference and day-of-week calculation
by Branko Radovanovic
</p>




<p>References:

K&amp;R2 Sec. B10 p. 256
<br>
ISO Secs. 7.12.2.2,7.12.2.3
<br>
H&amp;S Secs. 18.4,18.5 pp. 401-2
<br>
David Burki, ``Date Conversions''
<hr><hr><hr>
<a name="y2k">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/y2k.html"><!-- qtag -->Question 13.14b</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
Did C have any Year 2000 problems?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
No, although poorly-written C programs might have.
</p><p>The
<TT>tm_year</TT>
field of <TT>struct&nbsp;tm</TT>
holds the value of the year minus 1900;
this field therefore contains the value 100 for the year 2000.
Code that uses <TT>tm_year</TT> correctly
(by adding or subtracting 1900
when converting to or from human-readable 4-digit year representations)
has no problems at the turn of the millennium.
Any code that used <TT>tm_year</TT> incorrectly, however,
such as by
using it directly as a human-readable 2-digit year,
or setting it from a 4-digit year with code like
<pre>
	tm.tm_year = yyyy % 100;	/* WRONG */
</pre>
or printing it as an allegedly human-readable 4-digit year
with code like
<pre>
	printf("19%d", tm.tm_year);	/* WRONG */
</pre>
would have had
grave y2k problems indeed.

See also question <a href="faqcat38c2.html?sec=misc#leapyear">20.32</a>.
</p><p>(The y2k problem is now mostly old history;
all we have left to do
is fix all the 32-bit <TT>time_t</TT> problems by 2038...)

</p>


<p>References:

K&amp;R2 Sec. B10 p. 255
<br>
ISO Sec. 7.12.1
<br>
H&amp;S Sec. 18.4 p. 401
<hr><hr><hr>
<a name="rand">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/rand.html"><!-- qtag -->Question 13.15</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
I need a random number generator.
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
The
Standard
C library has one: <TT>rand</TT>.
The implementation on your system may not be perfect,
but writing a better one isn't necessarily easy, either.

</p><p>
If
you do find yourself needing to implement your own
random number generator,
there is plenty of literature out there;
see the References below or




the sci.math.num-analysis FAQ list.

There are also any number of packages on the net:
old standbys are
r250, RANLIB, and FSULTRA
(see question <a href="faqcatccbd.html?sec=resources#sources">18.16</a>),
and there is much recent work
by
<a href="http://stat.fsu.edu/~geo/">Marsaglia</a>,

and Matumoto and Nishimura
(the ``<a href="http://www.math.keio.ac.jp/~matumoto/emt.html">Mersenne Twister</a>''),
and




some code collected by
<a href="http://www-cs-faculty.stanford.edu/~knuth/">Don Knuth</a>
on his
<a href="http://www-cs-faculty.stanford.edu/~knuth/programs.html">web pages</a>.
</p><p>Here is
a portable C implementation of
the ``minimal standard'' generator proposed by
Park and
Miller:
<pre>
#define a 16807
#define m 2147483647
#define q (m / a)
#define r (m % a)

static long int seed = 1;

long int PMrand()
{
	long int hi = seed / q;
	long int lo = seed % q;
	long int test = a * lo - r * hi;
	if(test &gt; 0)
		seed = test;
	else	seed = test + m;
	return seed;
}
</pre>
(The ``minimal standard'' is adequately good;
it is something ``against which all others should be judged'';
it is recommended for use 
``unless one has access to a random number generator
<I>known</I> to be better.'')
</p><p>This code implements the generator
<blockquote><I>X</I> &nbsp;&lt;-&nbsp; (<I>aX</I> + <I>c</I>) mod <I>m</I>
</blockquote>for <I>a</I> = 16807,
<I>m</I> = 2147483647
(which is
2**31-1),
and <I>c</I> = 0.<a href="../../lib/pmprimem.html" rel=subdocument>[footnote]</a>
The multiplication is carried out
using a technique described by
Schrage,
ensuring that the intermediate result <I>aX</I> does not overflow.
The implementation above returns <TT>long&nbsp;int</TT> values
in the range [1, 2147483646];
that is, it corresponds to C's <TT>rand</TT>
with a <TT>RAND_MAX</TT> of 2147483646,
<em>except</em> that it never returns 0.
To alter it to return floating-point numbers in the range (0, 1)
(as in the Park and Miller paper),
change the declaration to
<pre>
	double PMrand()
</pre>
and the last line to
<pre>
	return (double)seed / m;
</pre>
For slightly better statistical properties,
Park and Miller now recommend using <I>a</I> = 48271.
</p>









<p>References:

K&amp;R2 Sec. 2.7 p. 46, Sec. 7.8.7 p. 168
<br>
ISO Sec. 7.10.2.1
<br>
H&amp;S Sec. 17.7 p. 393
<br>
PCS Sec. 11 p. 172
<br>
Knuth Vol. 2 Chap. 3 pp.&nbsp;1-177
<br>
Park and Miller, ``Random Number Generators: Good Ones are Hard to Find''
<hr><hr><hr>
<a name="randrange">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/randrange.html"><!-- qtag -->Question 13.16</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
How can I get random integers in a certain range?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
The obvious way,
<pre>
	rand() % N		/* POOR */
</pre>
(which tries to return numbers from <TT>0</TT> to <TT>N-1</TT>)
is poor,
because
the low-order bits of many random
number
generators are distressingly <em>non</em>-random.
(See question
<a href="faqcat1067.html?sec=lib#notveryrand">13.18</a>.)
A better
method is something like
<pre>
	(int)((double)rand() / ((double)RAND_MAX + 1) * N)
</pre>
</p><p>If you'd rather not use floating point,
another method is
<pre>
	rand() / (RAND_MAX / N + 1)
</pre>
If you just need to do something with probability 1/<TT>N</TT>,
you could use
<pre>
	if(rand() &lt; (RAND_MAX+1u) / N)
</pre>
All these
methods
obviously require knowing <TT>RAND_MAX</TT>
(which ANSI <TT>#define</TT>s in <TT>&lt;stdlib.h&gt;</TT>),
and
assume

that <TT>N</TT> is much less than <TT>RAND_MAX</TT>.
</p><p>When <TT>N</TT> is close to <TT>RAND_MAX</TT>,
and if the range of the random number generator
is not a multiple of <TT>N</TT>
(i.e. if <TT>(RAND_MAX+1)&nbsp;%&nbsp;N&nbsp;!=&nbsp;0</TT>),
all of these methods break down:
some outputs
occur more often than others.
(Using floating point does <em>not</em> help;
the problem is that <TT>rand</TT> returns <TT>RAND_MAX+1</TT>
distinct values,
which cannot
always be evenly
divvied up
into <TT>N</TT> buckets.)
If this is a problem, about the only thing you can do
is to call <TT>rand</TT> multiple times,
discarding certain values:
<pre>
	unsigned int x = (RAND_MAX + 1u) / N;
	unsigned int y = x * N;
	unsigned int r;
	do {
		r = rand();
	} while(r &gt;= y);
	return r / x;
</pre>

</p><p>For any of these techniques,
it's
straightforward to shift
the range,
if necessary;
numbers in the range [M, N] could be generated
with something like 
<pre>
	M + rand() / (RAND_MAX / (N - M + 1) + 1)
</pre>

</p><p>(Note, by the way, that
<TT>RAND_MAX</TT> is a <em>constant</em>
telling you what the fixed range
of the C library <TT>rand</TT> function is.
You cannot set <TT>RAND_MAX</TT> to some other value,
and there is no way of requesting that <TT>rand</TT>
return numbers in some other range.)
</p><p>If you're starting with a random number generator
which returns floating-point values
between 0 and 1
(such as the last version of <TT>PMrand</TT>
alluded to in question <a href="faqcat1067.html?sec=lib#rand">13.15</a>,
or <TT>drand48</TT> in question <a href="faqcat1067.html?sec=lib#rand48">13.21</a>),
all you have to do
to get integers from 0 to <TT>N-1</TT>
is multiply the output of that generator by <TT>N</TT>:
<pre>
	(int)(drand48() * N)
</pre>
</p><p><a href="../../lib/sd15.html" rel=subdocument>Additional links</a>
</p>

<p>References:

K&amp;R2 Sec. 7.8.7 p. 168
<br>
PCS Sec. 11 p. 172
<hr><hr><hr>
<a name="srand">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/srand.html"><!-- qtag -->Question 13.17</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
Each time I run my program,
I get the same sequence of numbers back from <TT>rand()</TT>.
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
It's a characteristic of most
pseudo-random number generators
(and a defined property of the C library <TT>rand</TT>)
that
they

always start with the same number
and go through the same sequence.
(Among other things,
a bit of predictability can make debugging
much easier.)
When you don't want this predictability,
you


can call <TT>srand</TT> to seed the pseudo-random number
generator with a truly random
(or at least variable)
initial value.
Popular seed values are the time of day,
or a process ID number,
or
the elapsed time
before the user presses a key,
or some combination of these.
Here's an example call,
using the time
of day
as a seed:
<pre>
	#include &lt;stdlib.h&gt;
	#include &lt;time.h&gt;

	srand((unsigned int)time((time_t *)NULL));
</pre>
(There remain several difficulties:
the <TT>time_t</TT> returned by <TT>time</TT>
might be a floating-point type,
hence not portably convertible to <TT>unsigned&nbsp;int</TT>
without the possibility of overflow.
Furthermore,
if time of day is available with 1-second resolution,
using it by itself means that
successive runs of the program can easily get the same seed.
Subsecond resolution,
of time-of-day
or


keystroke presses,
is
hard to achieve portably;
see
question
<a href="faqcatea63.html?sec=osdep#subsecond">19.37</a>.)
</p><p>Note also that
it's

rarely useful to call <TT>srand</TT> more 
than once during a run of a program;

in particular,
don't try calling <TT>srand</TT>
before each call to <TT>rand</TT>,
in an attempt to get ``really random''
numbers.</p>


<p>References:

K&amp;R2 Sec. 7.8.7 p. 168
<br>
ISO Sec. 7.10.2.2
<br>
H&amp;S Sec. 17.7 p. 393
<hr><hr><hr>
<a name="notveryrand">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/notveryrand.html"><!-- qtag -->Question 13.18</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
I need a random true/false value,
so I'm just taking <TT>rand()&nbsp;%&nbsp;2</TT>,
but it's alternating 0, 1, 0, 1, 0...
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
Poor
pseudorandom number generators
(such as the ones
unfortunately supplied with some

systems)
are not very random in
the low-order bits.
(In fact,
for a
pure
linear congruential random number generator
with period
2**e,
and this tends to be how random number generators for e-bit 
machines
are written,
the low-order n bits repeat with period
2**n.)
For this reason,
it's preferable to use
the higher-order bits:
see question
<a href="faqcat1067.html?sec=lib#randrange">13.16</a>.
</p>
<p>References:

Knuth Sec. 3.2.1.1 pp. 12-14
<hr><hr><hr>
<a name="shuffle">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/shuffle.html"><!-- qtag -->Question 13.19</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
How can I return a sequence of random numbers
which don't repeat at all?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
What you're looking for is often called a



``random permutation'' or
``shuffle.''
One way is to initialize an array with the
values to be shuffled,
then randomly interchange each of the cells with another one
later in the array:
<pre>
	int a[10], i, nvalues = 10;

	for(i = 0; i &lt; nvalues; i++)
		a[i] = i + 1;

	for(i = 0; i &lt; nvalues-1; i++) {
		int c = randrange(nvalues-i);
		int t = a[i]; a[i] = a[i+c]; a[i+c] = t;	/* swap */
	}
</pre>

where <TT>randrange(N)</TT> is
<TT>rand()&nbsp;/&nbsp;(RAND_MAX/(N)&nbsp;+&nbsp;1)</TT>
or one of the other expressions from question <a href="faqcat1067.html?sec=lib#randrange">13.16</a>.
</p>
<p>References:

Knuth Sec. 3.4.2 pp. 137-8