疑似乱数は、周期性だったり偏りがあることが知られています。
基本的には、用途に合わせて要件を見たせば問題ないはずですが、
めちゃめちゃ偏りがあったり、周期が短いと、そういった要件を満たせず問題になります。
レガシーな乱数にはどんな偏りや周期性があるのか、可視化してみました。
線形合同法について実装します。
pythonで実装
class LCG:
def __init__(self, seed, a=1664525, c=1013904223, m=2**32):
self.a = a
self.c = c
self.m = m
self.state = seed
def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state
def random(self):
return self.next() / self.m # 正規化して 0 から 1 の間の値に変換
def randint(self):
return self.next()
乱数出力
seed = 12345
lcg = LCG(seed)
rand_int = [lcg.randint() for _ in range(1000000)]
偏りの可視化
下位16bitを出力しています。
plt.figure(figsize=(20,4))
tmp = [ (i & 0xFF) for i in rand_int]
plt.hist(tmp, bins=255)
下位8bitが0xFF(255)の出現数が、
他の要素と比べて2倍近く有ります。
この設定の場合ほかのbitでも同様の傾向が見られました。
上位の8bitもだしてみます。
plt.figure(figsize=(20,4))
tmp = [((i >> 24) & 0xFF) for i in rand_int]
plt.hist(tmp, bins=255)
周期性の可視化
うまい方法がみつからなかったので、
とりあえずprint文でお茶を濁すことにしました。
lower_bits = [i & 0xFF for i in rand_int]
head_val = lower_bits[0]
i = 0
print(head_val, end=", ")
for v in lower_bits[1:2560]:
i+=1
if v == head_val:
print()
print("周期 =", i)
i=0
print(v, end=", ")
出力
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
周期 = 256
183, 170, 1, 108, 219, 126, 197, 96, 63, 146, 201, 148, 227, 230, 13, 8, 199, 122, 145, 188, 235, 78, 85, 176, 79, 98, 89, 228, 243, 182, 157, 88, 215, 74, 33, 12, 251, 30, 229, 0, 95, 50, 233, 52, 3, 134, 45, 168, 231, 26, 177, 92, 11, 238, 117, 80, 111, 2, 121, 132, 19, 86, 189, 248, 247, 234, 65, 172, 27, 190, 5, 160, 127, 210, 9, 212, 35, 38, 77, 72, 7, 186, 209, 252, 43, 142, 149, 240, 143, 162, 153, 36, 51, 246, 221, 152, 23, 138, 97, 76, 59, 94, 37, 64, 159, 114, 41, 116, 67, 198, 109, 232, 39, 90, 241, 156, 75, 46, 181, 144, 175, 66, 185, 196, 83, 150, 253, 56, 55, 42, 129, 236, 91, 254, 69, 224, 191, 18, 73, 20, 99, 102, 141, 136, 71, 250, 17, 60, 107, 206, 213, 48, 207, 226, 217, 100, 115, 54, 29, 216, 87, 202, 161, 140, 123, 158, 101, 128, 223, 178, 105, 180, 131, 6, 173, 40, 103, 154, 49, 220, 139, 110, 245, 208, 239, 130, 249, 4, 147, 214, 61, 120, 119, 106, 193, 44, 155, 62, 133, 32, 255, 82, 137, 84, 163, 166, 205, 200, 135, 58, 81, 124, 171, 14, 21, 112, 15, 34, 25, 164, 179, 118, 93, 24, 151, 10, 225, 204, 187, 222, 165, 192, 31, 242, 169, 244, 195, 70, 237, 104, 167, 218, 113, 28, 203, 174, 53, 16, 47, 194, 57, 68, 211, 22, 125, 184,
同じ数列が出力されているのが確認できると思います＝周期性がある
リッチな環境ではあまり関係ないかもしれませんが、
組込限界集落(?)では、乱数生成機を実装する場合が有ります。
偏りと周期が要件に足りているかどうか、確認するといいかもしれません。
オヌヌメは
- メルセンヌ・ツイスタ（XORよりも長い）
- ネットワークのMACアドレスを初期SEEDにする（ニンテンドーDSの手法）
とかかなあ