使用 Rand() 时模式的奇怪重复

Question

随机样本 password/string 生成器生成 32 个字符串。因此，生成随机数并保留 33 到 127 之间的随机数，因为这些是构成有效文本的 ASCII 值。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    srand(time(0));
    clock_t start = clock();

    long long iterations = 0;

    printf("Generating String...\n\n\t\" ");

    for (int i = 0; i < 32; i++)
    {
        long long holder = 0;
        while(holder < 33 || holder > 126)
        {
            holder = rand();
            iterations++;
        }
        putchar(holder);
    }

    clock_t end = clock();

    printf(" \"\n\n%.2lf s , %lld iterations & %lld avg\n",(double)(end - start)/CLOCKS_PER_SEC,iterations,iterations/32);

    return 0;
}

输出以一种或另一种形式重复字符串 DEX&H1_(okd/YVf8;49=el%<j:@"T,NU。

一些输出：

Generating String...

    " DEX&H1_(okd/YVf8;49=el%<j:@"T,NU "

9.11 s , 893836506 iterations & 27932390 avg

Generating String...

    " xq?!#O]tDEX&H1_(okd/YVf8;49=el%< "

7.59 s , 768749018 iterations & 24023406 avg

Generating String...

    " MJxq?!#O]tDEX&H1_(okd/YVf8;49=el "

7.63 s , 748742990 iterations & 23398218 avg

在 Clang/macOS 上用 cc file.c -o file 编译。

Answer 1

您尝试获取范围内随机数的方法效率极低。它也很可能是您看到的重复的来源。

您应该将返回的数字减少到所需范围内。

for (int i = 0; i < 32; i++)
{
    int holder = (rand() % (126 - 33 + 1)) + 33;
    putchar(holder);
}

Answer 2

另一个答案中已经解决了如何正确执行的问题。这是关于“*odd repetitions”的部分，之后可能不是那么“odd”全部.

以下假设 typical rand() implementation 其中：

所有可能的值都在 rand() return 前一个值之前恰好取一次；
下一个 rand() 值仅取决于前一个值。

在这些假设下，34 = '\"' 和 125 = '}' 之间的 94 个值将在一个循环中被 returned，然后将重复不变。然后发布的代码将始终 return 来自该循环的 32 个连续字符（包括环绕）

假设第一个运行 return 是 32 个字符的字符串 DEX&H1_(okd/YVf8;49=el%<j:@"T,NU。这意味着 rand() 生成器的 94 字符循环包括该字符串，后跟剩余 62 个字符的一些排列。

然后下一个运行将产生一个 32 个字符的字符串，它与第一个字符串重叠至少 16 个字符，前提是第一个符合条件的字符的索引介于 [0, 15] 或 [78, 93]。发生这种情况的概率是 16 / 94 ≈ 17%。反之，没有这种重叠的概率是≈ 83%，在接下来的7运行秒内没有重叠的概率是0.83^7 ≈ 0.27。因此，在接下来的 7 运行秒中第一个字符串获得“repetition”的机会是 ≈ 73% 即不足为奇。

[ EDIT ] 此外，它后面跟着一个直接的 pigeonhole 论点，即任何 6 运行将产生至少两个具有子字符串的字符串长度为 16 或以上的共同点。

使用 Rand() 时模式的奇怪重复

Odd Repetitions of Patterns When Using Rand()

c

random

generator