Generating a random, non-repeating sequence of all integers in .NET

If you don’t need the random numbers to be cryptographically secure, you can use a Linear Congruential Generator.

An LCG is a formula of the form X_n+1 = X_n * a + c (mod m), it needs constant memory and constant time for every generated number.
If proper values for the LCG are chosen, it will have a full period length, meaning it will output every number between 0 and your chosen modulus.

An LCG has a full period if and only if:

• The modulus and the increment are relatively prime, i.e. GCD(m, c) = 1
• a - 1 is divisible by all prime factors of m
• If m is divisible by 4, a - 1 must be divisible by 4.

Our modulus is 2 ^ 32, meaning a must be a number of form 4k + 1 where k is an arbitrary integer, and c must not be divisible by 2.

While this is a C# question I’ve coded a small C++ program to test the speed of this solution, since I’m more comfortable in that language:

#include <iostream>
#include <stdlib.h>

class lcg {
private:
    unsigned a, c, val;
public:
    lcg(unsigned seed=0) : lcg(seed, rand() * 4 + 1, rand() * 2 + 1) {}
    lcg(unsigned seed, unsigned a, unsigned c) {
        val = seed;
        this->a = a;
        this->c = c;
        std::cout << "Initiated LCG with seed " << seed << "; a = " << a << "; c = " << c << std::endl;
    }

    unsigned next() {
        this->val = a * this->val + c;
        return this->val;
    }
};

int main() {
    srand(time(NULL));
    unsigned seed = rand();
    int dummy = 0;
    lcg gen(seed);
    time_t t = time(NULL);
    for (uint64_t i = 0; i < 0x100000000ULL; i++) {
        if (gen.next() < 1000) dummy++; // Avoid optimizing this out with -O2
    }
    std::cout << "Finished cycling through. Took " << (time(NULL) - t) << " seconds." << std::endl;
    if (dummy > 0) return 0;
    return 1;
}

You may notice I am not using the modulus operation anywhere in the lcg class, that’s because we use 32 bit integer overflow for our modulus operation.
This produces all values in the range [0, 4294967295] inclusive.
I also had to add a dummy variable for the compiler not to optimize everything out.
With no optimization this solution finishes in about 15 seconds, while with -O2, a moderate optimization it finishes under 5 seconds.

If “true” randomness is not an issue, this is a very fast solution.