【密码学】一文读懂MT19937

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
语种识别,语种识别 100万字符
简介: 瞄了一眼redis的源码,然后发现里面好玩的东西还挺多的,本文来聊一聊redis当中用到的一个随机数生成算法 mt19937,具体源码参见文末的参考资料,在这里就不贴到文本当中了。对于redis源码里面用的是mt19937-64本文先来看一下32位的版本,对于64位的版本,只不过状态当中元素用的是64位的元素,整个运算过程框架是类似的。「梅森旋转算法」(「Mersenne twister」)是一个伪随机数生成算法,由松本真和西村拓士在1997年提出来的,可以快速产生高质量的伪随机数,修正了古典随机数生成算法当中的很多缺陷。19937这个名字来源于周期长度为梅森素数 。

【密码学】一文读懂MT19937


]MO$QND[_P_8_@G]TCR8GZI.jpg

瞄了一眼redis的源码,然后发现里面好玩的东西还挺多的,本文来聊一聊redis当中用到的一个随机数生成算法 mt19937,具体源码参见文末的参考资料,在这里就不贴到文本当中了。对于redis源码里面用的是mt19937-64本文先来看一下32位的版本,对于64位的版本,只不过状态当中元素用的是64位的元素,整个运算过程框架是类似的。

「梅森旋转算法」「Mersenne twister」)是一个伪随机数生成算法,由松本真和西村拓士在1997年提出来的,可以快速产生高质量的伪随机数,修正了古典随机数生成算法当中的很多缺陷。19937这个名字来源于周期长度为梅森素数 。


生成器结构

OBAK1U[T7G]C@CA0)UAVAKD.pngMT19937生成器结构

如上图所示,mt19937的随机数生成器结构首先需要一个uint32的种子,然后生成一个具有624个uint32数组的状态数组。生成状态数组之后,进行一次旋转,最终可以输出624个随机的uint32。然后重复执行旋转操作,就可以得到一个周期为 的随机数生成器了。

对于mt19937整个计算过程来说,虽然比我之前提到过的线性同余法复杂不少,但是整个流程还是比较清晰的,对于里面的原理,我其实也了解的不是很多,因此在这里就不展开讲了,如果想了解原理的读者,可以参考文末的参考资料当中的论文进行学习,本文是指来聊一下这个东西具体是怎么计算的。到这里,这篇文章我就水完了,逃~~~


代码实现

老样子了,还是给出我写的两个语言的参考,注意本文讲的是32位的mt19937,再去看redis源码当中的实现的时候用的是mt19937-64。

Go

const (
  n = 624
  m = 397
)
type MT19937 struct {
  state []uint32
  index int
}
func New(seed uint32) *MT19937 {
  mt := &MT19937{
    state: make([]uint32, n),
    index: 0,
  }
  mt.state[0] = seed
  for i := uint32(1); i < n; i++ {
    mt.state[i] = 1812433253*(mt.state[i-1]^mt.state[i-1]>>30) + i
  }
  return mt
}
func (mt *MT19937) twist() {
  for i := uint32(0); i < n; i++ {
    y := (mt.state[i] & 0x80000000) + (mt.state[(i+1)%n] & 0x7fffffff)
    mt.state[i] = (y >> 1) ^ mt.state[(i+m)%n]
    if y%2 != 0 {
      mt.state[i] = mt.state[i] ^ 0x9908b0df
    }
  }
}
func (mt *MT19937) Uint32() uint32 {
  if mt.index == 0 {
    mt.twist()
  }
  y := mt.state[mt.index]
  y = y ^ y>>11
  y = y ^ y<<7&2636928640
  y = y ^ y<<15&4022730752
  y = y ^ y>>18
  mt.index = (mt.index + 1) % n
  return y
}

Rust

const N: usize = 624;
struct MT19937 {
    state: [u32; N],
    index: usize,
}
impl MT19937 {
    pub fn new(seed: u32) -> Self {
        let mut mt = MT19937 {
            state: [0; N],
            index: 0,
        };
        mt.state[0] = seed;
        for i in 1..N {
            mt.state[i] = 1812433253 * (mt.state[i - 1] ^ (mt.state[i - 1] >> 30)) + i as u32;
        }
        mt
    }
    fn twist(&mut self) {
        for i in 0..N {
            let x = (self.state[i] & 0x80000000) | (self.state[(i + 1) % N] & 0x7fffffff);
            let mut x_a = x >> 1;
            if x % 2 != 0 {
                x_a ^= 0x9908b0df;
            }
            self.state[i] = self.state[(i + 397) % N] ^ x_a;
        }
        self.index = 0;
    }
    fn rand(&mut self) -> u32 {
        if self.index >= N {
            self.twist();
        }
        let y = self.state[self.index];
        self.index += 1;
        y ^ y >> 11
    }
}


目录
打赏
0
0
0
0
19
分享
相关文章
kde
|
5天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
3152 8
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
572 0
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
842 9
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
本文详细介绍了Maven的项目管理工具特性、安装步骤和配置方法。主要内容包括: Maven概述:解释Maven作为基于POM的构建工具,具备依赖管理、构建生命周期和仓库管理等功能。 安装步骤: 从官网下载最新版本 解压到指定目录 创建本地仓库文件夹 关键配置: 修改settings.xml文件 配置阿里云和清华大学镜像仓库以加速依赖下载 设置本地仓库路径 附加说明:包含详细的配置示例和截图指导,适用于各种操作系统环境。 本文提供了完整的Maven安装和配置
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
【保姆级图文详解】大模型、Spring AI编程调用大模型
【保姆级图文详解】大模型、Spring AI编程调用大模型
359 7
【保姆级图文详解】大模型、Spring AI编程调用大模型
Excel数据治理新思路:引入智能体实现自动纠错【Python+Agent】
本文介绍如何利用智能体与Python代码批量处理Excel中的脏数据,解决人工录入导致的格式混乱、逻辑错误等问题。通过构建具备数据校验、异常标记及自动修正功能的系统,将数小时的人工核查任务缩短至分钟级,大幅提升数据一致性和办公效率。
DeepSeek R1+Open WebUI实现本地知识库的搭建和局域网访问
本文介绍了使用 DeepSeek R1 和 Open WebUI 搭建本地知识库的详细步骤与注意事项,涵盖核心组件介绍、硬件与软件准备、模型部署、知识库构建及问答功能实现等内容,适用于本地文档存储、向量化与检索增强生成(RAG)场景的应用开发。
369 0
让AI时代的卓越架构触手可及,阿里云技术解决方案开放免费试用
阿里云推出基于场景的解决方案免费试用活动,新老用户均可领取100点试用点,完成部署还可再领最高100点,相当于一年可获得最高200元云资源。覆盖AI、大数据、互联网应用开发等多个领域,支持热门场景如DeepSeek部署、模型微调等,助力企业和开发者快速验证方案并上云。
306 22
让AI时代的卓越架构触手可及,阿里云技术解决方案开放免费试用
FLUX.1 Kontext 的全生态教程来啦!AIGC专区在线试玩!
Flux.1 Kontext [dev] 开源模型大家都用上了吗?小编汇总了3个使用教程,打包送上!
426 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等