Google – Implement Rand6 by Rand2

Google – Implement Rand6 by Rand2
Rand6() return a random number in [0, 6)
Rand2() return a random number in [0, 2)
用Rand2()来实现Rand6()

[Solution]
思路分为两步：
1.第一步要解决如何用rand2()来算其他的，比如rand3, rand4, rand5。
因为我们只能用rand2()，所以无非就是对rand2()进行加减乘除来得到randK. 但是不要天真的以为

rand4() = 2 * rand2(), 因为2 * [0, 2) = [0, 4)。 错！！

请问上面的式子中，2 * rand2()如何得到 3？
正确的rand4()应该等于2 * rand2() + rand2(), 但是这个范围可不是[0, 6)，而就是[0, 4).
2.第二步就是要保证等概率。
通过上面的分析，如果现在问要计算rand6()怎么算，可能看着上面现学现卖就会出现这样的回答:

rand6() = 2 * rand4() + rand4() 又错！！

这个方法有两个问题:
(1). 范围实际超过了[0, 6), 变成了[0, 9)
(2). 算一下会发现有两种不同的方法可以得到 4， 比如2 * 2 + 0或者2 * 1 + 2。而只有一种方法可以得到 1，就是2 * 0 + 1。
这样就说明[0, 9)之间每个数并不是等概率的。事实上范围超过[0, 6)并不是大问题，只要保证每个数都是等概率，如果random到678，丢掉继续random就是了，直到random出[0, 6)之间的。
关键是第二个问题，如何得到等概率。
我们可以证明下面的公式

I * randN + randI 得到的范围 [0, N * I) 内所有的数，都是evenly distributed

[0, I), randN = 0
[I, 2I), randN = 1
[2I, 3I), randN = 2
…
[kI, (k+1)I), randN = k
上面每个区间内的每个数都只有一种方法可以得到。
现在再来看rand6()怎么实现的话，就能得到以下两种方法：

rand6() = 2 * rand4() + rand2()
rand6() = 4 * rand4() + rand4()

不过还有一点需要注意，我们只有rand2()可以用，rand4()需要通过rand2()来计算，而上面第二种方法两个rand4()不是同一个数喔，要通过rand2()计算两次，得到两个不同的rand4()。

class Solution {

  public int rand6() {

    while (true) {

      int rand4 = 2 * rand2() + rand2();

      int result = 2 * rand4 + rand2();

      if (result < 6) {

        return result;

      }

    }

  }

}

 

class Solution2 {

  public int rand6() {

    while (true) {

      int rand4_1 = 2 * rand2() + rand2();

      int rand4_2 = 2 * rand2() + rand2();

      int result = 4 * rand4_1 + rand4_2;

      if (result < 12) {

        return result % 6;

      }

    }

  }

}

Read full article from Google – Implement Rand6 by Rand2