非迭代随机数序列的简单公式是什么? [英] What is a simple formula for a non-iterative random number sequence?

问题描述

我想拥有一个函数f(x)，该函数根据值x给出均匀分布的良好伪随机数.我知道线性同余生成器，但是这些都是迭代生成的，即我提供了初始种子，然后逐个得到一系列随机值.这不是我想要的，因为如果要让我们说序列中的第200000个数字，我必须计算数字1 ...199999.我需要一个函数，该函数由一个使用基本运算(例如+)的简单公式给出，*，mod等.我也知道哈希函数，但是找不到适合这些需求的函数.我可能自己想出了一些函数，但是我想使用经过测试的函数来提供合适的伪随机值.有没有类似的东西被使用?

I would like to have a function f(x) that gives good pseudo-random numbers in uniform distribution according to value x. I am aware of linear congruential generators, however these work in iterations, i.e. I provide the initial seed and then I get a sequence of random values one by one. This is not what I want, because if a want to get let's say 200000th number in the sequence, I have to compute numbers 1 ... 199999. I need a function that is given by one simple formula that uses basic operations such as +, *, mod, etc. I am also aware of hash functions but I didn't find any that suits these needs. I might come up with some function myself, but I'd like to use something that's been tested to give decent pseudo-random values. Is there anything like that being used?

推荐答案

您可能会考虑乘法同余生成器.它们是没有加法常数的线性同余式:对于合适的常数a和c，X _{i + 1} = aX _i ％c.将其扩展一些迭代将使您相信X _k = a ^k X ₀ ％c，其中X ₀ 是您的种子值.可以使用快速模块化幂运算以O(log(k))时间进行计算.无需计算第一个199,999就可以得到200,000 ^th 值，您可以按大约18步的比例找到它.

You might consider multiplicative congruential generators. These are linear congruentials without the additive constant: X_i+1 = aX_i % c for suitable constants a and c. Expanding this out for a few iterations will convince you that X_k = a^kX₀ % c, where X₀ is your seed value. This can be calculated in O(log(k)) time using fast modular exponentiation. No need to calculate the first 199,999 to get the 200,000^th value, you can find it in something proportional to about 18 steps.

这篇关于非迭代随机数序列的简单公式是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！