171

I made a class called QuickRandom, and its job is to produce random numbers quickly. It's really simple: just take the old value, multiply by a double, and take the decimal part.

Here is my QuickRandom class in its entirety:

public class QuickRandom {
    private double prevNum;
    private double magicNumber;

    public QuickRandom(double seed1, double seed2) {
        if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
        prevNum = seed1;
        if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
        magicNumber = seed2;
    }

    public QuickRandom() {
        this(Math.random(), Math.random() * 10);
    }

    public double random() {
        return prevNum = (prevNum*magicNumber)%1;
    }

}

And here is the code I wrote to test it:

public static void main(String[] args) {
        QuickRandom qr = new QuickRandom();

        /*for (int i = 0; i < 20; i ++) {
            System.out.println(qr.random());
        }*/

        //Warm up
        for (int i = 0; i < 10000000; i ++) {
            Math.random();
            qr.random();
            System.nanoTime();
        }

        long oldTime;

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            Math.random();
        }
        System.out.println(System.nanoTime() - oldTime);

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            qr.random();
        }
        System.out.println(System.nanoTime() - oldTime);
}

It is a very simple algorithm that simply multiplies the previous double by a "magic number" double. I threw it together pretty quickly, so I could probably make it better, but strangely, it seems to be working fine.

This is sample output of the commented-out lines in the main method:

0.612201846732229
0.5823974655091941
0.31062451498865684
0.8324473610354004
0.5907187526770246
0.38650264675748947
0.5243464344127049
0.7812828761272188
0.12417247811074805
0.1322738256858378
0.20614642573072284
0.8797579436677381
0.022122999476108518
0.2017298328387873
0.8394849894162446
0.6548917685640614
0.971667953190428
0.8602096647696964
0.8438709031160894
0.694884972852229

Hm. Pretty random. In fact, that would work for a random number generator in a game.

Here is sample output of the non-commented out part:

5456313909
1427223941

Wow! It performs almost 4 times faster than Math.random.

I remember reading somewhere that Math.random used System.nanoTime() and tons of crazy modulus and division stuff. Is that really necessary? My algorithm performs a lot faster and it seems pretty random.

I have two questions:

  • Is my algorithm "good enough" (for, say, a game, where really random numbers aren't too important)?
  • Why does Math.random do so much when it seems just simple multiplication and cutting out the decimal will suffice?
36
  • 154
    "seems pretty random"; you should generate a histogram and run some autocorrelation on your sequence... Jan 24, 2013 at 0:37
  • 63
    He means "seems pretty random" isn't really an objective measure of randomness and you should get some actual statistics.
    – Matt H
    Jan 24, 2013 at 0:38
  • 23
    @Doorknob: In layman's terms, you should investigate whether your numbers have a "flat" distribution between 0 and 1, and see whether there are any periodic/repetitive patterns over time. Jan 24, 2013 at 0:40
  • 22
    Try new QuickRandom(0,5) or new QuickRandom(.5, 2). Those will both repeatedly output 0 for your number. Jan 24, 2013 at 1:00
  • 119
    Writing your own random number generation algorithm is like writing your own encryption algorithm. There is so much prior art, by people who are hyper-qualified, that it's senseless to spend your time trying to get it right. There is no reason not to use the Java library functions, and if you really want to write your own for some reason, visit Wikipedia and look up algorithms there like Mersenne Twister.
    – steveha
    Jan 24, 2013 at 1:00

14 Answers 14

352

Your QuickRandom implementation hasn't really an uniform distribution. The frequencies are generally higher at the lower values while Math.random() has a more uniform distribution. Here's a SSCCE which shows that:

package com.stackoverflow.q14491966;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) throws Exception {
        QuickRandom qr = new QuickRandom();
        int[] frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (qr.random() * 10)]++;
        }
        printDistribution("QR", frequencies);

        frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (Math.random() * 10)]++;
        }
        printDistribution("MR", frequencies);
    }

    public static void printDistribution(String name, int[] frequencies) {
        System.out.printf("%n%s distribution |8000     |9000     |10000    |11000    |12000%n", name);
        for (int i = 0; i < 10; i++) {
            char[] bar = "                                                  ".toCharArray(); // 50 chars.
            Arrays.fill(bar, 0, Math.max(0, Math.min(50, frequencies[i] / 100 - 80)), '#');
            System.out.printf("0.%dxxx: %6d  :%s%n", i, frequencies[i], new String(bar));
        }
    }

}

