Results 1 to 3 of 3

Thread: Period of modulo sequence? (linear congruential random generator)

  1. #1
    Newbie Mobius's Avatar
    Joined
    Jul 2010
    Posts
    14

    Period of modulo sequence? (linear congruential random generator)

    Consider the following sequence of natural numbers:

    $\displaystyle x_{i+1} = (a \cdot x_i + c) \mod m$

    With certain constants a, c and m. Also known as the Linear Congruential (Random) Generator because it's used to generate pseudo-random numbers. For sake of simplicity assume $\displaystyle x_0$=0.

    Example with a=2, c=1, m=5: $\displaystyle x_i$ = 0,1,3,2,0,1,3,2,...etc

    In this case the sequence has a period of 4. Obviously in any case the period is at most m.

    I'm wondering for which numbers of m, there exist a>1 and c so that the maximum period m is actually obtained (with a=1 this is always possible for any m, the sequence then simply becomes 0,c,2c,3c,etc..).

    The first possibility seems to be m=8, for example with a=5 and b=3: $\displaystyle x_i$ = 0,3,2,5,4,7,6,1,(0,3,etc)

    The wiki link above suggests this ought to be possible for any m, as long as the following criteria are met:
    • c and m are coprime
    • a-1 is divisible by all prime factors of m
    • a-1 is a multiple of 4 $\displaystyle \Leftrightarrow$ m is a multiple of 4

    But in practice I found otherwise (for starters, there are no values a,c at all for m<8).

    Does anyone know more about this? I do have some vague idea as to what criterium m should meet in order to have this "full modulo period" property. But I'm not sure yet and certainly unable to prove anything.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    A starting point could be to first solve the recurrence relation:

    $\displaystyle x_{i+1} = a \cdot x_i + c $

    So $\displaystyle x_1 = a \cdot x_0 + c$
    Then $\displaystyle x_2 = a \cdot x_1 + c = a \cdot (a \cdot x_0 + c)+c = a^2 \cdot x_0+ a \cdot c + c$

    In general $\displaystyle x_t = a^t x_0 + c \sum_{k=0}^{t-1}a^k = a^t x_0 + c \frac{a^t-1}{a-1}$ where we've used the formula for the geometric sum. Now after modding out m, we need to be left with m distinct numbers

    To show that they are all different, I think you need to use something of the sort: $\displaystyle x_i = x_j \mod m => i = j $
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Mobius's Avatar
    Joined
    Jul 2010
    Posts
    14
    Thanks, nice start. I'm not that good with modulo calculations.

    Originally I mentioned we could assume $\displaystyle x_0$=0, but this isn't necessary: if some combination of a, c and m results in a full period, it does so for any $\displaystyle x_0$.

    And since $\displaystyle x_t=a^tx_0+c\frac{a^t-1}{a-1}$ perhaps we can pick $\displaystyle x_0$ so that $\displaystyle x_t$ becomes easier to resolve (mod m)...?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. R Language Random Number Generator
    Posted in the Advanced Statistics Forum
    Replies: 16
    Last Post: Feb 6th 2011, 04:32 AM
  2. Random Sequence Generator
    Posted in the Math Forum
    Replies: 0
    Last Post: Jul 3rd 2010, 08:38 AM
  3. Linear congruential generator problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jan 19th 2009, 06:13 AM
  4. Random Number Generator
    Posted in the Math Challenge Problems Forum
    Replies: 3
    Last Post: Oct 22nd 2008, 12:22 AM

Search Tags


/mathhelpforum @mathhelpforum