The period of the Fibonacci random number generator (Q1105311)

The Fibonacci random number generator \(r_ n\equiv r_{n-1}+r_{n- k}(mod M)\) is in focus in this paper. For M prime and some choices of k, any non-zero starting vector \(v=(r_ 1,...,r_ k)\) for integers creates a sequence of maximal period M k-1. In most cases, however, different v's give rise to different periods. An algorithm is presented that selects initial vectors with maximal period. The results of some empirical tests are given at the end of the paper. The Fibonacci generator passes the run test only after decimation.