TY - JOUR

T1 - The complexity of finding periods

AU - Sedgewick, Robert

AU - Szymanski, Thomas G.

N1 - Publisher Copyright:
© 1979 Association for Computing Machinery. 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

SN - 0737-8017

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

T2 - 11th Annual ACM Symposium on Theory of Computing, STOC 1979

Y2 - 30 April 1979 through 2 May 1979

ER -