Middle-square method

Pseudo-random Number Generator
Reading time: about 4 minutes

The Middle-square method is a really old PRNG algorithm from 1949. It was discovered by John von Neumann.

The Algorithm

In [1]:
def ms_next(seed, seed_len):
    seed = seed * seed
    seed = str(seed).zfill(seed_len * 2)
    mid = int(seed_len / 2)
    seed = seed[mid:-mid]
    return int(seed)
In [2]:
def ms_numbers(seed, seed_len):
    while True:
        seed = ms_next(seed, seed_len)
        yield seed
In [3]:
for i, num in zip(range(5), ms_numbers(123456, 6)):
    print(i, num)
Out:
0 241383
1 265752
2 624125
3 532015
4 39960

Increasing seed space

Let’s seed it with /dev/urandom.

In [4]:
import os

def rand_digit():
    while True:
        d = os.urandom(1)[0]
        if d > 250:
            continue
        return d % 10

seed_len = 50
seed = ""

for _ in range(seed_len):
    seed += str(rand_digit())

seed = int(seed)

seed
Out [4]:
7378710975714809271419972422814068416462491488115

Let’s see if we can turn these numbers into random bits.

In [5]:
def ms_bits(seed, seed_len):
    for num in ms_numbers(seed, seed_len):
        yield num & 1

def ms_bytes(seed, seed_len):
    bits = ms_bits(seed, seed_len)
    while True:
        b = 0
        for _ in range(8):
            b <<= 1
            b |= next(bits)
        yield b

bits = ""
for i, bit in enumerate(ms_bits(seed, seed_len)):
    if i == 40:
        break
    
    bits += str(bit)

print(bits)
Out:
1100101111000110001001111100001001101011

Estimating randomness quality

In [6]:
import subprocess

ent = subprocess.Popen(["ent"], stdin=subprocess.PIPE, stdout=subprocess.PIPE)

buf = b""

for i, byte in enumerate(ms_bytes(seed, seed_len)):
    buf += bytes([byte])
    
    if i == 500_000:
        break
ent.stdin.write(buf)
ent.stdin.close()

print(ent.stdout.read().decode('ascii'))
Out:
Entropy = 7.999652 bits per byte.

Optimum compression would reduce the size
of this 500001 byte file by 0 percent.

Chi square distribution for 500001 samples is 241.47, and randomly
would exceed this value 71.91 percent of the times.

Arithmetic mean value of data bytes is 127.6098 (127.5 = random).
Monte Carlo value for Pi is 3.138780555 (error 0.09 percent).
Serial correlation coefficient is -0.002272 (totally uncorrelated = 0.0).

Not too bad.

Useful links and references

  • https://en.wikipedia.org/wiki/Middle-square_method

The following pages link here

Citation

If you find this work useful, please cite it as:
@article{yaltirakliwikimiddlesquaremethod,
  title   = "Middle-square method",
  author  = "Yaltirakli, Gokberk",
  journal = "gkbrk.com",
  year    = "2024",
  url     = "https://www.gkbrk.com/wiki/middle-square-method/"
}
Not using BibTeX? Click here for more citation styles.
IEEE Citation
Gokberk Yaltirakli, "Middle-square method", November, 2024. [Online]. Available: https://www.gkbrk.com/wiki/middle-square-method/. [Accessed Nov. 12, 2024].
APA Style
Yaltirakli, G. (2024, November 12). Middle-square method. https://www.gkbrk.com/wiki/middle-square-method/
Bluebook Style
Gokberk Yaltirakli, Middle-square method, GKBRK.COM (Nov. 12, 2024), https://www.gkbrk.com/wiki/middle-square-method/

Comments

© 2024 Gokberk Yaltirakli