A way to generate guaranteed unique random numbers

Coding Critique is the place to post source code for peer review by other members of DevNetwork. Any kind of code can be posted. Code posted does not have to be limited to PHP. All members are invited to contribute constructive criticism with the goal of improving the code. Posted code should include some background information about it and what areas you specifically would like help with.

Popular code excerpts may be moved to "Code Snippets" by the moderators.

Moderator: General Moderators

alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Re: A way to generate guaranteed unique random numbers

Post by alex.barylski »

Oh...I thought you were older, with a cart load of experience behind you....but that was great, indeed...
Age is irrelevant in software enigneering, I could have done the same thing at 13. :P

No computer generated number is absolutely random unless you can introduce real random entropy.

Using a low-level PHP function might be able to use a server's MAC address but in PHP is you really wanted random, you could pull the data from various active/busy web sites and calculate a hash based on that data.

The idea being, that people who submit messages to a website are more random then a super speedy ticking clock.
User avatar
aditya2071990
Forum Contributor
Posts: 106
Joined: Thu May 22, 2008 11:30 am
Location: Hyderabad, India
Contact:

Re: A way to generate guaranteed unique random numbers

Post by aditya2071990 »

Hmm...didn't think in that direction...but hashes may be repeated, right?
User avatar
onion2k
Jedi Mod
Posts: 5263
Joined: Tue Dec 21, 2004 5:03 pm
Location: usrlab.com

Re: A way to generate guaranteed unique random numbers

Post by onion2k »

aditya2071990 wrote:Hmm...didn't think in that direction...but hashes may be repeated, right?
Yes, but the likelihood of it happening is very, very small. Unless you're generating thousands of hashes a second it's probably not worth worrying about it.
User avatar
aditya2071990
Forum Contributor
Posts: 106
Joined: Thu May 22, 2008 11:30 am
Location: Hyderabad, India
Contact:

Re: A way to generate guaranteed unique random numbers

Post by aditya2071990 »

Oh my, I was actually generating hashes in the first place, then I came to this microtime thingy. So I guess its back to square one...
jack_indigo
Forum Contributor
Posts: 186
Joined: Sun Jun 08, 2008 11:25 pm

Re: A way to generate guaranteed unique random numbers

Post by jack_indigo »

On a variation of this topic, I was trying to think of a way to make a kind of GUID that uses the least number of alphanumeric character positions. I could then use that as a key in a database table instead of using serialized IDs. Serialized IDs make me nervous because if you ever carry a table over from one server to another and don't do it right, you end up with mismatches where a table uses new IDs, and thus your integrity is blown. So, if I use a short GUID and set a unique constraint on the column, I can prevent that problem from happening. Here's my routine:

The only thing I'm not certain about is what happens when 2038 comes around. Will the microtime() routine start generating negative numbers?

Code: Select all

public function GenerateKey() {
 
  $sTime = microtime(true);
  $asTime = explode('.',$sTime);
  $sSeconds = $asTime[0];
  $sMicro = $asTime[1];
  if (empty($sMicro)) {
    $sMicro = '00';
  } else if (strlen($sMicro) < 2) {
    $sMicro .= '0';
  }
  $sTime = $sMicro . $sSeconds;
 
  $sFirst = strtoupper(base_convert(substr($sTime, 0, 7), 10, 23));
 
  $asRange = range('A','M');
  $sFirst = $asRange[(mt_rand(1,13)-1)] . $sFirst;
 
  $sLast = strtoupper(base_convert(substr($sTime, 7), 10, 23));
 
  if (strlen($sFirst) < 7) {
    $sFirst = str_pad($sFirst, 7, '81');
  }
 
  if (strlen($sLast) < 4) {
    $sLast = str_pad($sLast, 4, '92');
  }
 
  $sTime = substr($sFirst, 0, 7) . substr($sLast, 0, 4);
 
  $sTime = str_replace('I','P',$sTime);
  $sTime = str_replace('J','R',$sTime);
  $sTime = str_replace('1','T',$sTime);
  $sTime = str_replace('0','Z',$sTime);
  $sTime = str_replace('A','V',$sTime);
  $sTime = str_replace('E','X',$sTime);
 
  return $sTime;
 
}
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Re: A way to generate guaranteed unique random numbers

Post by pickle »

aditya2071990 wrote:Theory also says that no two computers can have the same IP address at the same microsecond
Sorry, but that's just plain wrong.

