Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 74-80 |
Number of pages | 7 |
Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - Apr 30 1979 |
Externally published | Yes |
Event | 11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States Duration: Apr 30 1979 → May 2 1979 |
All Science Journal Classification (ASJC) codes
- Software