2

我正在尝试连续生成一系列随机线性独立的二进制向量，每个向量包含 1024 个元素 0 或 1。我需要生成 1024 个（这也是我能得到的最大值）这样的向量。这是我所做的基本想法

srand( (unsigned) time(NULL) );
while(obtained <= 1024)
{
    for (int i=0;i<1024;i++)
        vector[i] = rand() % 2;

    check linear indepence against previously stored linearly independent vectors

    if (linearly independent)
        store it;
        obtained += 1;
    else
        discard;
 }

但是，这里的代码似乎只能生成 527 个线性独立向量，这很奇怪。我发现这可能是随机数生成器的问题，因为如果我将 srand() 放入循环中，即在每次 rand() 执行之前，它能够完成生成 1024 个这样的向量。但是，程序会很慢。

另外，有趣的是，如果我想生成 1024 个 1024 维随机线性独立向量，这些向量由从 Galois 域 GF(4) 或更高域而不是二进制域中选择的元素组成，上面的代码段可以正常工作。

请注意，这里的线性独立性是在有限域中的操作方面。

任何人都可以帮助解释可能的原因并建议一些方向吗？衷心感谢。

4

2 回答 2

2

看来您正在使用具有低质量实现的 C 库rand。例如，MSVC 的 CRT 中的实现是出了名的糟糕。

您所做的实际上与测量随机数生成器质量的常见统计测试非常相似。矩阵秩测试创建随机二进制矩阵，计算它们的秩，并测试秩分布是否与预期分布匹配。本质上，您的代码无法创建满秩二进制矩阵。

您可以使用更好的 RNG（可能来自第三方库）或尝试以下方法之一：

  • 使用返回的值的不同位rand。
  • rand在一定次数的迭代后再次调用并丢弃该值。由于 1024 是 2 的幂，这可能是随机值出现某种重复的原因。
  • 使用来自单次调用的更多位rand. 确保检查系统上 RAND_MAX 的值。
于 2013-10-20T21:28:38.040 回答
0

我很高兴地说我已经通过在 GNU 科学图书馆 (GSL) 中使用 RNG 解决了这个问题。现在使用gsl_rng_mt19937RNG 代替 unix 标准 rand()。

于 2013-10-21T16:32:11.647 回答