The average result looks like this:

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  11376  :#################################                 
0.1xxx:  11178  :###############################                   
0.2xxx:  11312  :#################################                 
0.3xxx:  10809  :############################                      
0.4xxx:  10242  :######################                            
0.5xxx:   8860  :########                                          
0.6xxx:   9004  :##########                                        
0.7xxx:   8987  :#########                                         
0.8xxx:   9075  :##########                                        
0.9xxx:   9157  :###########                                       

MR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  10097  :####################                              
0.1xxx:   9901  :###################                               
0.2xxx:  10018  :####################                              
0.3xxx:   9956  :###################                               
0.4xxx:   9974  :###################                               
0.5xxx:  10007  :####################                              
0.6xxx:  10136  :#####################                             
0.7xxx:   9937  :###################                               
0.8xxx:  10029  :####################                              
0.9xxx:   9945  :###################    

If you repeat the test, you'll see that the QR distribution varies heavily, depending on the initial seeds, while the MR distribution is stable. Sometimes it reaches the desired uniform distribution, but more than often it doesn't. Here's one of the more extreme examples, it's even beyond the borders of the graph:

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  41788  :##################################################
0.1xxx:  17495  :##################################################
0.2xxx:  10285  :######################                            
0.3xxx:   7273  :                                                  
0.4xxx:   5643  :                                                  
0.5xxx:   4608  :                                                  
0.6xxx:   3907  :                                                  
0.7xxx:   3350  :                                                  
0.8xxx:   2999  :                                                  
0.9xxx:   2652  :                                                  
11
  • 17
    +1 for numerical data - although looking on raw numbers can be misleading as it does not mean that they have statistically significant difference. Jan 24, 2013 at 1:40
  • 16
    These results vary heavily with the initial seeds passed to QuickRandom. Sometimes, it's close to uniform, sometimes it's much worse than this. Jan 24, 2013 at 2:20
  • 69
    @BlueRaja-DannyPflughoeft Any PRNG where the quality of the output depends highly on the initial seed value(s) (as opposed to internal constants) seems broken to me.
    – user
    Jan 24, 2013 at 9:21
  • 22
    First rule of statistics: plot the data. Your analysis is spot-on, but plotting a histogram shows this much quicker. ;-) (And it’s two lines in R.) Jan 24, 2013 at 10:59
  • 37
    Mandatory quotes: “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” - John von Neumann (1951) “Anyone who has not seen the above quotation in at least 100 places is probably not very old.” - D. V. Pryor (1993) “Random number generators should not be chosen at random.” - Donald Knuth (1986) Jan 25, 2013 at 21:25
133

What you are describing is a type of random generator called a linear congruential generator. The generator works as follows:

  • Start with a seed value and multiplier.
  • To generate a random number:
    • Multiply the seed by the multiplier.
    • Set the seed equal to this value.
    • Return this value.

This generator has many nice properties, but has significant problems as a good random source. The Wikipedia article linked above describes some of the strengths and weaknesses. In short, if you need good random values, this is probably not a very good approach.

4
  • @louism- It's not really "random," per se. The results will be deterministic. That said, I didn't think about that when writing my answer; perhaps someone can clarify that detail? Jan 24, 2013 at 0:56
  • 2
    Floating point arithmetic errors are implementation designed. As far as I know, they are consistent for a certain platform but can differ e.g. between different mobile phones and between PC architectures. Although there are extra 'guard bits' sometimes added when doing a series of floating point calculations in a row, and the presence or absence of these guard bits can make a calculation subtly differ in the result. (guard bits being, e.g., the expansion of a 64 bit double to 80 bits)
    – Patashu
    Jan 24, 2013 at 0:56
  • 2
    Also, keep in mind that the theory behind LCRNGs all assumes that you're working with integers! Throwing floating-point numbers at it will not yield the same quality of results.
    – user149341
    Jan 24, 2013 at 2:09
  • 1
    @duskwuff, you are right. But if the floating point hardware does follow sane rules, doing this is the same as doing it modulo the mantissa size, and the theory applies. Just need extra care in what you are doing.
    – vonbrand
    Jan 24, 2013 at 13:01
