使用C++11实现确定性均匀分布

Question

使用C++11实现确定性均匀分布

3

我正在使用C++11的随机库生成确定性随机值，我需要将输出限制在不同范围内，并自然地使用了std::uniform_int_distribution，但令我失望的是，规范给了库实现太多的自由度，因此在X86-64 Linux和X86 Windows 7之间输出有所不同。

除了实现自己的分布以确保输出是确定性的，还有其他选项吗？

- bsdunx

2

你使用的是哪个随机数引擎？ - jbgs

@jbgs 我已经测试了各种随机引擎的输出，并且它们确实在不同的STL实现中按照广告所述正常工作。 - bsdunx

2个回答

1

如果一个LCG已经足够满足你的需求，那么使用应用程序提供的一些固定常量实例化std::linear_congruential_engine 应该会产生确定性输出。

typedef uint64_t number;
constexpr number a {1};
constexpr number c {2};
constexpr number m {3};
constexpr number seed {0};
std::linear_congruential_engine<number, a, c, m> lcg {seed};
std::uniform_int_distribution<number> dist {0, 1000};
for (int i = 0; i < 10; ++i)
  std::cout << dist(lcg) << std::endl;

请注意，我故意选择了荒谬的值来代替a、c和m，以免在关于哪组参数是好的这个争论中持任何一方。

- 5gon12eder

LCG 是我测试过的引擎之一，PRNG 本身不是问题所在，输出的差异在于分布。 - bsdunx

1

好的，那么在这种情况下使用 offset + lcg() % range 可能是最简单的方法。幸运的是，你只需要均匀的整数分布。 - 5gon12eder

谢谢您的评论，那正是我要前往的地方。目前我的主要担忧是引入偏见，但嘿，现在应该足够好用，而且稍后替换起来也不难。 - bsdunx

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Howard Hinnant · Accepted Answer

除了实现自己的分布以确保输出是确定性的，无论库的实现如何，没有其他选项。虽然引擎是确定性的，但分布不是。典型的uniform_int_distribution实现将涉及"拒绝"算法，该算法将重复从URNG获取数字，如果该结果不在所需范围内，则丢弃它并再次尝试。该主题的变化将通过将超出范围的值折叠到范围内的值中来优化该算法，以最小化拒绝而不偏移接受范围，就像简单的offset + lcg() % range算法一样。