了解传奇算法，先从线性同余生成器开始

萧山财神

线性同余生成器（Linear Congruential Generator, LCG）是一种简单且常用的伪随机数生成算法。它通过以下递归公式生成一系列伪随机数：

[ X_{n+1} = (a \cdot X_n + c) \mod m ]

其中：

• ( X ) 是生成的伪随机数序列。
• ( a ) 是乘数。
• ( c ) 是增量。
• ( m ) 是模数。
• ( X_0 ) 是种子（初始值）。

下面是一个用 Lua 实现的线性同余生成器示例：

-- 定义线性同余生成器类
LCG = {}
LCG.__index = LCG

function LCG:new(seed, a, c, m)
    local lcg = {
        seed = seed,
        a = a,
        c = c,
        m = m,
        current = seed
    }
    setmetatable(lcg, LCG)
    return lcg
end

function LCG:next()
    self.current = (self.a * self.current + self.c) % self.m
    return self.current
end

-- 测试线性同余生成器
local seed = 12345
local a = 1103515245
local c = 12345
local m = 2^31

local lcg = LCG:new(seed, a, c, m)

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

解释

1. LCG类：定义了线性同余生成器类，包含种子、乘数、增量、模数和当前值。

   • new 方法：创建一个新的线性同余生成器实例，接受种子、乘数、增量和模数作为参数。
   • next 方法：生成下一个伪随机数，并更新当前值。

2. 测试代码：定义了种子、乘数、增量和模数，创建一个线性同余生成器实例，并生成一系列伪随机数。

输出

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

生成的伪随机数序列:
1406932606
654583775
1449466924
229283573
1109335178
1051550459
1293799192
794471793
551188310
803550167

这个简单的线性同余生成器可以根据实际需求进行调整，例如选择不同的参数 ( a )、( c ) 和 ( m ) 以生成不同的伪随机数序列。通过合理的参数选择，可以生成质量较高的伪随机数，适用于各种需要随机数的场景。