65.9K
CodeProject 正在变化。 阅读更多。
Home

CR-XAM

Jacob F. W.
starIconstarIconstarIconstarIconemptyStarIcon

4.00/5 (1投票)

2012年11月22日

公共领域

9分钟阅读

viewsIcon

18082

downloadIcon

285

一个简单但出奇有效的随机数生成器

介绍 

今天我想介绍一个我开发的随机数生成器，名为CR-XAM。这是一个简单高效的算法，能够生成质量惊人的随机输出。到目前为止，我已经用以下工具测试了它：

...它以出色的成绩通过了所有测试。我还没有用其他测试套件进行测试，例如：

...所以还不能完全下结论。但与线性同余发生器（LCGs）和线性反馈移位寄存器（LSFRs）等其他简单生成器相比，它生成的质量要好得多，而速度的下降却非常小。

背景 

那么，CR-XAM到底是什么意思呢？CR-XAM是组成随机数生成器的五个操作的首字母缩写：Counter（计数器）、Rotate（旋转）、Xor（异或）、Add（加法）、Multiply（乘法）。我喜欢它的发音，也喜欢它为一个简单的RNG（随机数生成器）所做的简单操作提供一个简单的名字……简单来说就是这样。

现在让我们深入研究一下代码。首先，我想向您展示如何使用这些代码，然后我们将看一下算法本身。

使用代码

如果您查看上面的两个文件，您会看到一个名为crxam32.zip和一个名为crxam64.zip的文件。区别在于，正如您可能猜到的那样，crxam32在其状态中使用32位无符号整数，而crxam64使用64位无符号整数。32位版本的周期约为2^48字节，而64位版本的周期为2^96字节。在下面的示例中，我将使用64位版本，但两个版本中的代码几乎完全相同。

此外，尽管比特大小不同，这两个生成器在每次调用后都会返回一个字节。当谈到算法时，我将解释原因。

种子 

对于任何随机数生成器，第一步都是对其进行“播种”（seeding）。CR-XAM在播种方面有3种不同的选择。在这3种情况下，播种过程都使用了stdlib.h中的rand()函数。

1） crxam64_seed(uint32 Seed)

第一种选择是，用户可以提供一个种子。在这种情况下，Seed（一个32位无符号整数）被传递给srand()。然后，CR-XAM使用rand()来创建初始状态。

void crxam64_seed(uint32 Seed)
{
    srand(Seed);
    setup();  // The function that creates the state
}

2） crxam64_init(void)

第二种选择是调用crxam64_init()。这将使用当前时间（time(0)）创建一个种子。这个过程非常简单。

void crxam64_init(void)
{
    time_t Seed = time(0);
    Seed += (Seed >> 32);
    srand(Seed & 0xffffffff);
    setup();  
}

3） 只需调用crxam64_genrand(void)

最后，如果您在未先调用crxam64_seed()或crxam64_init()的情况下调用crxam64_genrand()来开始获取随机数，它将直接使用rand()创建一个初始状态，而不先调用srand()。