113

Your random number function is poor, as it has too little internal state -- the number output by the function at any given step is entirely dependent on the previous number. For instance, if we assume that magicNumber is 2 (by way of example), then the sequence:

0.10 -> 0.20

is strongly mirrored by similar sequences:

0.09 -> 0.18
0.11 -> 0.22

In many cases, this will generate noticeable correlations in your game -- for instance, if you make successive calls to your function to generate X and Y coordinates for objects, the objects will form clear diagonal patterns.

Unless you have good reason to believe that the random number generator is slowing your application down (and this is VERY unlikely), there is no good reason to try and write your own.

2
  • 36
    +1 for a practical answer ... use this in a shoot em up and spawn enemies along diagonals for epic multiple headshots? :D
    – wim
    Jan 24, 2013 at 2:05
  • @wim: you don't need a PRNG if you want such patterns.
    – Lie Ryan
    Jan 25, 2013 at 6:23
110

The real problem with this is that it's output histogram is dependent on the initial seed far to much - much of the time it will end up with a near uniform output but a lot of the time will have distinctly un-uniform output.

Inspired by this article about how bad php's rand() function is, I made some random matrix images using QuickRandom and System.Random. This run shows how sometimes the seed can have a bad effect (in this case favouring lower numbers) where as System.Random is pretty uniform.

QuickRandom

System.Random

Even Worse

If we initialise QuickRandom as new QuickRandom(0.01, 1.03) we get this image:

The Code

using System;
using System.Drawing;
using System.Drawing.Imaging;

namespace QuickRandomTest
{
    public class QuickRandom
    {
        private double prevNum;
        private readonly double magicNumber;

        private static readonly Random rand = new Random();

        public QuickRandom(double seed1, double seed2)
        {
            if (seed1 >= 1 || seed1 < 0) throw new ArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
            prevNum = seed1;
            if (seed2 <= 1 || seed2 > 10) throw new ArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
            magicNumber = seed2;
        }

        public QuickRandom()
            : this(rand.NextDouble(), rand.NextDouble() * 10)
        {
        }

        public double Random()
        {
            return prevNum = (prevNum * magicNumber) % 1;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var rand = new Random();
            var qrand = new QuickRandom();
            int w = 600;
            int h = 600;
            CreateMatrix(w, h, rand.NextDouble).Save("System.Random.png", ImageFormat.Png);
            CreateMatrix(w, h, qrand.Random).Save("QuickRandom.png", ImageFormat.Png);
        }

        private static Image CreateMatrix(int width, int height, Func<double> f)
        {
            var bitmap = new Bitmap(width, height);
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++) {
                    var c = (int) (f()*255);
                    bitmap.SetPixel(x, y, Color.FromArgb(c,c,c));
                }
            }

            return bitmap;
        }
    }
}
6
  • 2
    Nice code. Yes, that is cool. I used to do that too sometimes, it's hard to get a quantifiable measure out of it, but it's another good way to look at the sequence. And if you wanted get a look at sequences of longer than width*height you could xor the next image with this one pixel-per-pixel. I think the QuickRandom picture is much more aesthetically pleasing though, on account of it being textured like a seaweed carpet. Jan 26, 2013 at 22:40
  • The aesthetically pleasing part is how the sequence tends to increase as you go along each row (and then back to the start again) as the magicNumber multiplication produces a number similar to prevNum, which shows the lack of randomness. If we use the seeds new QuickRandom(0.01, 1.03) then we get this i.imgur.com/Q1Yunbe.png! Jan 27, 2013 at 1:19
  • Yes, great analysis. Since it just multiplies mod 1 by a constant clearly before wrapping occurs there will be the increase you describe. Seems like this could be avoided if we took the less significant decimal placings by say multiplying by 1 billion then reducing mod a 256 color palette. Jan 27, 2013 at 4:52
  • Can you tell me what did you use to generate those output images? Matlab?
    – uday
    Jan 30, 2013 at 1:00
  • @uDaY: Take a look at the code, C# and System.Drawing.Bitmap. Jan 30, 2013 at 1:10
