TY - JOUR
T1 - The complexity of finding periods
AU - Sedgewick, Robert
AU - Szymanski, Thomas G.
N1 - Funding Information:
Suppose that we are given an arbitrary function f/which maps some finite domain D into D. If we take an arbitrary element z from D and generate the infinite sequence fo(,~), fl (z), f2(z), .... then we are guaranteed by the "pigeonhole principle" and the finiteness of D that the sequence becomes cyclic. That is, for some l and c we have l q--e distinct values ./°Cz),f'Cz),...,,ft+c-ICz ) but ft+c(z) -~ ft(z). This implies, in turn. that fi+c(z) = fi(z) for all i > l. The problem of finding this unique pair (l, c) will be termed the cycle problem for f and z. Tile integer c is the cycle length of the sequence, and l is termed the leader length. Similarly, tlie elements f~(z), ftWl(z),..., ft+c-I(z) are said to form the cycle of f on :~ and f°(z), ft(x),..., ft-I(x) are said to form the leader" of f on x. For notational * This work was supported in part by the National Science Foundation. grant number MCS75-23738.
Publisher Copyright:
© 1979 Association for Computing Machinery. All rights reserved.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 1979/4/30
Y1 - 1979/4/30
N2 - Given a function/over a finite domain D and an arbitrary starting point x, the sequence x f(x)t f[fix)) ? ? ? Is ultimately periodic Such sequences typically are used for constructiong random number generators. The cycle problem is to determine the first repeated element fn(x) in the sequence. Previous algorithms for this problem have required 3n operations, In this paper we present an algorithm which only requires n(l-/-0(1///M)) steps, if M memory cells are available to store values of the function. By increasing M, this running time can be made arbitrarily close to the information-theoretic lower bound on the running time of any algorithm for the cycle problem. Our treatment is novel in that we explicitly consider the performance of the algorithm as a function of the amount of memory available as well as the relative cost of evaluating/and comparing sequence elements for equality.
AB - Given a function/over a finite domain D and an arbitrary starting point x, the sequence x f(x)t f[fix)) ? ? ? Is ultimately periodic Such sequences typically are used for constructiong random number generators. The cycle problem is to determine the first repeated element fn(x) in the sequence. Previous algorithms for this problem have required 3n operations, In this paper we present an algorithm which only requires n(l-/-0(1///M)) steps, if M memory cells are available to store values of the function. By increasing M, this running time can be made arbitrarily close to the information-theoretic lower bound on the running time of any algorithm for the cycle problem. Our treatment is novel in that we explicitly consider the performance of the algorithm as a function of the amount of memory available as well as the relative cost of evaluating/and comparing sequence elements for equality.
UR - http://www.scopus.com/inward/record.url?scp=77950380194&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77950380194&partnerID=8YFLogxK
U2 - 10.1145/800135.804400
DO - 10.1145/800135.804400
M3 - Conference article
AN - SCOPUS:77950380194
SP - 74
EP - 80
JO - Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Proceedings of the Annual ACM Symposium on Theory of Computing
SN - 0737-8017
T2 - 11th Annual ACM Symposium on Theory of Computing, STOC 1979
Y2 - 30 April 1979 through 2 May 1979
ER -