3 ms·

> `random % alphabet` is a popular mistake to make when coding an ID generator. The spread will not be even; there will be a lower chance for some symbols to ap

> `random % alphabet` is a popular mistake to make when coding an ID generator. The spread will not be even; there will be a lower chance for some symbols to appear compared to others—so it will reduce the number of tries when brute-forcing. I don't understand: is the default implementation of random in node.js flawed? Surely it should produce a uniform distribution… edit nevermind, found the link to https://gist.github.com/joepie91/7105003c3b26e65efcea63f3db82dfba https://gist.github.com/joepie91/7105003c3b26e65efcea63f3db8... just above that paragraph

jimktrains2 9y ago
0,1,2,3,4 % 3 0 => 0 1 => 1 2 => 2 3 => 0 4 => 1 So, a uniform input will produce more 0s and 1s than it will 2s.
- heavenlyblue 9y ago
  Only if the alphabet size is not a multiple of two.
  - jimktrains2 9y ago
    More generally, only if your input is an integer multiple of your alphabet. However, there are methods of converting uniform distributions that will preserve uniformity. I'll have to find a good reference.
    - heavenlyblue 9y ago
      Well, it's obvious for me. Issue is that the root reply seemed to have taken it as a JS implementation issue (due to math.random) as it's quite obvious why you should not do the modulus (or when you can), if you know the underlying maths. So did I, as a matter of fact. You - on the other hand had given the answer to the wrong confusion.
      - AndrewCHM 9y ago
        they could of responded, "no, random is uniform" (the answer to the written question) and that wouldn't of answered anything!
      - falsedan 9y ago
        > Issue is that the root reply seemed to have taken it as a JS implementation issue I'm the root reply. jimktrains2's explanation exactly addressed my confusion. To get a uniform distribution over an alphabet from random, I would do: var bucket_size = (random.MAX_VALUE - random.MIN_VALUE) / count(alphabet) return alphabet[random/bucket_size]
        jimktrains2 9y ago
        Actually, that doesn't work either max = 4, min = 0, count = 3 bucket_size = 4 / 3 0,1,2,3,4 0 / (4/3) = 0 1 / (4/3) = 3/4 = 0 2 / (4/3) = 6/3 = 2 3 / (4/3) = 9/4 = 2 4 / (4/3) = 12/4 = 3 = invalid index but even if you adjust this to count - 1 bucket_size = 4 / 2 = 2 0 = 0/2 = 0 1 = 1/2 = 0 2 = 2/2 = 1 3 = 3/2 = 1 4 = 4/2 = 2 So, 0s and 1s are still more likely than 2 to appear. One of the easiest, and slowest, ways is just to discard any trial in which your uniform RNG generates a number above the largest index and try again. For a larger alphabet, you essentially just collect multiple trials, treat them as a single trial, and do similar tactics.
        falsedan 9y ago
        > bucket_size = 4 / 3 I have an off-by-one error… your random function has a range of 5, so it should be max - min + 1: bucket_size = 5 / 3 then 0 / (5/3) = 0 1 / (5/3) = 3/5 = 0 2 / (5/3) = 6/5 = 1 3 / (5/3) = 9/5 = 1 4 / (5/3) = 12/5 = 2 > So, 0s and 1s are still more likely than 2 to appear. Yeah, I planned for 65535 randoms and 52 alphabet. It would still mildly bias to the first range mod alphabet_size elements.

jimktrains2 9y ago

0,1,2,3,4 % 3 0 => 0 1 => 1 2 => 2 3 => 0 4 => 1 So, a uniform input will produce more 0s and 1s than it will 2s.

heavenlyblue 9y ago
Only if the alphabet size is not a multiple of two.
- jimktrains2 9y ago
  More generally, only if your input is an integer multiple of your alphabet. However, there are methods of converting uniform distributions that will preserve uniformity. I'll have to find a good reference.
  - heavenlyblue 9y ago
    Well, it's obvious for me. Issue is that the root reply seemed to have taken it as a JS implementation issue (due to math.random) as it's quite obvious why you should not do the modulus (or when you can), if you know the underlying maths. So did I, as a matter of fact. You - on the other hand had given the answer to the wrong confusion.
    - AndrewCHM 9y ago
      they could of responded, "no, random is uniform" (the answer to the written question) and that wouldn't of answered anything!
    - falsedan 9y ago
      > Issue is that the root reply seemed to have taken it as a JS implementation issue I'm the root reply. jimktrains2's explanation exactly addressed my confusion. To get a uniform distribution over an alphabet from random, I would do: var bucket_size = (random.MAX_VALUE - random.MIN_VALUE) / count(alphabet) return alphabet[random/bucket_size]
      - jimktrains2 9y ago
        Actually, that doesn't work either max = 4, min = 0, count = 3 bucket_size = 4 / 3 0,1,2,3,4 0 / (4/3) = 0 1 / (4/3) = 3/4 = 0 2 / (4/3) = 6/3 = 2 3 / (4/3) = 9/4 = 2 4 / (4/3) = 12/4 = 3 = invalid index but even if you adjust this to count - 1 bucket_size = 4 / 2 = 2 0 = 0/2 = 0 1 = 1/2 = 0 2 = 2/2 = 1 3 = 3/2 = 1 4 = 4/2 = 2 So, 0s and 1s are still more likely than 2 to appear. One of the easiest, and slowest, ways is just to discard any trial in which your uniform RNG generates a number above the largest index and try again. For a larger alphabet, you essentially just collect multiple trials, treat them as a single trial, and do similar tactics.
        falsedan 9y ago
        > bucket_size = 4 / 3 I have an off-by-one error… your random function has a range of 5, so it should be max - min + 1: bucket_size = 5 / 3 then 0 / (5/3) = 0 1 / (5/3) = 3/5 = 0 2 / (5/3) = 6/5 = 1 3 / (5/3) = 9/5 = 1 4 / (5/3) = 12/5 = 2 > So, 0s and 1s are still more likely than 2 to appear. Yeah, I planned for 65535 randoms and 52 alphabet. It would still mildly bias to the first range mod alphabet_size elements.