哪个C++随机数引擎具有O(1)丢弃函数？

Question

自C++11以来，出现了大量的std随机数引擎。它们实现的成员函数之一是void discard(int long long z)，它跳过z随机生成的数字。此函数的复杂度在www.cplusplus.com (发动机/废品/)上以O(z)表示。

然而，在www.cppreference.com (发动机/报废)上有一个注释说

对于某些引擎来说，“快速跳转”算法是众所周知的，它将状态推进了许多步骤(数百万阶)，而无需计算中间状态转换。

我如何知道哪个发动机的实际报废成本是O(1)？

Answer 1

事实上，std::linear_congruential_engine<UIntType,a,c,m>::discard(unsigned long long z)绝对是，可以非常高效地实现。它主要相当于a的幂与z模m的幂(对于零和非零c) --这意味着大多数基本的软件实现都是在O(log(z % phi(m))) UIntType乘法中执行(一般是素数和<m )，并且可以用并行硬件指数算法来实现更快的执行速度。

^^注意，在某种程度上，O(log(z % phi(m)))是O(1)，因为log2(z % phi(m)) < log2(m) < sizeof(UIntType)*CHAR_BIT --尽管在实践中它更像O(log(z))。

此外，对于大多数其他引擎的discard函数也可能有满足O(P(size of state))约束的有效算法(P(x) --一些低次多项式函数，最有可能是1+epsilon度，或者更小的，比如x*log(x)，考虑到log(z) < sizeof(unsigned long long)*CHAR_BIT可以被认为是常数)。

不知为何，C++标准(截至ISO/IEC 14882:2017) 不要求以比z operator()()更高效的方式实现discard，包括那些绝对允许这种的引擎。

对我个人来说，这是令人费解的，只是没有意义的--它粗暴地违反了C++语言设计的基本原则之一，即在C++标准中增加性能和实际用途方面的合理功能。

例如：没有 std::list<T>::operator[](size_type n)这样的东西，尽管它“简单”到只使用迭代器begin()调用operator++() n times。当然，因为O(n)执行时间会使这个函数在任何实际应用程序中都不合理的选择(一个代码词表示“愚蠢的想法”)。由于这个显而易见的原因，a[n]和a.at(n)并不是强制性序列容器要求 (ISO/IEC 14882:2017 26.2.3表87)的一部分，而是可选序列容器操作 (ISO/IEC 14882:2017 26.2.3表88)的一部分。

那么，为什么在世界范围内，e.discard(z)是强制性随机数引擎需求 (ISO/IEC 14882:2017 29.6.1.4表104)的一部分？？它有着荒谬的复杂性要求-- no worse than the complexity of z consecutive calls e() --而不是一些具有足够复杂要求的可选操作节条目，比如O(size of state)或O(P(size of state))。

更令人费解的是，在我的GCC身上，这个现实世界的实现：

void discard(unsigned long long __z)
{
    for (; __z != 0ULL; --__z)
        (*this)(); //<--  Wait what? Are you kidding me?
}

所以再一次和以前一样，我们别无选择，只能自己实现必要的功能.

Answer 2

我认为这种事情根本不存在。我的启发式结论是，O(1)-jump RNG基本上是一个散列，这意味着(例如，它可能根本不是“好的”RNG )。(见@AkiSuihkonen的新答案及其链接。)

但是，即使您询问的是O(log z)，我也不认为这是在STL中实现的。在GCC的所有discard函数中，我能够grep都是简单的循环。

      discard(unsigned long long __z)
      {
        for (; __z != 0ULL; --__z)
          (*this)();
      }

这不仅令人悲伤，而且误导人，因为只有有一种有效的方法，discard才会存在。

唯一重要的是mersenne (下面)，但它仍然是O(z)。

    discard(unsigned long long __z)
    {
      while (__z > state_size - _M_p)
    {
      __z -= state_size - _M_p;
      _M_gen_rand();
    }
      _M_p += __z;
    }

Boost的Mersenne有一个skip函数，但它只对大于(默认值为10000000 ) (!?)的跳转调用。这已经告诉我，在计算上跳过非常重(即使是O(log z))。twister.hpp

最后，推力有一个有效的discard线性同余明显，但只有在c == 0的情况下。(我不确定它作为RNG是否不太有用) aec05b19d2a85d02f1ff437791ea4dd68.html#aec05b19d2a85d02f1ff437791ea4dd68。

Answer 3

全基于计数器的随机数发生器

这些工作仅仅是通过计算一个函数uint64_t rnd(uint64_t counter)或uint16_t rnd(uint128_t counter)来完成的。然后跳过函数就像

// the method itself is "randomly" generated -- known at least
// by von Neumann to typically generate poor results
struct MyRandomCBRNG {
    uint64_t counter{0};
    void skip(uint64_t a) { counter+=a;}

    uint64_t operator()() {
        uint64_t x = counter++;
        // repeat multiple times if needed
        x = x * 0xdeadbeefcafebabeull ^ (x >> 53) ^ (x << 11) + 0x13459876abcdfdecull;
        return x;
    }
};

人们甚至可以通过使用类似SHA-512之类的秘密密钥来散列计数器，从而使CBRNG具有更强的密码学性能，更不用说Blum了。