Algorithm for generating a random number

Viewed 87 times

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.

Answers

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]

Wednesday, December 14, 2022

bparsa-2215e5399ed2

here's another, statistically sound good way: http://www.thebroth.com/blog/118/bayesian-rating

Tuesday, December 13, 2022

milligramme

If you use:

  SELECT * 
    FROM friends 
   WHERE member_id = '".$_SESSION['userid']."' 
ORDER BY rand() 
   LIMIT 6

If the person only has 3 friends, the query will only show those three - it doesn't mean that the query will always return six rows.

Monday, November 21, 2022

binay_thapa_magar

This trick works only if you need one single random numbers, or the interval between the random numbers includes pauses for human input. In all other cases, the numbers will not be random at all.

If you need many random numbers, then there are different pseudo-random number algorithms available.

Another note is that there is more easy way to get the number in the needed interval:

    mov  ax, dx
    xor  dx, dx
    mov  cx, 10    
    div  cx       ; here dx contains the remainder of the division - from 0 to 9

    add  dl, '0'  ; to ascii from '0' to '9'

You can use this method for every random number generator of course.

Friday, November 4, 2022

functionvoid

If the middle tier cannot check what "order numbers" already exists in the database, the best it can do will be the equivalent of generating a random number. However, if you generate a random number that's constrained to be less than 1 billion, you should start worrying about accidental collisions at around sqrt(1 billion), i.e., after a few tens of thousand entries generated this way, the risk of collisions is material. What if the order number is sequential but in a disguised way, i.e. the next multiple of some large prime number modulo 1 billion -- would that meet your requirements?

Saturday, August 6, 2022

e2a

Only authorized users can answer the search term. Please sign in first, or register a free account.

Not the answer you're looking for? Browse other questions tagged :

php

mysql

algorithm

random

pseudocode

Algorithm for generating a random number

Answers

php,mysql,algorithm,random,pseudocode