線形合同法の下位ビットのランダム性が悪い

実際にやってみた。

Pythonで線形合同法を実装し、最下位ビットを確かめ、色塗りする。

その際、生成するランダム値を指定した分だけ右シフトできるshiftパラメータをシェルスクリプトで動かす。

その際の模様を見てみようというアレ。

code:py

class LCG:

def __init__(self, shift=0):

self.a = 1103515245

self.x = 0

self.c = 12345

self.m = 1 << 31

self.max_char = 9999 # 64

self._counter = 0

self.bit_lshift = shift

self.buffer = []

self.map_func = None

def random(self):

while True:

self.x = (self.a * self.x + self.c) % self.m

yield self.x

def should_fold(self) -> bool:

return self._counter % self.max_char == 0

def plot(self) -> str:

buffer = self.buffer

while True:

if self._counter >= 1024:

break

self.x = next(self.random())

bit = (self.x >> self.bit_lshift) & 1

char = str(bit) if self.map_func is None else self.map_func(bit)

buffer.append(char)

self._counter += 1

if self.should_fold():

buffer.append("\n")

return buffer

def translate(char: int) -> str:

if str(char) == "1":

return "@"

return " "

def from_input() -> list:

shift = int(input())

lcg = LCG(shift)

return lcg.plot()

def loop(itr_times: int) -> str:

buffer = []

for shift in range(itr_times):

lcg = LCG(shift)

lcg.map_func = translate

buffer.append(f"{shift=}\n")

for char in lcg.plot():

buffer.append(char)

return buffer

def main():

buffer = loop(9)

# buffer = from_input()

print("".join(buffer))

if __name__ == "__main__":

main()

ターミナルの幅を変えて遊ぶ

code:plain

for i in {0..8}; do echo "shift=$i"; echo $i | ./solve.py | tr '01' ' @'; done

shift=0

@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @

shift=1

@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@

shift=2

shift=3

shift=4

@@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@ @@@ @ @@@@@ @@ @ @ @@@

shift=5

@@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@ @@ @@ @ @ @@@@@@ @@@ @ @ @@ @ @ @ @@@ @@ @ @@ @@

shift=6

@@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @ @@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @ @@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @ @@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @ @@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @ @@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @ @@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @ @@ @ @ @@@@ @@ @@@ @@@ @@ @@ @ @@@@@ @@ @ @ @@ @@@@@@ @ @ @ @ @@@ @ @ @@ @ @@ @@@@ @@@@@ @ @ @

shift=7

@ @@@ @@@@ @ @ @ @ @@ @ @@@@@@ @@ @ @@@@@ @@@@ @ @@ @@ @@@ @@ @@ @ @ @@ @@ @@@@@ @@ @@@ @ @ @ @@ @@@ @ @@@ @@ @ @@@ @ @ @ @@@ @@ @ @@ @ @ @ @ @ @ @@ @ @ @ @@ @ @@@ @@ @@@@ @@@@@@@@@@ @ @@@ @ @ @@@ @@@@ @ @ @ @ @@ @ @@@@@@ @@ @ @@@@@ @@@@ @ @@ @@ @@@ @@ @@ @ @ @@ @@ @@@@@ @@ @@@ @ @ @ @@ @@@ @ @@@ @@ @ @@@ @ @ @ @@@ @@ @ @@ @ @ @ @ @ @ @@ @ @ @ @@ @ @@@ @@ @@@@ @@@@@@@@@@ @ @@@ @ @ @@@ @@@@ @ @ @ @ @@ @ @@@@@@ @@ @ @@@@@ @@@@ @ @@ @@ @@@ @@ @@ @ @ @@ @@ @@@@@ @@ @@@ @ @ @ @@ @@@ @ @@@ @@ @ @@@ @ @ @ @@@ @@ @ @@ @ @ @ @ @ @ @@ @ @ @ @@ @ @@@ @@ @@@@ @@@@@@@@@@ @ @@@ @ @ @@@ @@@@ @ @ @ @ @@ @ @@@@@@ @@ @ @@@@@ @@@@ @ @@ @@ @@@ @@ @@ @ @ @@ @@ @@@@@ @@ @@@ @ @ @ @@ @@@ @ @@@ @@ @ @@@ @ @ @ @@@ @@ @ @@ @ @ @ @ @ @ @@ @ @ @ @@ @ @@@ @@ @@@@ @@@@@@@@@@ @ @@@ @

shift=8

@ @@@@ @ @@@ @ @@@ @@ @ @@ @ @ @@ @ @ @@@ @ @@ @@@@ @@@ @@ @ @@@ @ @@@ @@@ @ @ @ @@ @@@@@ @ @ @ @ @ @ @ @ @ @@ @@ @@ @ @ @@@ @@ @ @@ @ @ @ @@@ @@@ @ @@ @ @ @@ @@ @@@ @ @@ @@@@ @@@@ @@@@ @ @@ @@ @@@@@@@@@@@ @ @ @@ @@@ @@@@@ @@ @ @ @@ @@ @ @ @ @ @@ @@@ @ @@ @@@@ @ @@@ @ @@@ @@@@@@ @@@@@@ @ @ @ @@ @ @ @ @@ @ @ @ @@ @ @@ @@@@ @@ @@@@ @ @ @@@@ @ @ @ @@@@@@@@@ @ @@@@@ @@ @@ @ @ @ @@ @@ @ @@@@ @ @@@ @ @@@ @@ @ @@ @ @ @@ @ @ @@@ @ @@ @@@@ @@@ @@ @ @@@ @ @@@ @@@ @ @ @ @@ @@@@@ @ @ @ @ @ @ @ @ @ @@ @@ @@ @ @ @@@ @@ @ @@ @ @ @ @@@ @@@ @ @@ @ @ @@ @@ @@@ @ @@ @@@@ @@@@ @@@@ @ @@ @@ @@@@@@@@@@@ @ @ @@ @@@ @@@@@ @@ @ @ @@ @@ @ @ @ @ @@ @@@ @ @@ @@@@ @ @@@ @ @@@ @@@@@@ @@@@@@ @ @ @ @@ @ @ @ @@ @ @ @ @@ @ @@ @@@@ @@ @@@@ @ @ @@@@ @ @ @ @@@@@@@@@ @ @@@@@ @@ @@ @ @ @ @@ @@