While scanning your code, I couldn't help noticing that you wrote:
# this is as good a time as any to seed rand()
srand(time ^ $$);
This is actually a bad seed. Very old Camels suggested this, but
even the Camel-II warns about. The problem is that
time ^ $$ == (time + 1) ^ ($$ + 1) surprisingly often.
Below I quote from a post I made to comp.lang.perl.misc in March 1996
which analysis the problem, and which eventually lead to Perl using
a much more "random" seed. The post shows how often
time ^ $$ == (time + 1) ^ ($$ + 1).
Write both time and $$ as binary numbers. Suppose both time and $$ end
+ with
a 0 followed by n 1's (n >= 0). Then the bit patterns are:
time: t_k t_(k-1) ... t_(n+1) 0 1 ... 1
$$: s_k s_(k-1) ... s_(n+1) 0 1 ... 1
hence, the bit pattern of time^$$ is:
t_k^s_k t_(k-1)^s_(k-1) ... t_(n+1)^s_(n+1) 0 0 ... 0.
Now, look at the bit patterns of time + 1 and $$ + 1:
time+1: t_k t_(k-1) ... t_(n+1) 1 0 ... 0
$$+1: s_k s_(k-1) ... t_(k+1) 1 0 ... 0
XORing time+1 and $$+1 gives:
t_k^s_k t_(k-1)^s_(k-1) ... t_(n+1)^s_(n+1) 0 0 ... 0, which equals ti
+me^$$.
It is easily seen that if time ends with a 0 followed by n 1's, and $$
+ ends
with a 0 followed by m 1's (n <> m, wlog assume n < m), that then bit
+n + 1
(counted from the right) of time^$$ will differ from bit n + 1 of (tim
+e+1)^($$+1).
Now, how often do time and $$ end with the same number of 1's? If each
+ bit of
time and $$ has a 0.5 chance of being 1 or 0, the following holds:
Let Pt(n) be the chance time ends with a 0 followed by n 1's.
Then Pt(n) = 1/2^(n+1).
Similary, Ps(n) = 1/2^(n+1); Ps(n) being the chance $$ ends with a
0 followed by n 1's.
Let Q(n) be the chance BOTH time and $$ end with a 0 followed by n 1's
+.
Since Pt and Ps are independent, we have:
Q(n) = Pt(n) * Ps(n) = 1/2^(2n+2) = (0.25)^(n+1).
To get the total chance time^$$ equals (time+1)^($$+1), we need to
take a summation over all possible values of n. So, let Q be the chanc
+e
time^$$ == (time+1)^($$+1). Then we have:
Q = Sigma_{n=0}^{k} Q(n) = Sigma_{n=0}^{k} (0.25)^(n+1) =
Sigma_{n=1}^{k+1} (0.25)^n.
where k is the number of bits in an integer.
Hence Q = (0.25 - 0.25^(k+1))/0.75, which goes to 1/3 when k -> oo.
So, in almost one third of the cases, time^$$ equals (time+1)^($$+1).
(In the above analysis, ^ is used in 3 different roles:
- as the xor function,
- as the power function,
- in the LaTeX way.
I hope the context makes it clear which case applies)
Abigail