Improving Random Numbers

In the WikiWiki page LinearShuffle AndyPierce wrote:

Use an imperfect random number generator to create a distribution which approximates true randomness.

I make no claims of perfection but this is O(1). Many times when I've been working with an imperfect PseudoRandomNumberGenerator I've used a trick taught to me in the 1960's by a teacher/colleague/friend BobParslow?. -- DickBotting

---

Idea. Use the imperfect stream of numbers to fill and access a buffer. Use one new number to pick a number from the buffer and output that. Replace it by the next number.

Details. N is a small constant number, by default 10. Construct the new more perfect RNG by filling up an array B of N numbers from the imperfect RNG. Each call for a new number needs two bad random numbers: i is a random subscript for B and n is the next bad random number. Return B[i] and set B[i] to n. See implementation below.

Analysis. The buffer can only further randomize the order of numbers from a sequence, it will not change the numbers. It will not correct, for example, a statistical bias. Consider a RNG that produces even number twice as frequently as odd numbers. The buffer will be filled, on average, with twice as many even numbers as odd, and choosing from it with any statistic will maintain this bias.

---

Interesting differences. Using this method, with RANDOM_BUFFER_SIZE = 10, badRand is the instance of the standard java.util.Random class, and randomNumbers is the array of pre-generated randoms:

    public long nextRandom() {
        int nextIndex = badRand.nextInt(RANDOM_BUFFER_SIZE);
        long nextRand = badRand.nextLong();
        long result = randomNumbers[nextIndex] ^ nextRand;
        randomNumbers[nextIndex] = nextRand;
        return result;
    }

will generate 20155060 in 10 seconds on my test setup.

Same environment, using java.security.SecureRandom?, generates just 2100962 in 10 seconds. Specific results will vary across platforms, but the magnitude of the difference is consistently large. --StevenNewton

But does your method make any hard guarantees about the stream of numbers as far as cryptographic strength goes? What would be more interesting, I think, than comparing the apples and oranges of a CSPRNG and a cobbled PRNG would be to run StatisticalTestsForRandomness? on the output of various PRNG's and their modified counterpart, even with different buffer sizes. Just sayin'.

---

Knuth tried this...Took like 10 random number algorithms and used one of them to choose an algorithm, then took random number from that algorithm. Found non-randomness in the result using std tests.

But that is different from what is described above. The technique with the buffer is discussed by Knuth in TheArtOfComputerProgramming, and he recommends it.