37

One problem with your random number generator is that there is no 'hidden state' - if I know what random number you returned on the last call, I know every single random number you will send until the end of time, since there is only one possible next result, and so on and so on.

Another thing to consider is the 'period' of your random number generator. Obviously with a finite state size, equal to the mantissa portion of a double, it will only be able to return at most 2^52 values before looping. But that's in the best case - can you prove that there are no loops of period 1, 2, 3, 4...? If there are, your RNG will have awful, degenerate behavior in those cases.

In addition, will your random number generation have a uniform distribution for all starting points? If it does not, then your RNG will be biased - or worse, biased in different ways depending on the starting seed.

If you can answer all of these questions, awesome. If you can't, then you know why most people do not re-invent the wheel and use a proven random number generator ;)

(By the way, a good adage is: The fastest code is code that does not run. You could make the fastest random() in the world, but it's no good if it is not very random)

1
  • 8
    There is at least one trivial loop on this generator for all seeds: 0 -> 0. Depending on the seed, there may be many others. (For instance, with a seed of 3.0, 0.5 -> 0.5, 0.25 -> 0.75 -> 0.25, 0.2 -> 0.6 -> 0.8 -> 0.4 -> 0.2, etc.)
    – user149341
    Jan 24, 2013 at 1:00
36

One common test I always did when developing PRNGs was to :

  1. Convert output to char values
  2. Write chars value to a file
  3. Compress file

This let me quickly iterate on ideas that were "good enough" PRNGs for sequences of around 1 to 20 megabytes. It also gave a better top down picture than just inspecting it by eye, as any "good enough" PRNG with half-a-word of state could quickly exceed your eyes ability to see the cycle point.

If I was really picky, I might take the good algorithms and run the DIEHARD/NIST tests on them, to get more of an insight, and then go back and tweak some more.

The advantage of the compression test, as opposed to a frequency analysis is that, trivially it is easy to construct a good distribution : simply output a 256 length block containing all chars of values 0 - 255, and do this 100,000 times. But this sequence has a cycle of length 256.

A skewed distribution, even by a small margin, should be picked up by a compression algorithm, particularly if you give it enough (say 1 megabyte) of the sequence to work with. If some characters, or bigrams, or n-grams occur more frequently, a compression algorithm can encode this distribution skew to codes that favor the frequent occurrences with shorter code words, and you get a delta of compression.

Since most compression algorithms are fast, and they require no implementation (as OSs have them just lying around), the compression test is a very useful one for quickly rating pass/fail for an PRNG you might be developing.

Good luck with your experiments!

Oh, I performed this test on the rng you have above, using the following small mod of your code :

import java.io.*;

public class QuickRandom {
    private double prevNum;
    private double magicNumber;

    public QuickRandom(double seed1, double seed2) {
        if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
        prevNum = seed1;
        if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
        magicNumber = seed2;
    }

    public QuickRandom() {
        this(Math.random(), Math.random() * 10);
    }

    public double random() {
        return prevNum = (prevNum*magicNumber)%1;
    }

    public static void main(String[] args) throws Exception {
        QuickRandom qr = new QuickRandom();
        FileOutputStream fout = new FileOutputStream("qr20M.bin");

        for (int i = 0; i < 20000000; i ++) {
            fout.write((char)(qr.random()*256));
        }
    }
}

The results were :

Cris-Mac-Book-2:rt cris$ zip -9 qr20M.zip qr20M.bin2
adding: qr20M.bin2 (deflated 16%)
Cris-Mac-Book-2:rt cris$ ls -al
total 104400
drwxr-xr-x   8 cris  staff       272 Jan 25 05:09 .
drwxr-xr-x+ 48 cris  staff      1632 Jan 25 05:04 ..
-rw-r--r--   1 cris  staff      1243 Jan 25 04:54 QuickRandom.class
-rw-r--r--   1 cris  staff       883 Jan 25 05:04 QuickRandom.java
-rw-r--r--   1 cris  staff  16717260 Jan 25 04:55 qr20M.bin.gz
-rw-r--r--   1 cris  staff  20000000 Jan 25 05:07 qr20M.bin2
-rw-r--r--   1 cris  staff  16717402 Jan 25 05:09 qr20M.zip

I would consider an PRNG good if the output file could not be compressed at all. To be honest, I did not think your PRNG would do so well, only 16% on ~20 Megs is pretty impressive for such a simple construction. But I still consider it a fail.

2
  • 2
    Imaging it or not, I have the same idea with the zip years ago when I test my random generators.
    – Aristos
    Jan 24, 2013 at 23:47
  • 1
    Thanks @Alexandre C. and Aristos and aidan. I believe you. Jan 25, 2013 at 5:21
33

The fastest random generator you could implement is this:

enter image description here

XD, jokes apart, besides everything said here, I'd like to contribute citing that testing random sequences "is a hard task" [ 1 ], and there are several test that check certain properties of pseudo-random numbers, you can find a lot of them here: http://www.random.org/analysis/#2005

One simple way to evaluate random generator "quality" is the old Chi Square test.

static double chisquare(int numberCount, int maxRandomNumber) {
    long[] f = new long[maxRandomNumber];
    for (long i = 0; i < numberCount; i++) {
        f[randomint(maxRandomNumber)]++;
    }

    long t = 0;
    for (int i = 0; i < maxRandomNumber; i++) {
        t += f[i] * f[i];
    }
    return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount);
}

