Nano ID: A tiny, secure URL-friendly unique string ID generator for JavaScript

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.

[ Parent | on HN ]

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.

[ Parent | on HN ]