[ACCEPTED]-Algorithm for generating a random number-pseudocode

Accepted answer
Score: 18

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


[Edit] Additional information

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

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

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

Score: 17

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

Score: 6

Want an over-the-top solution?

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

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

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

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

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

Score: 3

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

Score: 2

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 11 having the random number as a 64 bit integer, with 10 the upper 32 bits containing the timestamp 9 (at row insert) and the lower 32 bits the 8 user_id. That would be unique even for multiple 7 rows with the same user, provided you use 6 an appropriate resolution on your timestamp 5 depending on how often you add new rows 4 for the same user. Combine with an unique 3 constraint on the random column and catch 2 any such error in your logic and then just 1 retry.

Score: 1

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

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

Score: 1

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

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

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

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

Score: 1

The problem is that if you are generating 7 random numbers is is very possible to produce 6 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 5 will do what you want it too, it is a bad 4 Idea as this won't scale for long, eventualy 3 your array will get to large and it will 2 take an extremely long time to generate 1 a random that is not already in your db.

Score: 1

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

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

Score: 1

I like Oddthinking's idea, but instead of 4 choosing the strongest hash function in 3 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 2 checking if a string belongs to an array 1 will avoid you a SELECT.

Score: 1

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

Score: 1

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

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

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

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

Score: 1

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

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

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

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

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

For M 21 = 2^31 - 1 we get can use the values of 20 A below to get a PRNG with a nice long period 19 (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 18 this type of generator is (by definition) not 17 cryptographically secure. If you know the 16 last number generated from it you can predict 15 what it will do next. Unfortunately I believe 14 that you cannot get cryptographic security 13 and guaranteed non-repeatability at the 12 same time. For a PRNG to be cryptographically 11 secure (e.g. Blum Blum Shub) it cannot expose sufficient 10 state in a generated number to allow the 9 next number in the sequence to be predicted. Therefore 8 the internal state is wider than the generated 7 number and (in order to have good security) the 6 period will be longer than the number of 5 possible values that can be generated. This 4 means that the exposed number will not be 3 unique within the period.

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

Score: 1

there are a couple ways to go about this 36 one way would be to construct an array with 35 the numbers 0000000 through 9999999 and 34 then pick a random pick of these numbers 33 in this array and swap the picked numbers 32 values with the highest value Max then reduce 31 max by 1 and pick another random member 30 of this array up to the new maximum

each 29 time reducing Max by one

for example (in 28 basic) : (to the right are comments which 27 should be removed in the actual program) Rndfunc 26 is a call to whatever random number generator 25 function you are using

dim array(0 to 9999999) as integer
for x% = 1 to 9999999
array(x%)=x%
next x%
maxPlus = 10000000
max =9999999
pickedrandom =int(Rndfunc*maxPlus)  picks a random indext of the array based on    
                                   how many numbers are left
maxplus = maxplus-1
swap array(pickedrandom) , array(max) swap this array value to the current end of the
                                     array 
max = max -1                   decrement the pointer of the max array value so it 
                              points to the next lowest place..

then keep doing this 24 for each number you wish to pick , but you 23 will need to have the option of using very 22 big arrays

the other method would be as follows 21 :generate a number and store it into an 20 array that can grow dynamically then after 19 that pick a new number and compare it to 18 the value that is halfway from the first 17 to the last element in the array in this 16 case it would be the first number picked if 15 it matches pick another random number, sort 14 the array according to size and if there 13 is not a match then depending on weather 12 it is greater or smaller than the number 11 you compared it with you go up or down in 10 the list half of half the distance, each 9 time that it does not match and is greater 8 or lesser than what you are comparing it 7 to.

each time halving it until you reach 6 a gap size of one then you check once and 5 stop as there is no match, and then the 4 number is added to the list and the list 3 is reshuffled in ascending order, so on 2 and so on until you are done picking random 1 numbers... hope this helps..

Score: 0

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

Score: 0

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

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

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

Score: 0

For Random Generation: ( In PHP )

Code:

It creates random numbers perfectly.

<?PHP
 /*set the bigger range if there is huge demand*/
$n=range(111111,999999);

shuffle($n); //shuffle those

for ($x=0; $x< 1; $x++) //selects unique random number.
{
echo $n[$x].' ';
}
echo "\n"

?>

Result:

First Time:

one

Second Time:

two

Third Time:

three

0

More Related questions