Citing [ 1 ]

The idea of the χ² test is to check whether or not the numbers produced are spread out reasonably. If we generate N positive numbers less than r, then we'd expect to get about N / r numbers of each value. But---and this is the essence of the matter---the frequencies of ocurrence of all the values should not be exactly the same: that wouldn't be random!

We simply calculate the sum of the squares of the frecuencies of occurrence of each value, scaled by the expected frequency, and then substract off the size of the sequence. This number, the "χ² statistic," may be expressed mathematically as

chi squared formula

If the χ² statistic is close to r, then the numbers are random; if it is too far away, then they are not. The notions of "close" and "far away" can be more precisely defined: tables exist that tell exactly how relate the statistic to properties of random sequences. For the simple test that we're performing, the statistic should be within 2√r

Using this theory and the following code:

abstract class RandomFunction {
    public abstract int randomint(int range); 
}

public class test {
    static QuickRandom qr = new QuickRandom();

    static double chisquare(int numberCount, int maxRandomNumber, RandomFunction function) {
        long[] f = new long[maxRandomNumber];
        for (long i = 0; i < numberCount; i++) {
            f[function.randomint(maxRandomNumber)]++;
        }

        long t = 0;
        for (int i = 0; i < maxRandomNumber; i++) {
            t += f[i] * f[i];
        }
        return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount);
    }

    public static void main(String[] args) {
        final int ITERATION_COUNT = 1000;
        final int N = 5000000;
        final int R = 100000;

        double total = 0.0;
        RandomFunction qrRandomInt = new RandomFunction() {
            @Override
            public int randomint(int range) {
                return (int) (qr.random() * range);
            }
        }; 
        for (int i = 0; i < ITERATION_COUNT; i++) {
            total += chisquare(N, R, qrRandomInt);
        }
        System.out.printf("Ave Chi2 for QR: %f \n", total / ITERATION_COUNT);        

        total = 0.0;
        RandomFunction mathRandomInt = new RandomFunction() {
            @Override
            public int randomint(int range) {
                return (int) (Math.random() * range);
            }
        };         
        for (int i = 0; i < ITERATION_COUNT; i++) {
            total += chisquare(N, R, mathRandomInt);
        }
        System.out.printf("Ave Chi2 for Math.random: %f \n", total / ITERATION_COUNT);
    }
}

