On Tue, Apr 22, 2014 at 8:16 PM, Richard Hipp <d...@sqlite.org> wrote: > On Tue, Apr 22, 2014 at 2:06 PM, Dominique Devienne > <ddevie...@gmail.com>wrote: > >> Regarding the uniqueness argument made by DRH, it's actually very hard >> to generate 2 random-based GUIDS [that collide], given that a 128-bit is a >> very very large number. > > This is called the "Birthday Paradox". Ask Google for more information.
Thanks for that Richard. Live and learn ;) > To a good approximation, if there are N possible values, you need to > generate sqrt(N) of them before you have a 50/50 chance of getting a > collision. (Wikipedia has the exact formula, if you are interested, but > the approximation is usually good enough.) > > So for a 128-bit GUID, you'd expect to get a collision after generating 4 > billion of them, or so. Said Google tells me 2^128 - 1 = 3.4028237e+38 and that sqrt(2^128 - 1) = 1.8446744e+19 You've confused a 128-bit with a 64-bit integer in your 4 billion approximation, no? > The above assumes you have a good source of randomness. The "rand()" > function in your favorite programming language is often not quite that > good. But random() in SQLite does a decent job, at last on Unix where it > can be seeded using /dev/random. FWIW, I used the Boost's http://www.boost.org/doc/libs/1_47_0/doc/html/boost/random/mt19937.html for the RNG. --DD _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
