Insight

xorshift 随机数生成器

Yonglun -

介绍

今天在看 karpathy 大神的llama2.c 的代码，里面使用了xorshift 随机数生成器，自己用C#实现了一次，记录下自己的理解。

xorshift 随机数生成器是一种基于位操作的伪随机数生成算法，由 George Marsaglia 在 2003 年提出。它通过异或操作与移位操作混合来生成随机数，并且相较于传统的线性同余生成器来说具有较好的随机性和性能。虽然 xorshift 通常用于需要生成快速伪随机数的场景。

优点

  • 性能：由于它的操作主要是简单的移位和异或，所以 xorshift 通常比其他复杂的生成器（如 Mersenne Twister）更快。
  • 可预测性：通过种子可以再现随机数序列，这在测试和调试中非常有用。

缺点

  • 随机性问题：与更复杂的生成器相比，xorshift 可能在高维空间或长序列下表现出一定的模式，使它不适用于某些高随机性要求的应用，例如加密。
  • 周期性问题：xorshift 的周期性依赖于其内部状态的长度。在某些配置下，周期可能较短。

适用场景

  • 适合：对于图形学、模拟、非加密性应用程序，xorshift 是一种良好的选择，尤其当需要快速产生大量随机数时。
  • 不适合：对于密码学、安全性要求较高的场景或某些科学模拟，建议选择更高随机性的生成器（如 RandomNumberGenerator 或 Mersenne Twister）。

综上所述，xorshift 是一种可靠的生成器，在适当的应用场景中可以胜任。但是，如果应用对随机性和安全性要求较高，应当使用加密安全的随机数生成器。

C#实现

下面我买实现了一个xorshift 随机数生成器的C#版本

using System;

class RandomNumberGenerator
{
    // 内部保存状态变量
    private ulong state;

    // 构造函数，接受初始状态
    public RandomNumberGenerator(ulong initialState)
    {
        state = initialState;
    }

    // 生成一个32位的无符号整数
    private uint RandomU32()
    {
        state ^= state >> 12;
        state ^= state << 25;
        state ^= state >> 27;
        return (uint)((state * 0x2545F4914F6CDD1DUL) >> 32);
    }

    // 生成一个在[0, 1)区间的float32随机数
    public float RandomF32()
    {
        return (RandomU32() >> 8) / 16777216.0f;
    }
}

ulong initialState 是生成随机数的初始种子值，用于设定伪随机数生成器的初始状态。每次生成器被实例化时，它的内部状态将从这个初始种子值开始。随机数生成器依赖于内部状态的变化产生随机数，如果您为 initialState 设置一个固定值，那么生成的随机数序列也将是确定的（即伪随机）。

  • 如果您希望生成相同的随机数序列（例如测试或调试目的），您可以设置一个固定的 initialState 值。这样，每次生成器都会产生相同的随机数序列。
  • 如果您希望确保生成的随机数序列尽可能不可预测，您可以使用系统时间、硬件熵源、或者其他随机事件来初始化 initialState。

使用例子

class Program
{
    static void Main()
    {
        // 使用当前系统时间的刻度数作为种子
        ulong seed = (ulong)DateTime.Now.Ticks;

        // 实例化随机数生成器
        RandomNumberGenerator rng = new RandomNumberGenerator(seed);

        // 生成随机数
        float randomValue = rng.RandomF32();
        Console.WriteLine($"Generated Random Float: {randomValue}");
    }
}