2 computers behind 1 router can appear as 1 device to a web server. The odds of them being served in the same microsecond is remote at best, but that's still a far cry from "guaranteed unique".
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
jack_indigo
Forum Contributor
Posts: 186
Joined: Sun Jun 08, 2008 11:25 pm

Re: A way to generate guaranteed unique random numbers

Post by jack_indigo »

pickle wrote:
aditya2071990 wrote:Theory also says that no two computers can have the same IP address at the same microsecond
Sorry, but that's just plain wrong.

2 computers behind 1 router can appear as 1 device to a web server. The odds of them being served in the same microsecond is remote at best, but that's still a far cry from "guaranteed unique".
Yeah, this is true. Perhaps it would be good to generate a unique number based on these two values:

$_SERVER['REMOTE_ADDR']
$_SERVER['HTTP_USER_AGENT']

+ microtime().

I mean, if you take microtime(), then tack on the IP2Int version of REMOTE_ADDR (there are several well-documented IP2Int APIs on the web), and then tack on a crc32() of HTTP_USER_AGENT, you'd have one long number. Then, use base conversion to convert it to another base in order to condense this down.

Some problems I have with base conversion, though, are:

1. Can sometimes spell out a cuss word.

2. Can make numbers that are hard to read aloud to someone else

So, pickle, in my previous post before yours, I present how I implement base conversion to get around those two problems.
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Re: A way to generate guaranteed unique random numbers

Post by pickle »

No matter how much you massage random numbers, there is still no 100% guarantee that you won't get duplicates. You can convert, randomly swap, & otherwise mess with a string/number until you're blue in the face. Unless you are verifying that the number you generate was not handed out before - by storing all numbers in a database & cross-checking, for example - you can't guarantee the number is unique. Of course, you can move the likelihood into the "astronomically remote", but "astronomically remote" != "impossible"
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
aditya2071990
Forum Contributor
Posts: 106
Joined: Thu May 22, 2008 11:30 am
Location: Hyderabad, India
Contact:

Re: A way to generate guaranteed unique random numbers

Post by aditya2071990 »

pickle wrote:
aditya2071990 wrote:Theory also says that no two computers can have the same IP address at the same microsecond
Sorry, but that's just plain wrong.

2 computers behind 1 router can appear as 1 device to a web server. The odds of them being served in the same microsecond is remote at best, but that's still a far cry from "guaranteed unique".
Whoops, sorry for the elephant sized blooper :D
jack_indigo
Forum Contributor
Posts: 186
Joined: Sun Jun 08, 2008 11:25 pm

Re: A way to generate guaranteed unique random numbers

Post by jack_indigo »

In PostgreSQL, they have a thing called a sequence in order to create a unique primary key for any requestor that calls the nextval('MySequence') of it. It's more preferable than a serial column because it supports up to 64 bit numbers -- a number up to 2 billion. A serial stores a 32 bit number. It's also more preferable than just using a table because it consumes less space and runs faster. That's why they were invented. For example:

Code: Select all

CREATE SEQUENCE uniq_seq
  INCREMENT 1
  MINVALUE 1234567
  START 1234567
  CACHE 1;
and then call this with select nextval('uniq_seq');

Other tips:

* You can also take the returned number and run it through a base_convert() call to condense it's size.

* To make the numbers seem somewhat more unique to the end user's eye, you can prefix or suffix a random 1, 2, or 3 letter code that you can throw away (as being meaningless) when doing any processing.

* If you lower your base_conversion from 36 (which would have been 0-9,A-Z) to 22 (0-9,A-L), this gives you extra letters (M-Z) which you can use to replace certain undesirable letters or numbers. And what are undesirable numbers or letters? Well, ones that are often easily printed out and confused with other letters or numbers (depending on font), or which may accidentally help spell a cuss word (like vowels) or spell an undesirable word (like a sequence of K's).

I'm not certain if such a thing exists for MySQL or SQLite, though, so you might want to check on that.
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Re: A way to generate guaranteed unique random numbers

Post by John Cartwright »

aditya2071990 wrote: Hmmm, but that's why we are adding the microseconds and user IP addresses together. Theory also says that no two computers can have the same IP address at the same microsecond...;)

But I am open to know more. I would definitely like to add yet another layer of randomness to what is already present, so any suggestions in that direction are most welcome...
That is incorrect. Any computers behind a router with share a single (external) IP address, proxies, etc.

EDIT| Sorry this was already brought up.
Post Reply