Access Restriction

Author Tootill, J. P. R. ♦ Robinson, W. D. ♦ Eagle, D. J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1973
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The theoretical limitations on the orders of equidistribution attainable by Tausworthe sequences are derived from first principles and are stated in the form of a criterion to be achieved. A second criterion, extending these limitations to multidimensional uniformity, is also defined. A sequence possessing both properties is said to be asymptotically random as no other sequence of the same period could be more random in these respects.An algorithm is presented which, for any Tausworthe sequence based on a primitive trinomial over GF(2), establishes how closely or otherwise the conditions necessary for the criteria are achieved. Given that the necessary conditions are achieved, the conditions sufficient for the first criterion are derived from Galois theory and always apply. For the second criterion, however, the period must be prime.An asymptotically random 23-bit number sequence of astronomic period, 2607 - 1, is presented. An initialization program is required to provide 607 starting values, after which the sequence can be generated with a three-term recurrence of the Fibonacci type. In addition to possessing the theoretically demonstrable randomness properties associated with Tausworthe sequences, the sequence possesses equidistribution and multidimensional uniformity properties vastly in excess of anything that has yet been shown for conventional congruentially generated sequences. It is shown that, for samples of a size it is practicable to generate, there can exist no purely empirical test of the sequence as it stands capable of distinguishing between it and an ∞-distributed sequence. Bounds for local nonrandomness in respect of runs above (below) the mean and runs of equal numbers are established theoretically.The claimed randomness properties do not necessarily extend to subsequences, though it is not yet known which particular subsequences are at fault. Accordingly, the sequence is at present suggested only for simulations with no fixed dimensionality requirements.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1973-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 20
Issue Number 3
Page Count 13
Starting Page 469
Ending Page 481

Open content in new tab

   Open content in new tab
Source: ACM Digital Library