News for hackers. Stuff that matters.
Re:Nano ID: A tiny, secure URL-friendly unique string ID ge... by heavenlyblue on Tuesday September 12, 2017 @08:56AM (#15226868)
Only if the alphabet size is not a multiple of two.
Re:Nano ID: A tiny, secure URL-friendly unique string ID ge... by jimktrains2 on Tuesday September 12, 2017 @09:31AM (#15227104)
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.

Re:Nano ID: A tiny, secure URL-friendly unique string ID ge... by heavenlyblue on Tuesday September 12, 2017 @10:49AM (#15227695)
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.

Re:Nano ID: A tiny, secure URL-friendly unique string ID ge... by falsedan on Tuesday September 12, 2017 @11:41AM (#15228195)
> 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]
Re:Nano ID: A tiny, secure URL-friendly unique string ID ge... by jimktrains2 on Tuesday September 12, 2017 @11:53AM (#15228312)
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.

Re:Nano ID: A tiny, secure URL-friendly unique string ID ge... by falsedan on Wednesday September 13, 2017 @07:51AM (#15237349)
> 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.

Re:Nano ID: A tiny, secure URL-friendly unique string ID ge... by AndrewCHM on Tuesday September 12, 2017 @11:26AM (#15228042)
they could of responded, "no, random is uniform" (the answer to the written question) and that wouldn't of answered anything!