-
Notifications
You must be signed in to change notification settings - Fork 39
/
solution_45.py
25 lines (20 loc) · 864 Bytes
/
solution_45.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def coding_problem_45(rand5):
"""
Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability,
implement a function rand7() that returns an integer from 1 to 7 (inclusive).
>>> from random import randint
>>> rand5 = lambda: randint(0, 4)
>>> rand7 = coding_problem_45(rand5)
>>> 0 <= rand7 < 7
True
Note: for n >= 24, rand5() ** n is a multiple of 7 and therefore rand5() ** 24 % 7 is an unbiased implementation
of rand7(). To avoid having to rely on big integer libraries, we use the property (a + b) % n == ((a % n) + b) % n
which is easy to prove by decomposing a into a // n * n + a % n.
"""
rand7 = 0
for _ in range(24):
rand7 = (rand7 * 5 + rand5()) % 7
return rand7
if __name__ == '__main__':
import doctest
doctest.testmod(verbose=True)