Fast real valued random generator in java

问题:

java.util.Random.nextDouble() is slow for me and I need something really fast.

I did some google search and I've found only integers based fast random generators. Is here anything for real numbers from interval <0, 1) ?

回答1:

If you need something fast and have access to Java8, I can recommend the java.utils SplitableRandom. It is faster (~twice as fast) and has better statistical distribution.

If you need a even faster or better algorithm I can recommend one of these specialized XorShift variants:

• Xoroshiro128+ (faster & better)
• XorShift1024* (similar speed, even longer period)

Information on these algorithms and their quality can be found in this big PRNG comparison.

I made an independent Performance comparison you can find the detailed results and the code here: github.com/tobijdc/PRNG-Performance

TLDR

Never use java.util.Random, use java.util.SplittableRandom. If you need faster or better PRNG use a XorShift variant.

回答2:

You could modify an integer based RNG to output doubles in the interval [0,1) in the following way:

double randDouble = randInt()/(RAND_INT_MAX + 1.0)

However, if randInt() generates a 32-bit integer this won't fill all the bits of the double because double has 53 mantissa bits. You could obviously generate two random integers to fill all mantissa bits. Or you could take a look at the source code of the Ramdom.nextDouble() implementation. It almost surely uses an integer RNG and simply converts the output to a double.

As for performance, the best-performing random number generators are linear congruential generators. Of these, I recommend using the Numerical Recipes generator. You can see more information about LCGs from Wikipedia: http://en.wikipedia.org/wiki/Linear_congruential_generator

However, if you want good randomness and performance is not that important, I think Mersenne Twister is the best choice. It also has a Wikipedia page: http://en.wikipedia.org/wiki/Mersenne_Twister

There is a recent random number generator called PCG, explained in http://www.pcg-random.org/. This is essentially a post-processing step for LCG that improves the randomness of the LCG output. Note that PCG is slower than LCG because it is simply a post-processing step for LCG. Thus, if performance is very important and randomness quality not that important, you want to use LCG instead of PCG.

Note that none of the generators I mentioned are cryptographically secure. If you need use the values for cryptographical applications, you should be using a cryptographically secure algorithm. However, I don't really believe that doubles would be used for cryptography.

回答3:

Note that all these solutions miss a fundamental fact (that I wasn't aware of up to a few weeks ago): passing from 64 bits to a double using a multiplication is a major loss of time. The implementation of xorshift128+ and xorshift1024+ in the DSI utilities (http://dsiutils.di.unimi.it/) use direct bit manipulation and the results are impressive.

See the benchmarks for nextDouble() at

http://dsiutils.di.unimi.it/docs/it/unimi/dsi/util/package-summary.html#package.description

and the quality reported at

http://prng.di.unimi.it/

回答4:

You could create an array of random doubles when you init your program and then just repeat it. This is much faster but the random values reapeat themselfs.

回答5:

Imho you should just accept juhist's answer - here's why.

nextDouble is slow because it makes two calls to next() - it's written right there in the documentation.

So your best options are:

• use a fast 64 bit generator, convert that to double (MT, PCG, xorshift*, ISAAC64, ...)
• generate doubles directly

Here's an overly long benchmark with java's Random, an LCG (as bad as java.util.Random), and Marsaglia's universal generator (the version generating doubles).

import java.util.*;

public class d01 {
    private static long sec(double x)
    {
        return (long) (x * (1000L*1000*1000));
    }
    // ns/op: nanoseconds to generate a double
    // loop until it takes a second.
    public static double ns_op(Random r)
    {
        long nanos = -1;
        int n;
        for(n = 1; n < 0x12345678; n *= 2) {
            long t0 = System.nanoTime();
            for(int i = 0; i < n; i++)
                r.nextDouble();
            nanos = System.nanoTime() - t0;
            if(nanos >= sec(1))
                break;
            if(nanos < sec(0.1))
                n *= 4;
        }
        return nanos / (double)n;
    }
    public static void bench(Random r)
    {
        System.out.println(ns_op(r) + " " + r.toString());
    }

    public static void main(String[] args)
    {
        for(int i = 0; i < 3; i++) {
            bench(new Random());
            bench(new LCG64(new Random().nextLong()));
            bench(new UNI_double(new Random().nextLong()));
        }
    }
}

// straight from wikipedia
class LCG64 extends java.util.Random {
    private long x;
    public LCG64(long seed) {
        this.x = seed;
    }
    @Override
    public long nextLong() {
        x = x * 6364136223846793005L + 1442695040888963407L;
        return x;
    }
    @Override
    public double nextDouble(){
        return (nextLong() >>> 11) * (1.0/9007199254740992.0);
    }
    @Override
    protected int next(int nbits)
    {
        throw new RuntimeException("TODO");
    }
}


class UNI_double extends java.util.Random {
    // Marsaglia's UNIversal random generator extended to double precision
    // G. Marsaglia, W.W. Tsang / Statistics & Probability Letters 66 (2004) 183 – 187
    private final double[] U = new double[98];
    static final double r=9007199254740881.0/9007199254740992.;
    static final double d=362436069876.0/9007199254740992.0;
    private double c=0.;
    private int i=97,j=33;
    @Override
    public double nextDouble(){
            double x;

            x=U[i]- U[j];
            if(x<0.0)
                x=x+1.0;
            U[i]=x;

            if(--i==0) i=97;
            if(--j==0) j=97;

            c=c-d;
            if(c<0.0)
                c=c+r;

            x=x-c;
            if(x<0.)
                return x+1.;
            return x;
        }
    //A two-seed function for filling the static array U[98] one bit at a time
    private
        void fillU(int seed1, int seed2){
            double s,t;
            int x,y,i,j;
            x=seed1;
            y=seed2;

            for (i=1; i<98; i++){
                s= 0.0;
                t=0.5;

                for (j=1; j<54; j++){
                    x=(6969*x) % 65543;
                    // typo in the paper:
                    //y=(8888*x) % 65579;
                    //used forthe demo in the last page of the paper.
                    y=(8888*y) % 65579;
                    if(((x^y)& 32)>0)
                        s=s+t;
                    t=.5*t;
                }
                if(x == 0)
                    throw new IllegalArgumentException("x");
                if(y == 0)
                    throw new IllegalArgumentException("y");
                U[i]=s;
            }
        }

    // Marsaglia's test code is useless because of a typo in fillU():
    //  x=(6969*x)%65543;
    //  y=(8888*x)% 65579;

    public UNI_double(long seed)
    {
        Random r = new Random(seed);
        for(;;) {
            try {
                fillU(r.nextInt(), r.nextInt());
                break;
            } catch(Exception e) {
                // loop again
            }
        }
    }

    @Override
    protected int next(int nbits)
    {
        throw new RuntimeException("TODO");
    }
}

回答6:

Have you actually done benchmarking or profiling to show that nextDouble is the bottleneck? Have you looked at alternatives such as MersenneTwister or L'Ecuyer's streams library? I'd suggest trying those with benchmarking, but there's no such thing as a free lunch. Improvements in speed will probably come at a cost of quality, and vice-versa.