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 ^ $$);
[download]

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)
[download]

Abigail

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.