ale*_*ack 6 random complexity-theory c++11
从C++ 11开始,有许多std随机数引擎.他们实现的成员函数之一是void discard(int long long z)跳过z随机生成的数字.此功能的复杂性在www.cplusplus.com上以O(z)的形式给出(http://www.cplusplus.com/reference/random/mersenne_twister_engine/discard/)
但是,在www.cppreference.com(http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine/discard)上有一条说明
对于一些引擎,已知"快速跳跃"算法,其在不计算中间状态转换的情况下将状态推进许多步骤(数百万的数量级).
我怎么知道丢弃的实际成本是哪些引擎是O(1)？
好吧，如果您使用预先计算的跳跃点，O(1) 将适用于现有的每个 RNG。请记住，有些算法可能比 O(z) 更好，但不是 O(1) - 比如 O(log 2 z)。
如果我们谈论跳转到任意点，事情就会变得有趣。例如，对于线性同余生成器，存在已知的 O(log 2 z) 跳转算法，该算法基于 F. Brown 的论文“任意步长的随机数生成”，Trans。是。核。苏克。（1994 年 11 月）。代码示例在这里。
C++11 标准中有 LCG RNG，不确定特定实现中的跳转速度有多快（http://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine）
我相信PCG家族的RNG拥有相同的财产
事实上，这std::linear_congruential_engine<UIntType,a,c,m>::discard(unsigned long long z)很容易、非常高效地实施。它主要相当于模数a的幂（对于零和非零） - 这意味着足够的软件实现在乘法+模约减运算中执行（- 对于素数和小于一般情况）。zmcO(log(z % \xcf\x86(m))) UIntType\xcf\x86(m)=m-1m
^^^注意，在某种程度上O(log(z % \xcf\x86(m)))是O(1)因为log2(z % \xcf\x86(m)) < log2(m) < sizeof(UIntType)*CHAR_BIT- 尽管实际上它更像是O(log(z))。
^^^还请注意，在生成一些依赖于模板参数的预计算表（如果合适，可以采用惰性计算或编译时计算）后，求幂复杂度可能会减少到只有几个multiplication + modulo reduction操作（例如 4 或 8） - 即O(1)在每个实际意义上。
此外，对于大多数其他引擎的函数来说，可能有足够有效的算法discard来满足O(P(sizeof(state))*log(z))约束（P(x)-一些低次多项式函数，最可能的1+o(1)次数或最多3+o(1)次数，假设log(z) < sizeof(unsigned long long)*CHAR_BIT可以被视为常数）。
尽管如此：
\n不知何故，出于某种未知的原因，C++ 标准（截至 ISO/IEC 14882:2017）不需要以更有效的方式实现discard，而不仅仅是z operator()()调用任何PRNG引擎，包括那些明确允许此操作的引擎。
对我个人来说，这是令人困惑的，而且毫无意义——它违反了 C++ 语言的基本设计原则之一（以一种非常残酷的方式） ——即只在性能和实际用途方面向 C++ 标准添加合理的功能。
\n值得注意且有大量文档记录的示例：不存在通过索引 ( )访问元素之类的事情，尽管它与仅使用迭代器调用时间一样“简单” 。自然如此 - 因为执行时间会使这个函数在任何实际应用中都是不合理的选择（又名简单的愚蠢想法）。由于这个明显的原因，它不是强制性序列容器要求的一部分（ISO/IEC 14882:2017 26.2.3 表 87 ），而是可选序列容器操作的一部分（ISO/IEC 14882:2017 26.2.3 表 88）。std::liststd::list<T>::operator[](size_type n)operator++() nbegin()O(n)a[n]a.at(n)
那么，为什么世界上e.discard(z)强制随机数引擎要求（ISO/IEC 14882:2017 29.6.1.4 表 104）的一部分具有这种荒谬的复杂性要求 -no worse than the complexity of z consecutive calls e()而不是一些具有足够复杂性要求的可选操作部分条目，例如O(P(sizeof(state))*log(z))？
就像什么...？z consecutive calls e()是指数复杂度——从什么时候开始可以了？
更令人困惑的是在我的 GCC 中实际找到了这个现实世界的实现：
\nvoid discard(unsigned long long __z)\n{\n for (; __z != 0ULL; --__z)\n (*this)(); //<-- Wait what? Are you kidding me?\n}\n因此，与之前一样，我们别无选择，只能自己实现必要的功能……C++ 标准库没有提供太多帮助。
\n修正案：
\n当深入研究Mersenne Twister的设计细节时，我们发现std::mersenne_twister_enginediscard(z)的设计细节也可以非常有效地实现。
为了
\ntemplate<\n class UIntType,\n std::size_t w, std::size_t n, std::size_t m, std::size_t r, UIntType a,\n std::size_t u, UIntType d, std::size_t s, UIntType b, std::size_t t, UIntType c,\n std::size_t l, UIntType f\n> class mersenne_twister_engine;\n即使通用实现discard(z)（适用于整个线性 PRNG 模 2 类 - 不仅是Mersenne Twister，还包括WELL和许多其他）也会具有复杂性，例如O(n^\xcf\x89*log(z))-上面的模板参数在哪里 -位字n中的状态大小，以及幂\xcf \x89是 2 到 3 之间的常数（取决于所选的位矩阵乘法算法）。通过对实际执行时间进行合理数量的依赖于模板参数的预计算，可以轻松降低复杂性。SIMD CPU 指令（向量 XOR 或向量 AND）会将实际性能提高一个常数因子。并行算法（例如专用硬件解决方案）将使用同步单位计算（XOR 和 AND）及时计算此值。wO(n^\xcf\x89)O(log(n))O(n^3)
当然，您可能会注意到n上面的参数通常不是那么小（例如 624 forstd::mt19937或 312 for std::mt19937_64），并且n-cubed 甚至更大 - 因此O(n^3)实际执行速度不一定很快。但现代 CPU（尤其是 GPU）仍然可以相当快地执行优化实现 - 无法与z consecutive calls of operator()().
一些一般观察：
\n每一个现有的PRNG（以及我能想象到的每一个）都可以用以下迭代方程来定义：
\nx[n+1] = T(x[n])\nOutput[n] = F(x[n])\n其中是迭代后的x[n]状态（某个W位序列） （初始状态也称为种子），是状态迭代变换函数（将当前状态转换为下一个状态），是输出变换，将每个状态位序列转换为输出- 位序列 ( ) - 通常。nx[0]T(x)F(x)WvOutput[n]v < W
当然，在最坏的情况下，T(x)和F(x)计算都很快 - 即最大时间是多项式。O(P(W))（通常这些函数被设计得更快 - 就像在大多数情况下O(P(v))本质上一样，因为通常选择 CPU 寄存器大小，并且通常可用于该大小的快速硬件优化操作）。O(1)v
我的意思是字面上的意思 - 所有现有（和未来）有意义的 PRNG 都可以用这种方式表达。
\n（我能想到的唯一进一步的概括是使W和v大小变得非常量 - 即依赖于n- 即从一次迭代更改为下一次迭代。这可能没有太多实际意义 - 我想没有人想要他们的 PRNG 内部数据无限增长并最终消耗所有 RAM 或类似的东西。即使增长非常缓慢也W可以允许非周期性 PRNG 设计。）
所以问题是：PRNG 的什么属性可以使discard(z)运算速度更快- 即使用多项式 -O(P(W))最坏情况下的运行时间？
IMO 非常明显的答案是，如果我们可以执行函数的快速计算 -T^z(x) = T(T(...T(x)...)) - z times对于任何z那么我们可以快速实现discard(z)。
另外，不难注意到IF T(x) = T_p(x)是具有某些内部固定参数的参数化变换p，它是具有变化参数值的一类变换之一，并且对于任何允许的参数值q变换T_q(x)都可以快速及时计算O(P(W))。而且，如果对于任何允许的参数值p和q变换T_p(T_q(x))也属于此类具有某些允许参数的变换r- 即T_p(T_q(x)) = T_r(x)可以r从参数快速计算p并且q......假设我们定义一个符号r=p*q- 哪里*是一些可快速计算的二元运算（以多项式形式）最多时间） - 所以T_{p*q}(x) = T_p(T_q(x)) 根据定义。（您可以注意到，二元运算*不一定是可交换的 - 即p*q不一定是与 相同的值q*p。但此运算在设计上是结合的T_p(T_q(T_r(x))) = T_p(T_{q*r}(x)) = T_{p*q}(T_r(x))- 因为- 因此p*(q*r)=(p*q)*r。）
^^^这种T(x)变换结构显然允许快速计算T^z(x)变换：如果T(x) = T_p(x)和 参数p已知 - 我们只需计算q=p^z=p*p*p*...p - z times（这只是O(log(z))的计算*，并且可以通过预计算和/或并行执行进行优化），然后我们计算T_q(x)。
^^^ 虽然这么多先决条件看起来像是非常特殊的情况 - 事实上所有这些都是很常见的。例如，对于一类模 2 线性变换（如 Mersenne Twister 或 WELL 等），迭代变换可以表示为模 2 算术中的常数位矩阵与状态位向量的乘法 - 以便常数矩阵求幂（模 2 位算术中） ）就可以了。有了std::linear_congruential_engine它就更简单了——自己做数学作为一个简单的练习。基于椭圆曲线的 PRNG 也满足这些条件。（实际上我想知道为什么有人会在没有这个非常有用的属性的情况下设计 PRNG。-但这只是我。）
| 归档时间： |
|
| 查看次数： |
361 次 |
| 最近记录： |