寻找体面的质量PRNG只有32状态位 [英] Looking for decent-quality PRNG with only 32 bits of state

问题描述

我想实施 rand_r 接口，它有它的整个状态存储在类型的单个对象的不幸接口要求的可容忍质量版本无符号，这对我而言意味着恰好有32位。此外，我需要它的输出范围为 [0,2³¹-1] 。标准的解决方案是使用LCG和删除低位（其中有在最短的时间），但仍留下了未来数位非常差时期。

I'm trying to implement a tolerable-quality version of the rand_r interface, which has the unfortunate interface requirement that its entire state is stored in a single object of type unsigned, which for my purposes means exactly 32 bits. In addition, I need its output range to be [0,2³¹-1]. The standard solution is using a LCG and dropping the low bit (which has the shortest period), but this still leaves very poor periods for the next few bits.

我最初的想法是使用LCG两个或三个迭代来生成输出的高/低或高/中/低位。然而，这样的方法并不preserve非偏压分布;而不是相同的频率每产值，很多出现多次，有的根本就不会发生。

My initial thought was to use two or three iterations of the LCG to generate the high/low or high/mid/low bits of the output. However, such an approach does not preserve the non-biased distribution; rather than each output value having equal frequency, many occur multiple times, and some never occur at all.

由于只有32状态的位，PRNG的周期由2³²界，并以是非偏置，所述PRNG必须输出每个值恰好两次，如果它有充分期间或正好一次，如果它有期间2³¹。较短的时间不能是非偏置

Since there are only 32 bits of state, the period of the PRNG is bounded by 2³², and in order to be non-biased, the PRNG must output each value exactly twice if it has full period or exactly once if it has period 2³¹. Shorter periods cannot be non-biased.

有没有符合这些标准的任何已知的完好PRNG算法？

Is there any good known PRNG algorithm that meets these criteria?

推荐答案

在阐述我的意见......

Elaborating on my comment...

在计数器模式下的分组密码给出大致如下形式发电机（除了使用更大的数据类型）：

A block cipher in counter mode gives a generator in approximately the following form (except using much bigger data types):

uint32_t state = 0;
uint32_t rand()
{
    state = next(state);
    return temper(state);
}

由于密码安全性尚未指定（在32位会或多或少徒劳的），一个简单的，即席回火功能应该做的伎俩。

Since cryptographic security hasn't been specified (and in 32 bits it would be more or less futile), a simpler, ad-hoc tempering function should do the trick.

一种方法是其中的next（）功能简单（如返回状态+ 1; ）和脾气（）由是复杂的（如在分组密码）进行补偿。

One approach is where the next() function is simple (eg., return state + 1;) and temper() compensates by being complex (as in the block cipher).

一个更加平衡的方法是实现LCG在的next（），因为我们知道，它也访问所有可能的状态，但在随机（ISH）秩序，找到一个实现脾气（）这不只是足够的工作覆盖LCG的遗留问题。

A more balanced approach is to implement LCG in next(), since we know that it also visits all possible states but in a random(ish) order, and to find an implementation of temper() which does just enough work to cover the remaining problems with LCG.

梅森倍捻机包括其输出这样的回火功能。这可能是合适的。此外，这个问题要求其履行要求操作。

Mersenne Twister includes such a tempering function on its output. That might be suitable. Also, this question asks for operations which fulfill the requirement.

我有一个最喜欢的，这是位反转的单词，然后由某个常数（奇）数相乘。这可能是过于复杂，如果位反转是不是在你的架构原生操作。

I have a favourite, which is to bit-reverse the word, and then multiply it by some constant (odd) number. That may be overly complex if bit-reverse isn't a native operation on your architecture.

这篇关于寻找体面的质量PRNG只有32状态位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！