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

I think you'll find that you really do not want to do this. As the numbers in the database increase, you might spend too much time in the "make sure this number isn't taken" loop.

Personally, I've had luck with hashes as an alternative, but to come up with a better solution, I'd really need to know why you want to do it this way.

Answer 2

My experience was simply using the RNG in PHP. I found that using a certain size of number (I'm using an int, so I have a max of 4G). I ran some tests and found that on average, in 500,000 iterations, I got 120 single duplicates. I never got a triplicate after running the loop a bunch of times. My "solution" was to then just insert and check if it fails, then generate a new ID and go again.

My advice is to do the same and see what your collision rate is &c and see if it's acceptable for your case.

This isn't optimal, so if anyone has suggestions I'm looking too:)

EDIT: I was limited to a 5 digit ID ([a-zA-z0-9]{5,5}), the longer the id (more combination, the few collisions). An md5 of the email would almost never conflict, for instance.

Answer 3

No your algorithm is not scalable. What I've done before is to issue numbers serially (+1 each time) and then pass them through an XOR operation to jumble the bits thus giving me a seemingly random numbers. Of course they aren't really random, but they look so to users eyes.

---

[Edit] Additional information

This algorithm's logic goes like this you use a known sequence to generate unique numbers and then you deterministically manipulate them, so they don't look serial anymore. The general solution is to use some form of encryption, which in my case was an XOR flipflop, because its as fast as it can get, and it fulfills the guarantee that numbers will never collide.

However you can use other forms of encryption, if you want prefer even more random looking numbers, over speed (say you don't need to generate many ids at a time). Now the important point in choosing an encryption algorithm is "the guarantee that numbers will never collide". And a way to prove if an encryption algorithm can fulfill this guarantee is to check if both the original number and the result of the encryption have the same number of bits, and that the the algorithm is reversible (bijection).

[Thanks to Adam Liss & CesarB for exapanding on the solution]

Answer 4

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.

Answer 5

Assuming:

• The randomness is needed for uniqueness, not for security
• Your user_id is 32 bit
• Your limit of 9999999 was just an example

You could do something simple as having the random number as a 64 bit integer, with the upper 32 bits containing the timestamp (at row insert) and the lower 32 bits the user_id. That would be unique even for multiple rows with the same user, provided you use an appropriate resolution on your timestamp depending on how often you add new rows for the same user. Combine with an unique constraint on the random column and catch any such error in your logic and then just retry.

Answer 6

It's easy to design a pseudorandom number generator with a long period of nonrepetition; e.g. this one, which is being used for the same thing that you want it for.

BTW, why not just issue the userid's sequentially?

Answer 7

PHP already has a function for this, uniqid. It generates a standard uuid which is great if you have to access the data from elsewhere. Don't reinvent the wheel.

Answer 8

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 9

Why don't you just use a GUID? Most languages should have a built-in way to do this. It's guaranteed to be unique (with very reasonable bounds).

Answer 10

I like Oddthinking's idea, but instead of choosing the strongest hash function in the world, you could simply:

• Generate the MD5's of the first 10 millions of numbers (expressed as strings, +some salt)
• Check for duplicates offline, i.e. before going in production (I guess there won't be any)
• Store the duplicates in an array somewhere
• When your application starts, load the array
• When you want to insert an ID, choose the next number, compute its MD5, check if it is in the array, and if it isn't use it as the ID in the database. Otherwise, choose next number

MD5's are fast, and checking if a string belongs to an array will avoid you a SELECT.

Answer 11

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

Answer 12

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 13

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

Answer 14

If you really want to get "random" numbers form 0 to 9 999 999, then the solution is to do the "randomization" once, and then store the result to your disk.

It's not hard to get the result you want, but I think of it more like "make a long list with numbers", than "get a random number".

$array = range(0, 9999999);
$numbers = shuffle($array);

You also need a pointer to current position in $numbers (store it in a database); start with 0 and increment it each time you need a new number. (Or you could use array_shift() or array_pop(), if you dont like to use pointers.)

Answer 15

A proper PRNG (Pseudo-Random Number Generator) algorithm will have a cycle time during which it will never be in the same state. If you expose the entire state of the PRNG in the number retrieved from it, you will get a number guaranteed unique for the period of the generator.

A simple PRNG that does this is called the 'Linear Congruential' PRNG which iterates a formula:

X(i) = AX(i-1)|M

Using the right pair of factors you can get a period of 2^30 (approximately 1 billion) from a simple PRNG with a 32 bit accumulator. Note that you will need a 64 bit long long temporary variable to hold the intermediate 'AX' part of the computation. Most if not all C compilers will support this data type. You should also be able to do it with a numeric data type on most SQL dialects.

With the right values of A and M we can get a random number generator with good statistical and geometrical properties. There is a famous paper about this written by Fishman and Moore.

For M = 2^31 - 1 we get can use the values of A below to get a PRNG with a nice long period (2^30 IIRC).

Good Values of A:

742,938,285  
950,706,376  
1,226,874,159  
62,089,911  
1,343,714,438

Note that this type of generator is (by definition) not cryptographically secure. If you know the last number generated from it you can predict what it will do next. Unfortunately I believe that you cannot get cryptographic security and guaranteed non-repeatability at the same time. For a PRNG to be cryptographically secure (e.g. Blum Blum Shub) it cannot expose sufficient state in a generated number to allow the next number in the sequence to be predicted. Therefore the internal state is wider than the generated number and (in order to have good security) the period will be longer than the number of possible values that can be generated. This means that the exposed number will not be unique within the period.

For similar reasons the same is true of long-period generators such as the Mersenne Twister.