Timeline for Prove that an expression can create duplicate
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 14, 2022 at 17:21 | history | edited | Ewan | CC BY-SA 4.0 |
added 158 characters in body
|
| Jul 14, 2022 at 17:09 | history | edited | Ewan | CC BY-SA 4.0 |
added 11 characters in body
|
| Jul 14, 2022 at 14:27 | vote | accept | Felice Pollano | ||
| Jul 13, 2022 at 8:56 | comment | added | Ralf Kleberhoff |
+1 It's quite plausible to treat the ms value as a random value, independent of i. And then the math is correct.
|
|
| Jul 12, 2022 at 22:40 | comment | added | Ewan | you would only hit 1b without a repeat if all the first 1m were xxxxxx000, the second 1m were xxxxxx001 etc | |
| Jul 12, 2022 at 22:32 | comment | added | Ewan | so 1,000,002 has a 1/1000 chance, 1,000,003 has a 1/1000 chance... etc by 1,000,693 you have had to be lucky for none of those chances to come up | |
| Jul 12, 2022 at 22:20 | comment | added | Philip Kendall | Pretty sure your maths is wrong here. There is zero chance that the 1,000,002nd invocation collides with anything other than the 2nd invocation, because it has the form 000002xxx and the only previous invocation with that pattern was the 2nd invocation. It's 1,000,000 separate buckets each of size 1,000, so starting to get a reasonable chance of a collision when there are sqrt(1000) = 33 or so in each bucket, or 33M invocations. Still less than 1B but much more than 1,000,693. | |
| Jul 12, 2022 at 22:00 | history | answered | Ewan | CC BY-SA 4.0 |