c - 生成随机线性无关二元 vector 的问题

Question

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

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 个线性独立 vector ，这很奇怪。我发现这可能是随机数生成器的问题，因为如果我将 srand() 放入循环中，即在每次 rand() 执行之前，它能够完成生成 1024 个这样的 vector 。但是，程序会非常慢。

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

请注意，这里的线性独立性是指有限域中的运算。

任何人都可以帮助解释可能的原因并建议一些查看方向吗？真诚地感谢。

Answer 1

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

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

您可以使用更好的 RNG(可能来自第三方库)或尝试以下方法之一:

• 使用 rand 返回值的不同位。
• 在一定次数的迭代后再次调用rand并丢弃该值。由于 1024 是 2 的幂，这可能是随机值出现某种重复的原因。
• 通过单次调用 rand 使用更多位。请务必检查您系统上的 RAND_MAX 值。