c# Fastest way to randomly index into an array

Question

I have an array of double values "vals", I need to randomly index into this array and get a value. GenRandomNumber() returns a number between 0 and 1 but never 0 or 1. I am using Convert.ToInt32 to basically get everything to the left of my decimal place, but there must be a more efficient way of doing this?

Here's my code:

public double GetRandomVal()
{
   int z = Convert.ToInt32(GenRandomNumber() * (vals.Length));
   return vals[z];
}

Thanks

Update

Thanks to all those who have replied, but I am constrained to use a supplied MersenneTwister random number implementation that has method rand.NextDouble()

Update 2

Thinking about this some more, all I need to do is gen a random number between 0 and array.length-1 and then use that to randomly index into the array. vals length is 2^20 = 1048576 so generating a random int is sufficient. I notice my MersenneTwister has a method:

public int Next(int maxValue)

If I call it like vals[rand.Next(vals.length-1)] that should do it right? I also see the MersenneTwister has a constructor:

public MersenneTwister(int[] init)

Not sure what this is for, can I use this to prepopulate the acceptable random numbers for which I provide an array of 0 to vals.length?

FYI vals is a double array of length 1048576 partitioning the normal distribution curve. I am basically using this mechanism to create Normally distributed numbers as fast as possible, the monte carlo simulation uses billions of Normally distributed random numbers every day so every little bit helps.

Answer 1

Try using a random integer instead:

Random random = new Random();
int randomNumber = random.Next(0, vals.Length);
return vals[randomNumber];

Answer 2

return vals[rng.Next(vals.Length)];

Where rng is

Random rng = new Random();

Answer 3

private static readonly Random _random = new Random();

public double GetRandomVal()
{
    int z = _random.Next(vals.Length);
    return vals[z];
}

Answer 4

Have you considered using the .NET Random class?

Answer 5

I would use Random.Next(Int32), which returns a value less than the input and >= zero. Pass your array length as the input, and you've got a random valid index.

Answer 6

If you are not constraint to use your random function, use the Random class.

public Double GetRandomValue(Double[] values)
{
    return values[new Random().Next(values.Length)];
}

Else I would just use a cast because it gives the right behavior - rounding towards zero instead of the closest integer as Convert.ToInt32() does.

public Double GetRandomValue(Double[] values)
{
    return values[(Int32)(GetNextRandomNumber() * values.Length)];
}

Answer 7

As other people have already noted, System.Random has a Next overload that will do what you're asking already.

As to your comment about Convert.ToInt32 and a more efficient alternative, you can directly cast a double to an int:

double d = 1.5;
int i = (int)d;

Answer 8

I think you have the simplest most direct implementation already identified.

But if you are looking for performance gains in your random indexing algorithm, you may be able to just 'crack' the IEEE 754 encoded double into its exponent and fraction - and use the fraction modulo the array size as a random index.

This technique IS NOT likely to be cryptographically secure - so if that is a consideration - don't do it.

Also, this approach DOES NOT make the code more obvious - I would stick with your original implementation unless maximizing performance is the consideration. As an aside, the slowest part of this processing is most likely the Mersenne Twister generation of random numbers.

Here's the code:

[StructLayout(LayoutKind.Explicit)] // used create a union of Long and Double
public struct IEEE754
{
    private const ulong SIGN_BITS     = 0x8000000000000000;
    private const ulong EXPONENT_BITS = 0x7FF0000000000000;
    private const ulong FRACTION_BITS = 0x000FFFFFFFFFFFFF;

    private const int SIGN_OFFSET     = 63;
    private const int EXPONENT_OFFSET = 52;

    // [FieldOffset] attribute is .NET's way of defining how to explicitly
    // layout the fields of a structure - we're using it to overlay the
    // double and long into a single bit-space ... effectively a C# 'union'
    [FieldOffset( 0 )] private double DoubleValue;
    [FieldOffset( 0 )] private ulong LongValue;

    public IEEE754(double val)
    {
        DoubleValue = val;
    }
    // properties that retrieve the various pieces of an IEEE754 double
    public long Fraction { get { return (long)(LongValue & FRACTION_BITS); } }
    public long Exponent { get { return (long)((LongValue & EXPONENT_BITS) >> EXPONENT_OFFSET); } }
    public long Sign     { get { return (long)((LongValue & SIGN_BITS) >> SIGN_OFFSET); } }

    public void Set( double val ) { DoubleValue = val; }
}

public static void TestFunction()
{
    var array = Enumerable.Range( 1, 10000 ).ToArray();   // test array...

    // however you access your random generator would go here...
    var rand = new YourRandomNumberGenerator();

    // crack the double using the special union structure we created...
    var dul = new IEEE754( rand.GenRandomNumber() );

    // use the factional value modulo the array length as a random index...
    var randomValue = array[dul.Fraction % array.Length];
}