Generate rand number excluding certain numbers

[holty]

Hey

I would like to generate a random number between 1 and 100,000,000 (100 million) that doesn't exist as a 'id' in another table.

Is it possible to write a sql query that can do this check in one go? I could generate a random number and check if that number exists as an 'id' in the other table via a while loop in PHP but as the table gets bigger its possible that the loop could run over and over again.

Is there anything i could add to this query to make it work?

SELECT FLOOR(1 + (RAND() * 100000000))

The only other option I can think of is to have a table with 100 million rows in with a redeemed timestamp and do the following query

SELECT * FROM prizes WHERE redeemed IS NULL ORDER BY RAND() LIMIT 1

Any ideas on how this can be achieved?

thanks for any help:thumbsup:

[Fumigator]

A table with 100 million rows in it is not a good solution. A better one would be to use your server side language to loop through a process that picks a random number, checks that number against your primary key with a simple query, and if it's not being used, break out of the loop and use the number. Depending on how many numbers you need to pick, you very rarely will find a used one so performance will not be an issue.

[holty]

Hi

Thanks for the reply.

Yeah i agree that the 100 million rows isnt a good solution.

The database i am building is for a site giving away 100 million prizes so I am a little worried that x amount of time down the line (lets say i 50 million prizes have been given away) that when i generate a random number and do the check (in a while loop) that it may start taking a while to find a unique number between 1 and 100 million.

Thats why i was wondering whether its possible to do a sql query to generate a random number that isnt being used.

Another solution i was thinking was to have a table with the random numbers in and use the next available value (would prob split table and do a merge in the query to find the next value)

any other ideas? just worried about performance later on!

thanks

[Fumigator]

Yeah no you're right, that will become an issue. But really? 100 million prizes? There are only 60 million people in the UK. That's a lot of prizes. ;) Neverthe less, how will you match up your lucky number to the winner? How are the contestants issued numbers?

[Old Pedant]

There is a *MUCH* simpler way to do this.

Use a REALLY LARGE random number. Also known as a GUID.

Standard GUIDs are just a 128-bit random number. Some databases (well, SQL Server, specifically) even have GUID as a data type and a builtin function to get a new GUID.

With 128 bits, there are 34,028,236,692,093,846,346,337,460,743,177,000,000 different possible numbers. If you allocated 100,000,000 numbers out of that range, the odds of hitting a duplicate are *still* only 1 in 340,282,366,920,938,463,463,374,607,431 !!!

In short, you will NEVER see a duplicate, just by random chance alone.

Many many many computer systems are based on this truism. Many sites generate GUIDs and send them in email knowing that nobody could possibly hit on a match to an allocated GUID by accident.

There's nothing really magic about generating a GUID. The random number generator built into most systems (PHP, MySQL, Java, C++, etc.) is *NOT* good enough to create one in a single pass. That's because these generators create a double precision floating point number from 0 to just less than 1 as their base value. But even if all the bits in those floating point numbers were usably random (and they aren't! read Knuth), that means there are only 51 bits in such a number. The answer is easy: Generate the GUID in "chunks".

Since MySQL doesn't have a 128-bit datatype, anyway, the obvious answer is to use (say) four 32-bit numbers or even eight 16-bit numbers. And just use a standard random number generator to produce each of the four or eight numbers.

For example (using pseudo code, not trying to match any particular language):

unsigned int16 guid[8];
for ( int i = 0; i < 8; ++i )
{
guid[i] = (unsigned int16) Math.floor( 65536 * Math.random() );
}

And now you have eight 16-bit unsigned integers that you could store in eight fields of a MySQL database. And I guarantee you that you'd never have two records with the same four values.

No?

[holty]

Hey guys

Thanks very much for your replies - v helpful so far.

I will explain the process a little more.

I have 100 million prizes to give a way:

90 million 50p off vouchers (1 to 90000000)
5 million £1 off vouchers (90000001 to 95000000)
3 million £2 off vouchers (95000001 to 98000000)
2 million £5 off vouchers (98000001 to 100000000)

A user enters a prize draw form and then i generate a random number between 1 and 100 million (using PHP's rand) to work out what they have won. I then take decrement the count of that prize in another table. This works fine however the probabilities are static so you always have the same % chance of winning a £5 voucher all the time. As prizes are being won i need to change the mechanic so the chances of you winning a certian voucher change with whats available for that voucher and the entire prize pool. Therefore i thought about redeeming the random numbers generated.

Unfortunately the GUID wont work in this case as it doesnt relate to a voucher number. Unless i stored a GUID against each number in a table but this would be slow.

Any other ideas?

[Fumigator]

So you really just need to calculate the odds of the remaining vouchers and randomize based on that. There’s no need to store any of the random numbers at all.

To illustrate—at the beginning the odds of winning voucher A is 90%, B is 5%, C is 3%, and D is 2%. To determine which voucher is won, randomize between 0 and 1, and award A to a random result like this:

A: 0 to .9
B: .9000001 to .95
C: .9500001 to .98
D: .9800001 to 1

As vouchers are awarded, you’ll keep track of how many remain in each pool so the next randomization will use a slightly different odds table. After a few days, you may have 85 million As left, 4 million Bs left, 2.5 million Cs left, and 500,000 Ds left (92 million total). Your odds will then be:

A: 85,000,000 / 92,000,000 = 92.39130%
B: 4,000,000 / 92,000,000 = 4.34783%
C: 85,000,000 / 92,000,000 = 2.71739%
D: 85,000,000 / 92,000,000 = 0.54348%

And your next random number’s ranges will be:

A: 0 to .9239130
B: .9239131 to .9673913
C: .9673914 to .9945652
D: .9945653 to 1