Odd Repetitions of Patterns When Using Rand()

user_13651625 0
Viewed 67

Sample random password/string generator which generates 32 character strings. So, generates random numbers and keep those which are between 33 and 127 as these are the ASCII values which constitute valid text.

#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;
}

Output repeats the string DEX&H1_(okd/YVf8;49=el%<j:@"T,NU in one form or another.

Some Outputs :

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

Compiled with cc file.c -o file on Clang/macOS.

generator random c
2 Answers

The way you're trying to get random numbers in a range is extremely inefficient. It's also most likely the source of the repetition you're seeing.

You should instead reduce the number returned to be within the desired range.

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

The question of how to do it right has been addressed in another answer already. This is about the "*odd repetitions" part, which may not be so "odd" after all.

The following assumes a typical rand() implementation where:

  • all possible values are taken exactly once before rand() returns a previous value;

  • the next rand() value depends only on the previous value.

Under these assumptions, the 94 values between 34 = '\"' and 125 = '}' will be returned in a cycle, which will then repeat unchanged. Then the posted code will always return 32 consecutive characters from that cycle (including wraparound)

Suppose for example that the first run returns the 32-char string DEX&H1_(okd/YVf8;49=el%<j:@"T,NU. That means the 94-char cycle of the rand() generator includes that string followed by some permutation of the remaining 62 characters.

Then the next run will produce a 32-char string that overlaps the first one for at least, say, 16 characters iff the first eligible character has an index between [0, 15] or [78, 93]. The probability of that happening is 16 / 94 ≈ 17%. Conversely, the probability of not having such overlap is ≈ 83%, and the probability of no overlaps in the next 7 runs is 0.83^7 ≈ 0.27. So the chance of getting a "repetition" for the first string in the next 7 runs is ≈ 73% i.e. not too surprising.

[ EDIT ]   Also, it follows by a straight pigeonhole argument that any 6 runs will produce at least two strings that have a substring in common of length 16 or more.

user_55384200
Related