I got the following result:

Ave Chi2 for QR: 108965,078640
Ave Chi2 for Math.random: 99988,629040

Which, for QuickRandom, is far away from r (outside of r ± 2 * sqrt(r))

That been said, QuickRandom could be fast but (as stated in another answers) is not good as a random number generator


[ 1 ] SEDGEWICK ROBERT, Algorithms in C, Addinson Wesley Publishing Company, 1990, pages 516 to 518

4
  • 9
    +1 for xkcd which is an amazing wobsite (oh, and the great answer) :P
    – tckmn
    Jan 29, 2013 at 2:27
  • 1
    Thanks, and yes xkcd racks! XD
    – higuaro
    Jan 29, 2013 at 2:41
  • The theory is fine but the execution is poor: the code is susceptible to integer overflow. In java all int[] are initialized to zero, so no need for this part. Casting to float is pointless when you work w/ doubles. Last: calling the methods names random1 and random2 is quite funny.
    – bestsss
    Jan 29, 2013 at 11:04
  • @bestsss Thanks for the observations! I made a direct translation from the C code and didn't pay much attention to it =(. I made some modifications and updated the answer. I'd appreciate any additional suggestion
    – higuaro
    Jan 29, 2013 at 13:22
14

I put together a quick mock-up of your algorithm in JavaScript to evaluate the results. It generates 100,000 random integers from 0 - 99 and tracks the instance of each integer.

The first thing I notice is that you are more likely to get a low number than a high number. You see this the most when seed1 is high and seed2 is low. In a couple of instances, I got only 3 numbers.

At best, your algorithm needs some refining.

0
8

If the Math.Random() function calls the operating system to get the time of day, then you cannot compare it to your function. Your function is a PRNG, whereas that function is striving for real random numbers. Apples and oranges.

Your PRNG may be fast, but it does not have enough state information to achieve a long period before it repeats (and its logic is not sophisticated enough to even achieve the periods that are possible with that much state information).

Period is the length of the sequence before your PRNG begins to repeat itself. This happens as soon as the PRNG machine makes a state transition to a state which is identical to some past state. From there, it will repeat the transitions which began in that state. Another problem with PRNG's can be a low number of unique sequences, as well as degenerate convergence on a particular sequence which repeats. There can also be undesirable patterns. For instance, suppose that a PRNG looks fairly random when the numbers are printed in decimal, but an inspection of the values in binary shows that bit 4 is simply toggling between 0 and 1 on each call. Oops!

Take a look at the Mersenne Twister and other algorithms. There are ways to strike a balance between the period length and CPU cycles. One basic approach (used in the Mersenne Twister) is to cycle around in the state vector. That is to say, when a number is being generated, it is not based on the entire state, just on a few words from the state array subject to a few bit operations. But at each step, the algorithm also moves around in the array, scrambling the contents a little bit at a time.

5
  • 5
    I mostly agree, except with your first paragraph. The built-in random calls (and /dev/random on Unix-like systems) are also PRNGs. I'd call anything that produces random numbers algorithmically a PRNG, even if the seed is something that is hard to predict. There are a few "true" random number generators that use radioactive decay, atmospheric noise, etc but these often generate relatively few bits/second. Jan 24, 2013 at 13:56
  • On Linux boxes, /dev/random is a source of real randomness obtained from device drivers, and not a PRNG. It blocks when not enough bits are available. The sister device /dev/urandom also does not block, but it is still not exactly a PRNG since it is updated with random bits when they are available.
    – Kaz
    Jan 24, 2013 at 21:36
  • If the Math.Random() function calls the operating system to get the time of day -- this is absolutely untrue. (in any of the java flavors/versions I know of)
    – bestsss
    Jan 25, 2013 at 1:01
  • @bestsss This is from the original question: I remember reading somewhere that Math.random used System.nanoTime(). Your knowledge may be worth adding there or in your answer. I used it conditionally with an if. :)
    – Kaz
    Jan 25, 2013 at 1:25
  • Kaz, both nanoTime()+counter/hash is used for the default seed of java.util.Random of oracle/OpenJDK. That's for the seed only then it's a standard LCG. In effect the OP generator takes 2 random numbers for seed, which is ok - so no difference than java.util.Random. System.currentTimeMillis() was the default seed in JDK1.4-
    – bestsss
    Jan 25, 2013 at 1:34
