3 ms·
I'm not sure, but let me guess. It looks like most browsers are using xorshift128+ https://johnkavanagh.co.uk/writing/javascripts-math-random/ https://johnkavan
by gus_massa 3y ago
I'm not sure, but let me guess. It looks like most browsers are using xorshift128+ https://johnkavanagh.co.uk/writing/javascripts-math-random/ https://johnkavanagh.co.uk/writing/javascripts-math-random/ that has a result of 64 bits, that is scaled to the interval 0 .. 1. By the birthday paradox you need the square root and almost an additional bit, so let's say 33 bits. That is like 8.000.000.000 tries to get a collision. Assuming the table uses 4 bytes per float, you need 32GB of ram to store it. It's probably too much for a normal computer, but not impossible.
Actually, the float point numbers use 1 bit for the sign, 11 for the exponent and 52 for the digits. Here you are not using the sign, and the exponent is between -1 and -64, so it's only 6 bits. Instead of a random number of 64 bits, you get only 52+6=58. Again, using the birthday paradox you need only 2^30 that is only 1.000.000.000 and 4GB of memory.
Actually, the distribution of representables floating point numbers is not uniform and half of the floats you will get are between .5 and 1. In that range, you only have 52 bits because the exponent is always fixed. Again, using the birthday paradox you need only 2^27.
But half of the time you will get a number between 0 and .5. The collisions in that range are harder, so let's ignore them. So you need 2^28, i.e, 2.500.000.000 tries and 1GB. If you don't ignore the small numbers, it should be slightly faster, perhaps like a 30% faster.
If you run the code, I'd love to see some results to know how good/bad is my approximation. In particular my guess is that 70% of the times you will get the first collision with a number between .5 an 1, and 30% of the time with a number between 0 and .5.