Java
Beware, this is a trick question .....
Most people in Java will use math.random() to help to generate this sequence, but they will get confused because they will only get positive results! random()
returns a decimal value from 0 to 1 (excluding 1 itself). So, you have to play some tricks to make sure you get a good distribution of random values from over the entire integer range (positive and negative).
Also, you cannot simply multiply Math.random()
and Integer.MAX_VALUE
because you this will never include Integer.MAX_VALUE
itself as part of the result! Also, it would be logical to do math.rand() * (Integer.MAX_VALUE + 1)
so that you get a full distribution, but, of course, this does not work because Integer.MAX_VALUE + 1
will overflow, and become Integer.MIN_VALUE
! So, unfortunately, the best solution is to resort to bit-wise manipulation of the data...
So, here is a complete sequence for generating 'n' random values in the range Integer.MIN_VALUE
to Integer.MAX_VALUE
(Inclusive of both extremes (which is the hard part)!!!!):
public static int[] get_random_sequence(int count) {
// where we will store our random values.
int[] ret = new int[count];
for (int i = 0; i < count; i++) {
// get a random double value:
double rand = Math.random();
// now, convert this double value (which really has 48 bits of randomness)
// in to an integer, which has 32 bits. Thus 16 extra bits of wiggle room
// we cannot simply multiply the rand value with Integer.MAX_VALUE
// because we will never actually get Integer.MAX_VALUE
// (since the rand will never exactly == 1.0)
// what we do is treat the 32-bits of the integer in a clever bit-shifting
// algorithm that ensures we make it work:
// We use two special Mersenne Prime values (2^19 - 1) and (2^13 - 1)
// http://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes
// these are very convenient because 13 + 19 is 32, which is the
// number of bits of randomness we need (32-bit integer).
// Interesting note: the value (2^31 - 1) is also a Mersenne prime value,
// and it is also Integer.MAX_VALUE. Also, it is a double marsenne prime
// since 31 is also a marsenne prime... (2^(2^5 - 1) - 1). Math is Cool!!!
// 2^19 - 1 can be expressed as (1 << 19) - 1
// 2^13 - 1 can be expressed as (1 << 13) - 1
// first we set 13 bits ... multiply a 13-bit prime by the random number.
ret[i] = (int)(rand * (1 << 13) - 1);
// now shift those 13 random bits 19 bits left:
ret[i] <<= 19;
// now add in the 19 random bits:
ret[i] ^= (int)(rand * (1 << 19) - 1);
}
return ret;
}
This produces output like:
[-368095066, -1128405482, 1537924507, -1864071334, -130039258, 2020328364, -2028717867, 1796954379, 276857934, -1378521391]
Of course, the above is a complete BS answer. It does not produce a good description, and it 'hides' a severe bug ( ^=
should be |=
). it also hides a less-severe bug (the order-pf-precedence means we do not actually multiply by a prime value at all!) Using fancy words, prime numbers, and lots of comments is no reason to trust the code.... Of course, if you want to do the above, you should just use java.util.Random.nextInt()