byte crxam64_genrand(void)
{
    if(!IsSeeded)
    {
         setup();
    }
    ....
    // Rest of code will be shown later.

生成随机数 

现在我们已经为生成器播种完毕，我们需要开始获取一些随机数。同样，这个过程非常简单。

byte B = crxam64_genrand();
 
// OR

for(size_t I = 0; I < Buffer_len; I++)
{
    Buffer[I] = crxam64_genrand();
}

同样，crxam64_genrand()和crxam32_genrand()都返回一个字节。

注意：我清楚地知道，随机数生成器最常被使用的场景是需要32位整数甚至双精度浮点数，而不是单个字节。我将在几天内发布一些代码，使CR-XAM的使用更加方便，并更容易生成更大范围内的浮点数和整数（即Min和Max之间的随机数）。在此期间，对于由此带来的任何不便，我深表歉意。

以上就是允许您使用生成器的函数调用。现在，让我们更深入地看看幕后发生的事情。

状态 

RNG（随机数生成器）的状态是用于生成随机数的所有变量和比特。我认为，具体来说，它们是所有可以被播种过程改变的变量。

  // Generator State
static uint64 Xc;
static uint64 Ac;
static uint64 Mc;
 
static byte Xr;
static byte Ar;
static byte Mr;
 
static uint64 Accum;
static int IsSeeded = 0; // Flag

在解释不同变量之前，我想先指出，crxam64中的uint64和crxam32中的uint32数据类型，以及byte和在另一个文件"stdtypes.h"中声明的typedefs。

typedef unsigned char byte;
typedef unsigned long int uint32;
typedef unsigned long long int uint64;

我相信大多数人都已经明白了，但我不希望任何人感到困惑。是的，我知道<stdint.h>中几乎有相同的东西。

// Found in stdint.h>
uint32_t;
uint64_t;

个人而言，那个小小的“_t”后缀让我很恼火。您可能会觉得我有点疯狂，但我认为它只是让我的代码变得不必要的杂乱。我自己已经制造了很多杂乱的东西了，谢谢。我不需要标准库强加给我的杂乱。

设置 - 播种过程

在前面的代码中，我向您展示了可用于播种生成器的不同函数。所有这3个选项都使用了同一个函数：setup()。

static void setup(void)
{
    Accum = 0;
    Xc = Ac = Mc = 0;
 
    for(int I = 0; I < 8; I++)
    {
         Accum = (Accum << 8) | (rand() & 0xff);
	 Xc = (Xc << 8) | (rand() & 0xff);
	 Ac = (Ac << 8) | (rand() & 0xff);
	 Mc = (Mc << 8) | (rand() & 0xff);
    }
 
    Xr = rand() & 0xff;
    Ar = rand() & 0xff;
    Mr = rand() & 0xff;
 
    IsSeeded = 0xffff;
}

你们中的许多人可能想知道，为什么我只用rand()来播种生成器？为什么我只允许用户传入一个32位种子，而不是一整串字节？为什么？为什么？为什么？？？

我有3个原因：

  1. 这使得播种过程更简单。您不必担心获取一整串随机字节，只需担心一个32位整数。
  2. 使用一个质量较低的生成器来播种一个高质量的生成器是一种常见的做法。有几种实现梅森旋转算法（Mersenne Twister），如果愿意的话，可以称之为RNGs中的兰斯洛特爵士，它们使用一个滞后斐波那契生成器（Lagged Fibonacci Generator）来播种梅森旋转算法。
  3. 我希望CR-XAM能在人们以前使用stdlib.h中的rand()的地方得到使用。这使得用crxam64_seed(Seed)替换srand(Seed)变得更容易。（是的，我知道rand()返回一个short。我正在努力改进它！！！）。

crxam64_genrand()

最后但同样重要的是，这颗心脏的“小黑匣子”。

byte crxam64_genrand(void)
{
    if(!IsSeeded)
    {
        setup();
    }
 
    Accum = rotl(State, ++Xr);
    Accum ^= ++Xc;
 
    Accum = rotr(State, ++Ar);
    Accum += ++Ac;
 
    Accum = rotl(State, ++Mr);
    Accum *= ++Mc;
 
    return (Accum >> 56) & 0xff;
}

很简单，不是吗？

算法

好了，我们已经看完了所有代码，现在来讨论一下它是如何工作的。

首先，rotr()和rotl()函数是位旋转。这些是非常常用的函数，所以我不打算在这里深入介绍。如果您从未听说过它们，它们会移动比特，但不会像普通的移位那样丢弃一端的比特并在另一端填充0，而是会将将要掉落的比特移到另一端。

同样，算法也非常简单。其伪代码相当直观。

  1. 将变量Xr、Xc、Ar、Ac、Mr和Mc加1。不用担心溢出。
  2. 将Accum左旋转Xr位，然后与Xc进行异或。将结果存回Accum。
  3. 将Accum右旋转Ar位，然后将Ar加到Accum上。将结果存回Accum。
  4. 将Accum左旋转Mr位，然后与Mc相乘。将结果存回Accum。
  5. 返回Accum的最高8位（1字节）作为输出。

我最喜欢的算法方面之一是，您可以根据需要将其改编为任何大小的整数（尽管那样您可能需要担心溢出）。

现在我们来谈谈状态。我试图给变量起一些简单但显而易见的名字。第一个字母X、A和M都描述了它们所涉及的操作。

  • Xr和Xc参与异或阶段，
  • Ar和Ac用于加法阶段。
  • Mr和Mc用于乘法阶段。

此外，最后一个字母r和c分别表示旋转和计数器（技术上所有变量都是计数器，但我喜欢这种命名约定，所以决定坚持下去）。

Accum是所有操作执行的变量。它是所有随机数的累积处，也是输出的来源。

操作

计数器、旋转、加法和异或是构建密码学原语常用的方法。乘法是一个例外。已故的George Marsaglia，Diehard测试的创建者，也是一位备受尊敬的随机数生成器权威，他曾说过，根据他的经验，乘法在混合比特方面比异或或加法做得更好（我很抱歉，我不记得我在哪里读到过这段话了。找到来源后，我会发布它）。

输出

与许多其他简单的RNG不同，我没有返回Accum的全部64位作为输出，而是只返回8位。有些人认为这效率低下。认为我本可以获得当前输出量的八倍。然而，我有两个理由来支持我的选择。

  1. 由于乘法运算，最高8位将是混合得最彻底的。通过只使用它们，我们确保获得最佳输出。
  2. 导致大多数简单RNG在高级统计测试中失败的一个常见弱点是，它们中的许多无法生成随机性很小的输出。在某些时候，一个真正的随机数生成器会生成一长串全1或全0。大多数简单RNG失败的原因是，当它们生成输出时，它们同时将输出用作下一个输出的种子。但是，如果它们的种子随机性很小（即，它们是111111111或00000000），它们的生成器将无法生成任何有用的输出。通过只使用最高8位，我们可以确保生成长串的1和0，而不受实际状态有多随机的影响。
     

统计测试

文件Stat_Tests.zip包含了我在文章开头提到的统计测试的结果。我还进行了一项未提及的额外测试，即使用Ent，这是一个执行一些基本统计测试的程序。

Entropy = 7.999998 bits per byte.

Optimum compression would reduce the size
of this 126000000 byte file by 0 percent.

Chi square distribution for 126000000 samples is 276.34, and randomly
would exceed this value 17.13 percent of the times.

Arithmetic mean value of data bytes is 127.5020 (127.5 = random).
Monte Carlo value for Pi is 3.141631810 (error 0.00 percent).
Serial correlation coefficient is -0.000067 (totally uncorrelated = 0.0).

结论  

到目前为止，我对CR-XAM非常满意。它还没有失败任何我用过的测试，我当然希望它能继续下去。如果您发现任何问题或有任何疑问，请随时提出。

希望大家都能从中受益。感恩节快乐！

Jacob W.

历史 

2012年11月22日 - 首次发布
                       - 添加了统计测试结果。

算法许可

由于本文涵盖了我编写的源代码和我提出的算法，我觉得应该涵盖所有方面。

此处呈现的所有源代码以及包含在文件中的源代码均属于公共领域，可随意使用。

我特此将此算法置于公共领域，并放弃所有版税权利和版权。

© . All rights reserved.