Technical Correspondence: Random Link Generator
Vector 15:1, page 130
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 130
Random Link Generator¶
In Eugene McDonnell’s piece on a Random Link Generator (Vector Vol.14 no.4 pp. 122-127) he refers to the treatment of an idea of G.J. Mitchell and D.P. Moore in several editions of Knuth’s book Seminumerical Algorithms (vol.2 of The Art of Computer Programming).
My copy of the 1969 edition has, at the end of the preface on p.vi, an Author’s note "In this second printing, I have incorporated several hundred improvements to the text and exercises while retaining the original page numbering." In the index there are entries for Mitchell, Gerard Joseph Francis Xavier and Moore, Donald Philip which both point to page 464. That page is in the ‘Answers to Exercises’ and contains a brief mention of their 1958 idea for the case that \(m\) is a power of 2. I enclose a copy of page 464.
The results of this exercise…suggest[s] the following way to obtain the efficiently computable sequence with a very long period… If \(x^k + x^j + 1\) is a primitive polynomial modulo 2, the sequence defined by \(X_n = (X_{n-j} + X_{n-k}) \bmod 2^e\) has a period length between \(2^k - 1\) and \(2^{e-1}(2^k - 1)\), if \(X_0, \ldots, X_{k-1}\) are not all even. For example, the sequence defined by \(X_n = (X_{n-24} + X_{n-55}) \bmod 2^e\) will have a period length of at least \(2^{55} - 1\), which is the period of its unit digits, and the actual period length will probably be much larger. This idea, due to G.J. Mitchell and D.P. Moore in 1958 (unpublished), has been used with apparent success to generate full-word random numbers.; the sequence clearly has some locally nonrandom subsequences which hardly ever occur. When \(k = 127\) we may take \(j = 1, 7, 15, 30, 63, 64, 97, 112, 120\) or \(126\).
I don’t have access to copies of the other editions but it is interesting that Knuth’s thinking on this had begun to change even by the second printing which appears to be in the same year.
John Sutton
Reply¶
Kudos to Mr. Sutton for having the diligence to do what I should have done, that is, to look in the index of Knuth’s Seminumerical Algorithms for the names Mitchell and Moore. Had I done so, I would have seen that the names were even in my copy, which was the first printing of the book, along with the text cited by Sutton. My attention, however, was paid to Knuth’s caution in the main part of the book in Section 3.2.2, where he says, "At the present time, not very much is known about such an additive number generator; before its use can be recommended, it will be necessary to develop the theoretical results necessary to prove certain desirable randomness properties…"
It is also of interest to note that between 1969 and 1993 the algorithm had changed from an additive one to a subtractive one, whence the name "the subtractive method", used in Knuth’s The Stanford Graph, Section GB_FLIP 4.
Eugene McDonnell
Palo Alto