Hello all, Is it possible to generate random numbers that are "unique" in O(1) in Haskell? I mean something like the GUID-thingy Windows uses. Of course, I could create unique numbers by incrementing a global value, but for security reasons I need random numbers. Also, I could use a list of numbers already in use, but this would mean that I'd not be able to generate a new number in O(1). Any ideas? Regards, Robert
Hi Robert,
Is it possible to generate random numbers that are "unique" in O(1) in Haskell?
I mean something like the GUID-thingy Windows uses.
Of course, I could create unique numbers by incrementing a global value, but for security reasons I need random numbers. Also, I could use a list of numbers already in use, but this would mean that I'd not be able to generate a new number in O(1).
do you really need random numbers? If not: I vaguely remember an algorithm from one of the "Graphic Gems" books, implementing some sort of fancy counter which goes through all numbers from 0,...,2^n-1 in a seemingly random, but of course deterministic and repeatable order. It was used for some sort of cross dissolve effect, because you can index every pixel of a bitmap with one number (ignoring numbers mapped to positions outside the screen/viewport/whatever) and this way blend from one image to another. If this sort of behavious suits your needs just let me know and I will look it up. Regards, Jens
Hi! Thanks for your answer. However, I think I just stumbled upon a more easy method that does what I need. Namely: generate a random number, increment the global number, make sure the length of the random number is always the same number of digits, and concatenate the two of them :-). Robert
This topic should be posed to a more general forum than GHusers... Jens Fisseler answers:
Is it possible to generate random numbers that are "unique" in O(1) in Haskell?
Of course, I could create unique numbers by incrementing a global value, but for security reasons I need random numbers.
do you really need random numbers? If not: I vaguely remember an algorithm from one of the "Graphic Gems" books, implementing some sort of fancy counter which goes through all numbers from 0,...,2^n-1 in a seemingly random, but of course deterministic and repeatable order.
Actually, decent random number generators, even simple congruential ones: X_{n+1} = A*X_n + C (mod M) if the parameters are chosen correctly, *guarantee* to generate ALL M integers between 0 and M-1 without repetitions, and only then the sequence repeats. Take M sufficiently large, and you are safe, provided you know what you are doing. See Knuth for details, how to choose the params. Another story -- of course -- is the generation of RN in Haskell. Too often, too many people suggest all these horrible manadic devices, while the usage of a simple lazy stream of consecutively generated numbers would suffice... Bon courage. Jerzy Karczmarczuk
Robert van Herk wrote,
Hello all,
Is it possible to generate random numbers that are "unique" in O(1) in Haskell?
I mean something like the GUID-thingy Windows uses.
Of course, I could create unique numbers by incrementing a global value, but for security reasons I need random numbers. Also, I could use a list of numbers already in use, but this would mean that I'd not be able to generate a new number in O(1).
There are standard algorithms for doing this job, and it might be better to use one of them rather than reinventing the wheel. See here, http://www.itu.int/ITU-T/asn1/uuid.html or possibly here, http://www.ietf.org/internet-drafts/draft-mealling-uuid-urn-05.txt Open source implementations in a variety of (imperative) languages and with a variety of licenses are available via google. There's also one in J2SE 5.0. Cheers, Miles
participants (4)
-
Jens Fisseler -
karczma＠info.unicaen.fr -
Miles Sabin -
Robert van Herk