7

There are many, many pseudo random number generators out there. For example Knuth's ranarray, the Mersenne twister, or look for LFSR generators. Knuth's monumental "Seminumerical algorithms" analizes the area, and proposes some linear congruential generators (simple to implement, fast).

But I'd suggest you just stick to java.util.Random or Math.random, they fast and at least OK for occasional use (i.e., games and such). If you are just paranoid on the distribution (some Monte Carlo program, or a genetic algorithm), check out their implementation (source is available somewhere), and seed them with some truly random number, either from your operating system or from random.org. If this is required for some application where security is critical, you'll have to dig yourself. And as in that case you shouldn't believe what some colored square with missing bits spouts here, I'll shut up now.

7

It is very unlikely that random number generation performance would be an issue for any use-case you came up with unless accessing a single Random instance from multiple threads (because Random is synchronized).

However, if that really is the case and you need lots of random numbers fast, your solution is far too unreliable. Sometimes it gives good results, sometimes it gives horrible results (based on the initial settings).

If you want the same numbers that the Random class gives you, only faster, you could get rid of the synchronization in there:

public class QuickRandom {

    private long seed;

    private static final long MULTIPLIER = 0x5DEECE66DL;
    private static final long ADDEND = 0xBL;
    private static final long MASK = (1L << 48) - 1;

    public QuickRandom() {
        this((8682522807148012L * 181783497276652981L) ^ System.nanoTime());
    }

    public QuickRandom(long seed) {
        this.seed = (seed ^ MULTIPLIER) & MASK;
    }

    public double nextDouble() {
        return (((long)(next(26)) << 27) + next(27)) / (double)(1L << 53);
    }

    private int next(int bits) {
        seed = (seed * MULTIPLIER + ADDEND) & MASK;
        return (int)(seed >>> (48 - bits));
    }

}

I simply took the java.util.Random code and removed the synchronization which results in twice the performance compared to the original on my Oracle HotSpot JVM 7u9. It is still slower than your QuickRandom, but it gives much more consistent results. To be precise, for the same seed values and single threaded applications, it gives the same pseudo-random numbers as the original Random class would.


This code is based on the current java.util.Random in OpenJDK 7u which is licensed under GNU GPL v2.


EDIT 10 months later:

I just discovered that you don't even have to use my code above to get an unsynchronized Random instance. There's one in the JDK, too!

Look at Java 7's ThreadLocalRandom class. The code inside it is almost identical to my code above. The class is simply a local-thread-isolated Random version suitable for generating random numbers quickly. The only downside I can think of is that you can't set its seed manually.

Example usage:

Random random = ThreadLocalRandom.current();
2
  • 2
    @Edit Hmm, I may compare QR, Math.random, and ThreadLocalRandom sometime when I'm not too lazy :) That's interesting, thanks!
    – tckmn
    Oct 8, 2013 at 21:27
  • 1. You can gain some more speed by dropping the mask as the highest 16 bits don't influence the used bits. 2. You can use those bits, save one subtraction and get a better generator (bigger state; the most significant bits of a product are the most nicely distributed, but some evaluation would be needed). 3. The Sun guys simply implemented an archaic RNG by Knuth and added synchronization. :(
    – maaartinus
    Jun 12, 2017 at 16:01
3

'Random' is more than just about getting numbers.... what you have is pseudo-random

If pseudo-random is good enough for your purposes, then sure, it's way faster (and XOR+Bitshift will be faster than what you have)

Rolf

Edit:

OK, after being too hasty in this answer, let me answer the real reason why your code is faster:

From the JavaDoc for Math.Random()

