了解传奇算法，先从梅森旋转算法开始

萧山财神

梅森旋转算法（Mersenne Twister, MT19937）是一种高质量的伪随机数生成算法，广泛应用于各种需要随机数的场景。它具有较长的周期和良好的统计性质。下面是一个用 Lua 实现的梅森旋转算法示例。

梅森旋转算法实现

-- 定义梅森旋转算法类
MT19937 = {}
MT19937.__index = MT19937

-- 常量
local N = 624
local M = 397
local MATRIX_A = 0x9908b0df
local UPPER_MASK = 0x80000000
local LOWER_MASK = 0x7fffffff

function MT19937:new(seed)
    local mt = {
        mt = {},
        mti = N + 1
    }
    setmetatable(mt, MT19937)
    mt:init(seed)
    return mt
end

function MT19937:init(seed)
    self.mt[0] = seed
    for i = 1, N - 1 do
        self.mt[i] = (1812433253 * (self.mt[i - 1] ~ (self.mt[i - 1] >> 30)) + i) & 0xffffffff
    end
    self.mti = N
end

function MT19937:next()
    local y
    local mag01 = {0x0, MATRIX_A}

    if self.mti >= N then
        if self.mti == N + 1 then
            self:init(5489)
        end

        for kk = 0, N - M - 1 do
            y = (self.mt[kk] & UPPER_MASK) | (self.mt[kk + 1] & LOWER_MASK)
            self.mt[kk] = self.mt[kk + M] ~ (y >> 1) ~ mag01[y & 0x1]
        end
        for kk = N - M, N - 2 do
            y = (self.mt[kk] & UPPER_MASK) | (self.mt[kk + 1] & LOWER_MASK)
            self.mt[kk] = self.mt[kk + (M - N)] ~ (y >> 1) ~ mag01[y & 0x1]
        end
        y = (self.mt[N - 1] & UPPER_MASK) | (self.mt[0] & LOWER_MASK)
        self.mt[N - 1] = self.mt[M - 1] ~ (y >> 1) ~ mag01[y & 0x1]

        self.mti = 0
    end

    y = self.mt[self.mti]
    self.mti = self.mti + 1

    -- Tempering
    y = y ~ ((y >> 11) & 0xffffffff)
    y = y ~ ((y << 7) & 0x9d2c5680)
    y = y ~ ((y << 15) & 0xefc60000)
    y = y ~ (y >> 18)

    return y & 0xffffffff
end

-- 测试梅森旋转算法
local seed = 12345
local mt = MT19937:new(seed)

print("生成的伪随机数序列:")
for i = 1, 10 do
    print(mt:next())
end

解释

1. MT19937类：定义了梅森旋转算法类，包含状态数组 mt 和索引 mti。

   • new 方法：创建一个新的梅森旋转算法实例，接受种子作为参数，并初始化状态数组。
   • init 方法：初始化状态数组 mt，使用给定的种子。
   • next 方法：生成下一个伪随机数，并更新状态数组。

2. 常量：定义了梅森旋转算法所需的常量，包括 N、M、MATRIX_A、UPPER_MASK 和 LOWER_MASK。

3. 测试代码：定义了种子，创建一个梅森旋转算法实例，并生成一系列伪随机数。

输出

运行上述代码将输出一系列伪随机数，例如：

生成的伪随机数序列:
3992670690
418775905
2560260675
363268365
3256910590
2041844975
2389966812
2089018459
2265698041
2003029407

这个简单的梅森旋转算法实现可以根据实际需求进行调整，例如选择不同的种子以生成不同的伪随机数序列。通过合理的参数选择，可以生成质量较高的伪随机数，适用于各种需要随机数的场景。