^ 2.02.1"Uniform random number generators for supercomputers" （页面存档备份，存于互联网档案馆）, Richard Brent, 1992
^"Four-tap shift-register-sequence random-number generators" （页面存档备份，存于互联网档案馆）, Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392
十月 31, 2023
时滞斐波那契生成器, 英語, lagged, fibonacci, generator, 简称, lfg或lfib, 是一类伪随机数生成器, 用于改进标准的线性同余生成器, 用递推关系表示序列的生成, displaystyle, equiv, star, pmod, 其中, 新项由两个老项计算生成, m通常是2的幂, 经常232或264, 其中, displaystyle, star, 算符表示一般的二元运算符, 这可以是加法, 减法, 乘法或者位运算异或, 相应地称作加法, alfg, 乘法, mlfg, 双抽头. 时滞斐波那契生成器 英語 Lagged Fibonacci generator 简称 LFG或LFib 是一类伪随机数生成器 用于改进标准的线性同余生成器 用递推关系表示序列的生成 S n S n j S n k mod m 0 lt j lt k displaystyle S n equiv S n j star S n k pmod m 0 lt j lt k 其中 新项由两个老项计算生成 m通常是2的幂 m 2M 经常232或264 其中 displaystyle star 算符表示一般的二元运算符 这可以是加法 减法 乘法或者位运算异或 相应地称作加法时滞斐波那契生成器 ALFG 乘法时滞斐波那契生成器 MLFG 双抽头广义反馈移位寄存器 GFSR 梅森旋转算法是GFSR的变种 GFSR与线性反馈移位寄存器有关 使用k个状态字的生成器 称作 记住 了过去k个值 时滞斐波那契生成器的理论相当复杂 理论也不够充分到能指导如何选择j与k 生成器的初始化也非常敏感 目录 1 性值 2 时滞斐波那契生成器的问题 3 使用 4 参考文献性值 编辑时滞斐波那契生成器对于加减法运算 有最大周期 2k 1 2M 1 对异或运算有最大周期 2k 1 k 对乘法运算的最大周期为 2k 1 2M 3 即加法运算最大周期的1 4 为了达到最大周期 多项式 y xk xj 1必须是本原多项式 对于mod 2的整数 满足这样的约束的j与k 已经在文献中公布 常用的有 j 7 k 10 j 5 k 17 j 24 k 55 j 65 k 71 j 128 k 159 1 j 6 k 31 j 31 k 63 j 97 k 127 j 353 k 521 j 168 k 521 j 334 k 607 j 273 k 607 j 418 k 1279 2 页面存档备份 存于互联网档案馆 另一套j与k的可能值在 计算机程序设计艺术 第2卷第29页公布 24 55 38 89 37 100 30 127 83 258 107 378 273 607 1029 2281 576 3217 4187 9689 7083 19937 9739 23209 注意到上述数越小 周期就越短 如果使用加法 要求前k个初始化生成器的值中至少一个是奇数 如果使用乘法 要求前k个值都必须是奇数 1 有研究建议j与k最好近似黄金比例 2 时滞斐波那契生成器的问题 编辑Robert M Ziff在四抽头移位寄存器的论文中指出 众所周知这种生成器 特别是双抽头的 R 103 250 有严重的缺陷 George Marsaglia 英语 George Marsaglia 发现R 24 55 与更小的生成器的作为相当差 并建议不要用这类生成器 双抽头生成器R a b 的基础问题是给定了生成器 则有内在的三点相关 x n displaystyle x n nbsp x n a displaystyle x n a nbsp x n b displaystyle x n b nbsp 这种相关性在p m a x a b c displaystyle p max a b c ldots nbsp 尺度上传播 显然导致了问题 3 这是指标准的时滞斐波那契生成器 每个新数依赖于以前的2个老数 三抽头的时滞斐波那契生成器去除了很多统计问题 如在Birthday Spacings 英语 Diehard tests 与Generalized Triple测试失败问题 2 时滞斐波那契生成器的初始化是个非常复杂的问题 时滞斐波那契生成器的输出对其初始化条件非常敏感 时滞斐波那契生成器的数学理论是不完备的 使它依赖于统计测试而不是理论分析 使用 编辑Freeciv游戏使用时滞斐波那契生成器 j 24 k 55 Boost C Libraries实现了时滞斐波那契生成器 Subtract with carry是时滞斐波那契生成器的一种实现 包含在C 11标准模板库中 Oracle数据库在DBMS RANDOM包中实现了时滞斐波那契生成器 参考文献 编辑Toward a universal random number generator G Marsaglia A Zaman Parameterizing Parallel Multiplicative Lagged Fibonacci Generators 页面存档备份 存于互联网档案馆 M Mascagni A Srinivasan 2 0 2 1 Uniform random number generators for supercomputers 页面存档备份 存于互联网档案馆 Richard Brent 1992 Four tap shift register sequence random number generators 页面存档备份 存于互联网档案馆 Robert M Ziff Computers in Physics 12 4 Jul Aug 1998 pp 385 392 取自 https zh wikipedia org w index php title 时滞斐波那契生成器 amp oldid 79112806, 维基百科，wiki，书籍，书籍，图书馆，
