The complexity of finding periods

Robert Sedgewick, Thomas G. Szymanski

Research output: Contribution to journalConference article

8 Scopus citations

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 languageEnglish (US)
Pages (from-to)74-80
Number of pages7
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Apr 30 1979
Externally publishedYes
Event11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States
Duration: Apr 30 1979May 2 1979

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'The complexity of finding periods'. Together they form a unique fingerprint.

  • Cite this