Algorithm for generating a random number

Question

I'm looking to generate a random number and issue it to a table in a database for a particular user_id. The catch is, the same number can't be used twice. There's a million ways to do this, but I'm hoping someone very keen on algorithms has a clever way of solving the problem in an elegant solution in that the following criteria is met:

1) The least amount of queries to the database are made. 2) The least amount of crawling through a data structure in memory is made.

Essentially the idea is to do the following

1) Create a random number from 0 to 9999999
2) Check the database to see if the number exists
OR
2) Query the database for all numbers
3) See if the returned result matches whatever came from the db
4) If it matches, repeat step 1, if not, problem is solved.

Thanks.

Answer 1

Want an over-the-top solution?

I assume randomness is not intended to be encryption-quality, but just enough to discourage guessing the longevity of a user, by user_id.

During development, generate a list of all 10 million numbers in string form.

Optionally, perform some simple transformation, like adding a constant string to the middle. (This is just in case the result is too predictable.)

Pass them into a tool that generates Perfect Hash functions, such as gperf.

The resulting code can be used to quickly encode the user's id at runtime into a unique hash value that is guaranteed not to clash with any other hash values.

Answer 2

I've actually previously written an article about this. It takes the same approach as Robert Gould's answer, but additionally shows how to shorten a block cipher to a suitable length using xor folding, and then how to generate the permutations over a range that isn't a power of 2, while still preserving the uniqueness property.

Answer 3

I probably did not catch your point, but what about auto_increments ?

Answer 4

If you want to ensure that the random-numbers aren't repeating, you need a non-repeating random number-generator (as described here).

The basic idea is that the following formula seed * seed & p will produced non-repeating random-numbers for any input x such that 2x < p and p - x * x % p produces all other random-number aswell non-repeating, but only if p = 3 mod 4. So basically all you need is a single primnumber as close to 9999999 as possible. This way the effort can be reduced to a single read field, but with the downside that either too big IDs are generated or too few IDs will be generated.

This algorithm doesn't permute very well, so i'd recommend combining it with either XOR or addition or some other approach to change the exact value without destroying the 1-to-1-relation between seeds and their generated value.

Answer 5

Try the statement in mysql SELECT CAST(RAND() * 1000000 AS INT)

Answer 6

The problem is that if you are generating random numbers is is very possible to produce duplicates infinatly.

however:

<?php
//Lets assume we already have a connection to the db
$sql = "SELECT randField FROM tableName";
$result = mysql_query($sql);
$array = array();
while($row = mysql_fetch_assoc($result))
 {
   $array[] = $row['randField'];
 }
while(True)
 {
   $rand = rand(0, 999999);
   if(!in_array($rand))
     {
       //This number is not in the db so use it!
       break;
     }
 }
?>

While this will do what you want it too, it is a bad Idea as this won't scale for long, eventualy your array will get to large and it will take an extremely long time to generate a random that is not already in your db.