If a sequence takes only a small number of different values, then by regarding the values as the elements of a finite field, the Berlekamp-Massey algorithm is an efficient procedure for finding the shortest linear recurrence from the field that will generate the sequence.
Berlekamp-Massey Algorithm
See also
Reeds-Sloane AlgorithmExplore with Wolfram|Alpha
References
Berlekamp, E. R. Ch. 7 in Algorithmic Coding Theory. New York: McGraw-Hill, 1968.Berlekamp, E. R.; Fredricksen, H. M.; and Proto, R. C. "Minimum Conditions for Uniquely Determining the Generator of a Linear Sequence." Util. Math. 5, 305-315, 1974.Brent, R. P.; Gustavson, F. G.; and Yun, D. Y. Y. "Fast Solution of Toeplitz Systems of Equations and Computation of Padé Approximants." J. Algorithms 1, 259-295, 1980.Dickinson, B. W.; Morf, M.; and Kailath, T. "A Minimal Realization Algorithm for Matrix Sequences." IEEE Trans. Automatic Control 19, 31-38, 1974.Gustavson, F. G. "Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm." IBM J. Res. Dev. 20, 204-212, 1976.MacWilliams, F. J. and Sloane, N. J. A. Ch. 9 in The Theory of Error-Correcting Codes. New York: Elsevier, 1978.Massey, J. L. "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Information Th. 15, 122-127, 1969.McEliece, R. J. The Theory of Information Coding. Reading, MA: Addison-Wesley, 1977.Mills, W. H. "Continued Fractions and Linear Recurrences." Math. Comput. 29, 173-180, 1975.Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, pp. 25-26, 1995.Referenced on Wolfram|Alpha
Berlekamp-Massey AlgorithmCite this as:
Weisstein, Eric W. "Berlekamp-Massey Algorithm." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Berlekamp-MasseyAlgorithm.html