1 /*
2 * License : The MIT License
3 * Copyright(c) 2022 Olyutorskii
4 */
5
6 package io.github.olyutorskii.aletojio;
7
8 import io.github.olyutorskii.aletojio.rng.RndInt32;
9 import java.util.Objects;
10
11 /**
12 * Bounded random integer value {@code [0,bound)} generator.
13 *
14 * <p>Random source is {@link RndInt32}.
15 *
16 * <p>This implementation uses a fast algorithm(Nearly Divisionless)
17 * that does not use a division(/) or remainder(%) but bitmask and right-shift.
18 *
19 * <p>Modulo bias removal may consume multiple 32-bit random numbers per one output.
20 *
21 * @see <a href="https://arxiv.org/abs/1805.10941">Fast Random Integer Generation in an Interval (arXiv)</a>
22 * @see <a href="https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/">
23 * Nearly Divisionless Random Integer Generation On Various Systems
24 * </a>
25 */
26 public class BoundRnd {
27
28 private static final String ERRMSG_BOUND = "too small bound";
29
30 private static final long RNDCAR = 1L << Integer.SIZE;
31 private static final long MASK_I32 = (1L << Integer.SIZE) - 1;
32
33
34 private final RndInt32 rnd;
35 private final long bound;
36 private final long judge2nd;
37
38
39 /**
40 * Constructor for [0,N) bounded random number.
41 *
42 * <p>N is upper bound(exclusive).
43 *
44 * @param rnd 32bit random number generator
45 * @param bound upper bound(exclusive) must be 2 or more
46 * @throws NullPointerException argument is null
47 * @throws IllegalArgumentException toosmall bound
48 */
49 public BoundRnd(RndInt32 rnd, int bound) throws IllegalArgumentException {
50 super();
51
52 Objects.requireNonNull(rnd);
53 if (bound < 2) throw new IllegalArgumentException(ERRMSG_BOUND);
54
55 this.rnd = rnd;
56 this.bound = bound;
57 this.judge2nd = RNDCAR % this.bound; // = (RNDCAR - bound) % bound
58
59 assert this.bound > this.judge2nd;
60
61 return;
62 }
63
64
65 /**
66 * Return sparce random number.
67 *
68 * <p>unsigned 32bit random number * bound.
69 *
70 * @return sparce random number
71 */
72 private long sparceRnd() {
73 int r32 = this.rnd.nextInt32();
74 long r64 = Integer.toUnsignedLong(r32);
75 long result = r64 * this.bound;
76 return result;
77 }
78
79 /**
80 * Return next bounded random number.
81 *
82 * @return [0, bound) random number
83 */
84 public int next() {
85 long mul64;
86 long low32;
87
88 mul64 = sparceRnd();
89 low32 = mul64 & MASK_I32;
90
91 if (low32 < this.bound) {
92 final long limit2nd = this.judge2nd;
93 while (low32 < limit2nd) {
94 mul64 = sparceRnd();
95 low32 = mul64 & MASK_I32;
96 }
97 }
98
99 int high32 = (int) (mul64 >>> Integer.SIZE);
100 return high32;
101 }
102
103 }