The period of the Fibonacci random number generator |
| |
Institution: | Department of Computer Science, Boston College, 432 Fulton Hall, Chestnut Hill, MA 02167, USA |
| |
Abstract: | Smith, Green, and Klem introduced the Fibonacci RNG in 7]. A starting vector of k integers is chosen, and new numbers are generated by the recurrence rn≡rn−1+rn−k (mod M). For a prime M and some choices of the parameter k, any non-zero initial vector υ gives a sequence with a period of Mkminus;1. However, in most cases, different initial values give rise to very different periods. This behavior was noted by the authors, but left unexplained. In this paper we review how sequences with short periods arise, and provide an algorithm that selects different starting vectors that give a maximal period. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|