The Complexity of Finding Periods

Given a function f over a finite domain D and an arbitrary starting point x , the sequence x,f(x),f(f(x)), ... is ultimately periodic. Such sequences typically are used for constructing random number generators. The cycle problem is to determine the first repeated element f n (x) in the sequence. Previous algorithms for this problem have required 3 n operations. In this paper we present an algorithm which only requires n (1+ O (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 f and comparing sequence elements for equality.

Authors

• Robert Sedgewick
• Thomas G. Szymanski

Keywords

No keywords are indexed for this paper.