11

How are random numbers generated.? How do languages such as java etc generate random numbers, especially how it is done for GUIDs.? i found that algorithms like Pseudorandomnumber generator uses initial values.

But i need to create a random number program, in which a number once occurred should never repeats even if the system is restarted etc. I thought that i need to store the values anywhere so that i can check if the number repeats or not, but it will be too complex when the list goes beyond limits.?

Binary Worrier
  • 50,774
  • 20
  • 136
  • 184
SyncMaster
  • 9,754
  • 34
  • 94
  • 137
  • 2
    Do you want a GUID generator? If so, please provide the language and OS you're working in. We'll tell you how to use the GUID library for your platform. – S.Lott May 26 '09 at 10:34
  • Duplicate (almost) of http://stackoverflow.com/questions/506118/how-to-manually-generate-random-numbers – Binary Worrier May 26 '09 at 10:35
  • @S.Lott: ya. I'm using VS2005 in Windows xp and C#. @Binary Worrier: sorry as i didnt find that stackoverflow question when posting this. – SyncMaster May 26 '09 at 10:41
  • @pragadheesh: I said (alomst) because I'm not sure if the question corresponds to your or that the answers there answer your question. – Binary Worrier May 26 '09 at 10:50
  • fwiw, I think this is a different (and excellent) question despite the fact the answers might overlap – annakata May 26 '09 at 10:56
  • A question about random numbers and no-one's linked to xkcd yet? My god, what is the world coming to!? – Ed James May 26 '09 at 11:09

6 Answers6

18

First: If the number is guaranteed to never repeat, it's not very random.

Second: There are lots of PRNG algorithms.

UPDATE:

Third: There's an IETF RFC for UUIDs (what MS calls GUIDs), but you should recognize that (U|G)UIDs are not cryptographically secure, if that is a concern for you.

UPDATE 2:

If you want to actually use something like this in production code (not just for your own edification) please use a pre-existing library. This is the sort of code that is almost guaranteed to have subtle bugs in it if you've never done it before (or even if you have).

UPDATE 3:

Here's the docs for .NET's GUID

Community
  • 1
  • 1
Hank Gay
  • 70,339
  • 36
  • 160
  • 222
  • +1: I do believe that's all the bases covered, if this doesn't answer the question as asked, nothing will :) – Binary Worrier May 26 '09 at 10:52
  • Interestingly, since the LCG (http://en.wikipedia.org/wiki/Linear_congruential_generator) is only seeded by the previous value, it will create a non repeating sequence. That is, there will be no repeats until the entire sequence repeats. – Sionide21 May 26 '09 at 10:58
  • 1
    A RNG can certainly be random if it doesn't repeat itself. This merely requires it to have an equal chance of picking any number not picked so far. – MSalters May 26 '09 at 11:27
  • 1
    Enforcing that constraint reduces your entropy with every number generated and will make it progressively easier to predict the next number in the sequence, at which point it is no longer random. – Hank Gay May 26 '09 at 11:31
3

There are a lot of ways you could generate random numbers. It's usually done with a system/library call which uses a pseudo-number generator with a seed as you've already described.

But, there are other ways of getting random numbers which involve specialized hardware to get TRUE random numbers. I know of some poker sites that use this kind of hardware. It's very interesting to read how they do it.

Pablo Santa Cruz
  • 176,835
  • 32
  • 241
  • 292
  • Presumably this is based on watching decaying particles? Damn, there goes my next half hour. – annakata May 26 '09 at 10:59
  • 1
    It can be done using some diode kept near its knee (is that the term in English?) where it's very unstable and can randomly switch from passing current to not passing current. – Nathan Fellman May 26 '09 at 11:28
0

Most random number generators have a way to "randomly" reïnitialize the seed value. (Sometimes called randomize).

If that's not possible, you can also use the system clock to initialize the seed.

Toon Krijthe
  • 52,876
  • 38
  • 145
  • 202
  • 1
    system clock is a bad idea. if you're running a poker site i can use trial and error and very easily work out your seed based on the past few cards and guessing the time difference between our clocks. – SillyMonkey May 26 '09 at 10:51
0

You could use this code sample: http://xkcd.com/221/ Or, you can use this book: http://www.amazon.com/Million-Random-Digits-Normal-Deviates/dp/0833030477

But seriously, don't implement it yourself, use an existing library. You can't be the first person to do this.

thijs
  • 3,445
  • 1
  • 27
  • 46
0

Specifically regarding Java:

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
0

I understand that you are seeking a way to generate random number using C#. If yes, RNGCryptoServiceProvider is what you are looking for.

[EDIT]

If you generate a fairly long number of bytes using RNGCryptoServiceProvider, it is likely to be unique but there is no gurantee. In theory, true random numbers doesnt mean to be unique. You roll a dice 2 times and you may get head both the times but they are still random. TRUE RANDOM!

I guess to apply the check of being unique, you just have to roll out your own mechanism of keeping history of previously generated numbers.

Hemant
  • 19,486
  • 24
  • 91
  • 127