0

I'm trying to understand one aspect of a secure shuffle using Fisher-Yates. For reference, here is Fisher-Yates to shuffle an array x of n elements (numbered from 0 to n-1) (from Securing a Shuffle Algorithm):

for all i from 0 to n-1
    let j = rnd(n - i) + i
    swap x[i] with x[j]

I don't quite understand what Tom Leeks is getting at in his explanation of the rnd function at Securing a Shuffle Algorithm:

rnd(k):
    while true
        let z = next-random-word
        let r = z mod k
        if z - r + k <= 2^32
            return r

Why can't r be used directly, and why is the if z - r + k <= 2^32 needed?

I think my problem is I don't appreciate on understand the bias in the reduction.

2

The check is to ensure that skew doesn't occur. If your random number generator has a range of 0 to 9, and you simply take a straight modulus, you'll end up with the following outputs:

0 % 6 = 0
1 % 6 = 1
2 % 6 = 2
3 % 6 = 3
4 % 6 = 4
5 % 6 = 5
6 % 6 = 0
7 % 6 = 1
8 % 6 = 2
9 % 6 = 3

This leads to the values 4 and 5 being less common than 0, 1, 2, or 4.

The algorithm Tom gave ensures that the range of the raw RNG values is limited to a range that is evenly divisible by the output range.

So, let's say we want a range of values from 0 to 15. That's a total range of 16. Our internal RNG outputs values between 0 and 100, which would lead to skew like above. The design of the algorithm rejects values larger than or equal to 96 (because it's the largest number less than 100 that's divisible by 16) because those values would lead to skew.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.