How to generate a random number from scratch

Question

How can a random number be generated from scratch, i.e without using any built-in features of the language / outside API that will help with the randomization process?

For example php has a rand() function and a seed function, and I'm sure java also has some similar stuff.

You can use built-in functions to get the current time etc, but the actual process of generating a random number has to be done by your code.

Any ideas?

Answer 1

Use system clock. Then hash it.

Answer 2

Take some initial seed number and multiply it with a large and well picked number to produce new pseudo-random numbers. Actually, this is what many languages do.

int seed = 94664704;
public int rand() {
    seed = 23*seed % 10e8 + 1;
    return seed % 10e5;
}

Taken from my highschool formula collection, Formeln und Tafeln, page 8.

Answer 3

Java actually details how they pick the next random number in the javadoc for java.util.Random:

The general contract of next is that it returns an int value and if the argument bits is between 1 and 32 (inclusive), then that many low-order bits of the returned value will be (approximately) independently chosen bit values, each of which is (approximately) equally likely to be 0 or 1. The method next is implemented by class Random as follows:

 synchronized protected int next(int bits) {
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int)(seed >>> (48 - bits));
 }

This is a linear congruential pseudorandom number generator, as defined by D. H. Lehmer and described by Donald E. Knuth in The Art of Computer Programming, Volume 2: Seminumerical Algorithms, section 3.2.1.

Answer 4

Implement a linear congruential generator -- simple, and reasonably high quality for well chosen parameters.

Answer 5

Wikipedia's discussion of the linear congruential generator is decent and accessible, if you're hell-bent on doing this yourself:

http://en.wikipedia.org/wiki/Random%5Fnumber%5Fgeneration#Computational%5Fmethods

Though I can't imagine why you'd want to do this yourself; most decent languages and/or operating environments already provide tested sources of pseudo-randomness.

Answer 6

If you need a good quality random number, then you should look in to implementing the Mersenne twister random number generator in your language of choice. There are a lot of ready implementations floating around the net, so you can just pick one that you'd like to use.

If you can deal with something cruddy, just use a linear congruential generator.

Answer 7

Your question is a bit unclear. Are you trying to solve a concrete problem? Are you just asking out of curiosity?

If I understand you correctly, you want to re-implement the random-number generation that most languages/APIs offer. To do this, you'll have to implement a pseudo-random generator. This is a rather complex mathematical topic (if you want to do it correctly), so be prepared to do a lot of reading and thinking. A good starting point would be the Wikipedia article on Pseudorandom number generators

Answer 8

most languages have a PRNG function like Math.random() in java. The PRNG is usually seeded with a value like the current time or something you choose.

For something more secure, you need a greater source of entropy than the current time. A class like java.security.SecureRandom implements that.

One high quality PRNG is the Mersenne Twister algorithm.

There are much simpler PRNG's for more basic applications, like this one from the C documentation:

int rand(void)
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/(2 * (RAND_MAX +1L)) % (RAND_MAX+1L));
}

void srand(unsigned int seed)
{
  next = seed;
}

You can test the quality of your PRNG using this tester: http://www.phy.duke.edu/~rgb/General/dieharder.php

Answer 9

Computers being discrete mathematical device are incapable of generating pure random number without external intervention. Below code generates fairly usable random number:

public static synchronized String getAutoGenId(){
    StringBuilder autogenID=new StringBuilder();
    try 
    {   

        Random rand = new Random();
        autogenID.append(Long.toString(System.nanoTime()));
        autogenID.append(Integer.toString(rand.nextInt(99)));
        if(autogenID.toString().length()<15)
        {
            autogenID.append(Integer.toString(rand.nextInt(9)));
        }

    } catch (Exception e) {
        //Do something
    } 
    return autogenID.toString();
}

Or else you may also find it interesting to study the implementation of UUID

Answer 10

If you want truly random, you must build a dice rolling robot and then program it accordingly. Or buy the one this dude made:

DiceOMatic