線形合同法(LCG)による疑似乱数の生成

線形合同法とは

線形合同法(LCG; Linear Congruential Generator)は古くから知られている疑似乱数生成アルゴリズムで、背景の理論も簡単。
実行コストが低いため、暗号学的な安全性を求めないかつコンピューティングリソースに制約があるようなユースケースで利用されていました。

LCGではある乱数列 を以下の漸化式で表します

このとき

• 
• 
• 

の制約があります

ようは妥当な と を与えるとよしなな疑似乱数列が生まれるよというやつ。その際の仕組みも簡素で、適当に mul して add して mod とるだけという作り。簡単じゃんか

仕組みが簡素なぶん、指定されるパラメータによって生成される疑似乱数の質がかなり変わる。極端な例だと するとただの でmodとるカウンタになって終了するよっていうのが wikipediaに紹介されてた

また、mを2べきにすると下位bitの周期が短くなる既知の性質もあります。

実装

仕組み自体はむちゃくちゃ簡単なので、実装でこまることも特にないです。今回はオーバーフローは考慮しません。

// You can edit this code!
// Click here and start typing.
package main

import "fmt"

func main() {
    r := newLCG(19, 11, 7, 6)
    for _ = range 100 {
        fmt.Println(r.next())
    }
}

type lcg struct {
    m    uint64
    a    uint64
    c    uint64
    seed uint64
}

func newLCG(m, a, c, seed uint64) *lcg {
    return &lcg{m: m, a: a, c: c, seed: seed}
}

func (r *lcg) next() uint64 {
    r.seed = (r.a*r.seed + r.c) % r.m
    return r.seed
}

https://go.dev/play/p/zotICACR2lo

このとき結果は以下のようになる

16
12
6
16
12
6
16
12
6
...

この設定値の場合は 16, 12, 6 しか生成されません。また3回ごとに同じパターンを繰り返しているので周期は3です。

設定値によって周期や値の分布が大きく異なるので、ここの設定がキモっぽい。よく使われた値集みたいなのも探せば見つかる
https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use