This method is properly synchronized to allow correct use by more than one thread. However, if many threads need to generate pseudorandom numbers at a great rate, it may reduce contention for each thread to have its own pseudorandom-number generator.

This is likely why your code is faster.

5
  • 3
    Pretty much anything that doesn't involve a hardware noise generator or a direct line into the OS's I/O stuff, is going to be pseudo-random. Genuine randomness can't be generated by an algorithm alone; you need noise from somewhere. (Some OSes' RNGs get their input by measuring stuff like how/when you move the mouse, type stuff, etc. Measured on a scale of microseconds to nanoseconds, that can be highly unpredictable.)
    – cHao
    Jan 24, 2013 at 0:47
  • @OliCharlesworth: indeed, as far as I know the only true random values are found using atmospheric noise. Jan 24, 2013 at 0:47
  • @me ... stupid to answer hastily. The Math.random is pseudorandom, and also, it is synchronized.
    – rolfl
    Jan 24, 2013 at 0:52
  • @rolfl: Synchronization could very well explain why Math.random() is slower. It'd either have to synchronize or create a new Random every time, and neither one's very attractive performancewise. If i cared about performance, i'd create my own new Random and just use that. :P
    – cHao
    Jan 24, 2013 at 0:55
  • @JeroenVannevel radioactive decay is random too. Jan 30, 2013 at 3:02
3

java.util.Random is not much different, a basic LCG described by Knuth. However it has main 2 main advantages/differences:

  • thread safe - each update is a CAS which is more expensive than a simple write and needs a branch (even if perfectly predicted single threaded). Depending on the CPU it could be significant difference.
  • undisclosed internal state - this is very important for anything non-trivial. You wish the random numbers not to be predictable.

Below it's the main routine generating 'random' integers in java.util.Random.


  protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
          oldseed = seed.get();
          nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

If you remove the AtomicLong and the undisclosed sate (i.e. using all bits of the long), you'd get more performance than the double multiplication/modulo.

Last note: Math.random should not be used for anything but simple tests, it's prone to contention and if you have even a couple of threads calling it concurrently the performance degrades. One little known historical feature of it is the introduction of CAS in java - to beat an infamous benchmark (first by IBM via intrinsics and then Sun made "CAS from Java")

0

This is the random function I use for my games. It's pretty fast, and has good (enough) distribution.

public class FastRandom {

    public static int randSeed;

      public static final int random()
      {
        // this makes a 'nod' to being potentially called from multiple threads
        int seed = randSeed;

        seed    *= 1103515245;
        seed    += 12345;
        randSeed = seed;
        return seed;
      }

      public static final int random(int range)
      {
        return ((random()>>>15) * range) >>> 17;
      }

      public static final boolean randomBoolean()
      {
         return random() > 0;
      }

       public static final float randomFloat()
       {
         return (random()>>>8) * (1.f/(1<<24));
       }

       public static final double randomDouble() {
           return (random()>>>8) * (1.0/(1<<24));
       }
}
5
  • 1
    This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. Jun 5, 2014 at 13:45
  • I think it was already established that the original algorithm is not good enough? Perhaps an example of what is good enough can lead to inspiration on how to improve it?
    – Terje
    Jun 5, 2014 at 13:54
  • Yes, maybe, but it doesn't answer the question at all and there's no data supporting your algorithm is actually "good enough". Generally, random number algoritms and closely related encryption algorithms are never as good as the ones by the experts that implemented them in a programming language. So, if you could support your claim and elaborate on why it is better than the algorithm in the Question you would at least answer a question asked. Jun 5, 2014 at 14:26
  • Well... Experts that implemented them in a programming language aim for "perfect" distribution, whereas in a game, you never need that. You want speed, and "good enough" distribution. This code offers this. If it's inappropriate here, I'll delete the answer, no problem.
    – Terje
    Jun 6, 2014 at 7:21
  • Concerning multithreading, your usage of the local variable is a no-op, as without volatile, the compiler is free to eliminate (or introduce) local variables at will.
    – maaartinus
    Jun 12, 2017 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.