Generate Random numbers without using any external functions

Question

This was questions asked in one of the interviews that I recently attended.

As far as I know a random number between two numbers can be generated as follows

public static int rand(int low, int high) {
    return low + (int)(Math.random() * (high - low + 1));
}

But here I am using Math.random() to generate a random number between 0 and 1 and using that to help me generate between low and high. Is there any other way I can directly do without using external functions?

Answer 1

Typical pseudo-random number generators calculate new numbers based on previous ones, so in theory they are completely deterministic. The only randomness is guaranteed by providing a good seed (initialization of the random number generation algorithm). As long as the random numbers aren't very security critical (this would require "real" random numbers), such a recursive random number generator often satisfies the needs.

The recursive generation can be expressed without any "external" functions, once a seed was provided. There are a couple of algorithms solving this problem. A good example is the Linear Congruential Generator.

A pseudo-code implementation might look like the following:

long a = 25214903917;   // These Values for a and c are the actual values found
long c = 11;            // in the implementation of java.util.Random(), see link
long previous = 0;

void rseed(long seed) {
    previous = seed;
}

long rand() {
    long r = a * previous + c;
    // Note: typically, one chooses only a couple of bits of this value, see link
    previous = r;
    return r;
}

You still need to seed this generator with some initial value. This can be done by doing one of the following:

• Using something like the current time (good in most non-security-critical cases like games)
• Using hardware noise (good for security-critical randomness)
• Using a constant number (good for debugging, since you get always the same sequence)
• If you can't use any function and don't want to use a constant seed, and if you are using a language which allows this, you could also use some uninitialized memory. In C and C++ for example, define a new variable, don't assign something to it and use its value to seed the generator. But note that this is far from being a "good seed" and only a hack to fulfill your requirements. Never use this in real code.

Note that there is no algorithm which can generate different values for different runs with the same inputs without access to some external sources like the system environment. Every well-seeded random number generator makes use of some external sources.

Answer 2

Here I am suggesting some sources with comment may be you find helpful:

• System Time : Monotonic in a day poor random. Fast, Easy.
• Mouse Point : Random But not useful on standalone system.
• Raw Socket/ Local Network (Packet 's info-part ) : Good Random Technical and time consuming - Possible to model a attack mode to reduce randomness.
• Some input text with permutation : Fast, Common way and good too (in my opinion).
• Timing of the Interrupt due to keyboard, disk-drive and other events: Common way – error prone if not used carefully.
• Another approach is to feed an analog noise signal : example like temp.

• /proc file data: On Linux system. I feel you should use this.

  /proc/sys/kernel/random: This directory contains various parameters controlling the operation of the file /dev/random.

  The character special files /dev/random and /dev/urandom (present since Linux 1.3.30) provide an interface to the kernel's random number generator.

  try this commads:

  $cat /dev/urandom   
  

  and

  $cat /dev/random
  

  You can write a file read function that read from this file.

  Read (also suggests): Is a rand from /dev/urandom secure for a login key?

`

Answer 3

Does System.currentTimeMillis() count as external? You could always get this and calculate mod by some max value:

int rand = (int)(System.currentTimeMillis()%high)+low;

Answer 4

You can get near randomness (actually chaotic and definitely not uniform*) from the logistic map x = 4x(1-x) starting with a "non-rational" x between 0 and 1.

The "randomness" appears because of the rounding errors at the edge of the accuracy of the floating point representation.

(*)You can undo the skewing once you know it is there.

Answer 5

You may use the address of a variable or combine the address of more variables to make a more complex one...

Answer 6

You could get the current system time, but that would also require a function in most languages.

Answer 7

You can do it without external functions if you are allowed to use some external state (e.g. a long initialised with the current system time). This is enough for you to implement a simple psuedo-random number generator.

In each call to your random function, you would use the state to create a new random value, and update the state, so that subsequent calls get different results.

You can do this with just regular Java arithmetic and/or bitwise operations, so no external functions are required.

Answer 8

public class randomNumberGenerator {

    int generateRandomNumber(int min, int max) {
        return (int) ((System.currentTimeMillis() % max) + min);
    }

    public static void main(String[] args) {
        randomNumberGenerator rn = new randomNumberGenerator();
        int cv = 0;
        int min = 1, max = 4;
        Map<Integer, Integer> hmap = new HashMap<Integer, Integer>();

        int count = min;
        while (count <= max) {
            cv = rn.generateRandomNumber(min, max);
            if ((hmap.get(cv) == null) && cv >= min && cv <= max) {
                System.out.print(cv + ",");
                hmap.put(cv, 1);
                count++;
            }
        }

    }
}

Answer 9

Poisson Random Generator

Lets say we start with an expected value 'v' of the random numbers. Then to say that a sequence of non negative integers satisfies a Poisson Distribution with expected value v means that over subsequences, the mean(average) of the value will appear 'v'. Poisson Distribution is part of statistics and the details can be found on wikipedia. But here the main advantage of using this function are: 1. Only integer values are generated. 2. The mean of those integers will be equal to the value we initially provided.

It is helpful in applications where fractional values don't make sense. Like number of planes arriving on an airport in 1min is 2.5(doesn't make sense) but it implies that in 2 mins 5 plans arrive.

int poissonRandom(double expectedValue) {
  int n = 0; //counter of iteration
  double limit; 
  double x;  //pseudo random number
  limit = exp(-expectedValue);
  x = rand() / INT_MAX; 
  while (x > limit) {
    n++;
    x *= rand() / INT_MAX;
  }
  return n;
}

The line

rand() / INT_MAX

should generate a random number between 0 and 1. So we can use time of the system. Seconds / 60 will serve the purpose. Which function we should use is totally application dependent.