001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.rng.sampling.distribution;
019
020import org.apache.commons.rng.UniformRandomProvider;
021
022/**
023 * Discrete uniform distribution sampler generating values of type {@code long}.
024 *
025 * <p>Sampling uses {@link UniformRandomProvider#nextLong}.</p>
026 *
027 * <p>When the range is a power of two the number of calls is 1 per sample.
028 * Otherwise a rejection algorithm is used to ensure uniformity. In the worst
029 * case scenario where the range spans half the range of a {@code long}
030 * (2<sup>63</sup> + 1) the expected number of calls is 2 per sample.</p>
031 *
032 * @since 1.4
033 */
034public abstract class UniformLongSampler implements SharedStateLongSampler {
035    /** Underlying source of randomness. */
036    protected final UniformRandomProvider rng;
037
038    /**
039     * Discrete uniform distribution sampler when the sample value is fixed.
040     */
041    private static final class FixedUniformLongSampler extends UniformLongSampler {
042        /** The value. */
043        private final long value;
044
045        /**
046         * @param value The value.
047         */
048        FixedUniformLongSampler(long value) {
049            // No requirement for the RNG
050            super(null);
051            this.value = value;
052        }
053
054        @Override
055        public long sample() {
056            return value;
057        }
058
059        @Override
060        public String toString() {
061            // No RNG to include in the string
062            return "Uniform deviate [X=" + value + "]";
063        }
064
065        @Override
066        public UniformLongSampler withUniformRandomProvider(UniformRandomProvider rng) {
067            // No requirement for the RNG
068            return this;
069        }
070    }
071
072    /**
073     * Discrete uniform distribution sampler when the range is a power of 2 and greater than 1.
074     * This sampler assumes the lower bound of the range is 0.
075     *
076     * <p>Note: This cannot be used when the range is 1 (2^0) as the shift would be 64-bits
077     * which is ignored by the shift operator.</p>
078     */
079    private static final class PowerOf2RangeUniformLongSampler extends UniformLongSampler {
080        /** Bit shift to apply to the long sample. */
081        private final int shift;
082
083        /**
084         * @param rng Generator of uniformly distributed random numbers.
085         * @param range Maximum range of the sample (exclusive).
086         * Must be a power of 2 greater than 2^0.
087         */
088        PowerOf2RangeUniformLongSampler(UniformRandomProvider rng,
089                                        long range) {
090            super(rng);
091            this.shift = Long.numberOfLeadingZeros(range) + 1;
092        }
093
094        /**
095         * @param rng Generator of uniformly distributed random numbers.
096         * @param source Source to copy.
097         */
098        PowerOf2RangeUniformLongSampler(UniformRandomProvider rng,
099                                        PowerOf2RangeUniformLongSampler source) {
100            super(rng);
101            this.shift = source.shift;
102        }
103
104        @Override
105        public long sample() {
106            // Use a bit shift to favour the most significant bits.
107            return rng.nextLong() >>> shift;
108        }
109
110        @Override
111        public UniformLongSampler withUniformRandomProvider(UniformRandomProvider rng) {
112            return new PowerOf2RangeUniformLongSampler(rng, this);
113        }
114    }
115
116    /**
117     * Discrete uniform distribution sampler when the range is small
118     * enough to fit in a positive long.
119     * This sampler assumes the lower bound of the range is 0 and the range is
120     * non-zero.
121     */
122    private static final class SmallRangeUniformLongSampler extends UniformLongSampler {
123        /** Maximum range of the sample (exclusive). */
124        private final long n;
125        /** Limit of the uniform range (inclusive) to sample a positive long.
126         * This is the largest positive multiple of {@code n} minus 1:
127         * {@code floor(2^63 / n) * n - 1}.
128         * The -1 changes the limit to an inclusive bound and allows support
129         * for a power of 2 range. */
130        private final long limit;
131
132        /**
133         * @param rng Generator of uniformly distributed random numbers.
134         * @param range Maximum range of the sample (exclusive).
135         */
136        SmallRangeUniformLongSampler(UniformRandomProvider rng,
137                                     long range) {
138            super(rng);
139            this.n = range;
140            // Set the upper limit for the positive long.
141            // The sample must be selected from the largest multiple
142            // of 'range' that fits within a positive value:
143            // limit = floor(2^63 / range) * range
144            //       = 2^63 - (2^63 % range)
145            // Sample:
146            //   X in [0, limit) or X in [0, limit - 1]
147            //   return X % range
148            // This is a one-off computation cost.
149            // The divide will truncate towards zero (do not use Math.floorDiv).
150            // Note: This is invalid if range is not strictly positive.
151            limit = (Long.MIN_VALUE / range) * -range - 1;
152        }
153
154        /**
155         * @param rng Generator of uniformly distributed random numbers.
156         * @param source Source to copy.
157         */
158        SmallRangeUniformLongSampler(UniformRandomProvider rng,
159                                     SmallRangeUniformLongSampler source) {
160            super(rng);
161            this.n = source.n;
162            this.limit = source.limit;
163        }
164
165        @Override
166        public long sample() {
167            // Note:
168            // This will have the same output as the rejection algorithm
169            // from o.a.c.rng.core.BaseProvider. The limit for the uniform
170            // positive value can be pre-computed. This ensures exactly
171            // 1 modulus operation per call.
172            for (;;) {
173                // bits in [0, limit]
174                final long bits = rng.nextLong() >>> 1;
175                if (bits <= limit) {
176                    return bits % n;
177                }
178            }
179        }
180
181        @Override
182        public UniformLongSampler withUniformRandomProvider(UniformRandomProvider rng) {
183            return new SmallRangeUniformLongSampler(rng, this);
184        }
185    }
186
187    /**
188     * Discrete uniform distribution sampler when the range between lower and upper is too large
189     * to fit in a positive long.
190     */
191    private static final class LargeRangeUniformLongSampler extends UniformLongSampler {
192        /** Lower bound. */
193        private final long lower;
194        /** Upper bound. */
195        private final long upper;
196
197        /**
198         * @param rng Generator of uniformly distributed random numbers.
199         * @param lower Lower bound (inclusive) of the distribution.
200         * @param upper Upper bound (inclusive) of the distribution.
201         */
202        LargeRangeUniformLongSampler(UniformRandomProvider rng,
203                                     long lower,
204                                     long upper) {
205            super(rng);
206            this.lower = lower;
207            this.upper = upper;
208        }
209
210        @Override
211        public long sample() {
212            // Use a simple rejection method.
213            // This is used when (upper-lower) >= Long.MAX_VALUE.
214            // This will loop on average 2 times in the worst case scenario
215            // when (upper-lower) == Long.MAX_VALUE.
216            while (true) {
217                final long r = rng.nextLong();
218                if (r >= lower &&
219                    r <= upper) {
220                    return r;
221                }
222            }
223        }
224
225        @Override
226        public UniformLongSampler withUniformRandomProvider(UniformRandomProvider rng) {
227            return new LargeRangeUniformLongSampler(rng, lower, upper);
228        }
229    }
230
231    /**
232     * Adds an offset to an underlying discrete sampler.
233     */
234    private static final class OffsetUniformLongSampler extends UniformLongSampler {
235        /** The offset. */
236        private final long offset;
237        /** The long sampler. */
238        private final UniformLongSampler sampler;
239
240        /**
241         * @param offset The offset for the sample.
242         * @param sampler The discrete sampler.
243         */
244        OffsetUniformLongSampler(long offset,
245                                 UniformLongSampler sampler) {
246            // No requirement for the RNG
247            super(null);
248            this.offset = offset;
249            this.sampler = sampler;
250        }
251
252        @Override
253        public long sample() {
254            return offset + sampler.sample();
255        }
256
257        @Override
258        public String toString() {
259            return sampler.toString();
260        }
261
262        @Override
263        public UniformLongSampler withUniformRandomProvider(UniformRandomProvider rng) {
264            return new OffsetUniformLongSampler(offset, sampler.withUniformRandomProvider(rng));
265        }
266    }
267
268    /**
269     * @param rng Generator of uniformly distributed random numbers.
270     */
271    UniformLongSampler(UniformRandomProvider rng) {
272        this.rng = rng;
273    }
274
275    /** {@inheritDoc} */
276    @Override
277    public String toString() {
278        return "Uniform deviate [" + rng.toString() + "]";
279    }
280
281    /** {@inheritDoc} */
282    // Redeclare the signature to return a UniformLongSampler not a SharedStateLongSampler
283    @Override
284    public abstract UniformLongSampler withUniformRandomProvider(UniformRandomProvider rng);
285
286    /**
287     * Creates a new discrete uniform distribution sampler.
288     *
289     * @param rng Generator of uniformly distributed random numbers.
290     * @param lower Lower bound (inclusive) of the distribution.
291     * @param upper Upper bound (inclusive) of the distribution.
292     * @return the sampler
293     * @throws IllegalArgumentException if {@code lower > upper}.
294     */
295    public static UniformLongSampler of(UniformRandomProvider rng,
296                                        long lower,
297                                        long upper) {
298        if (lower > upper) {
299            throw new IllegalArgumentException(lower  + " > " + upper);
300        }
301
302        // Choose the algorithm depending on the range
303
304        // Edge case for no range.
305        // This must be done first as the methods to handle lower == 0
306        // do not handle upper == 0.
307        if (upper == lower) {
308            return new FixedUniformLongSampler(lower);
309        }
310
311        // Algorithms to ignore the lower bound if it is zero.
312        if (lower == 0) {
313            return createZeroBoundedSampler(rng, upper);
314        }
315
316        final long range = (upper - lower) + 1;
317        // Check power of 2 first to handle range == 2^63.
318        if (isPowerOf2(range)) {
319            return new OffsetUniformLongSampler(lower,
320                                                new PowerOf2RangeUniformLongSampler(rng, range));
321        }
322        if (range <= 0) {
323            // The range is too wide to fit in a positive long (larger
324            // than 2^63); use a simple rejection method.
325            // Note: if range == 0 then the input is [Long.MIN_VALUE, Long.MAX_VALUE].
326            // No specialisation exists for this and it is handled as a large range.
327            return new LargeRangeUniformLongSampler(rng, lower, upper);
328        }
329        // Use a sample from the range added to the lower bound.
330        return new OffsetUniformLongSampler(lower,
331                                            new SmallRangeUniformLongSampler(rng, range));
332    }
333
334    /**
335     * Create a new sampler for the range {@code 0} inclusive to {@code upper} inclusive.
336     *
337     * <p>This can handle any positive {@code upper}.
338     *
339     * @param rng Generator of uniformly distributed random numbers.
340     * @param upper Upper bound (inclusive) of the distribution. Must be positive.
341     * @return the sampler
342     */
343    private static UniformLongSampler createZeroBoundedSampler(UniformRandomProvider rng,
344                                                               long upper) {
345        // Note: Handle any range up to 2^63 (which is negative as a signed
346        // 64-bit long but handled as a power of 2)
347        final long range = upper + 1;
348        return isPowerOf2(range) ?
349            new PowerOf2RangeUniformLongSampler(rng, range) :
350            new SmallRangeUniformLongSampler(rng, range);
351    }
352
353    /**
354     * Checks if the value is a power of 2.
355     *
356     * <p>This returns {@code true} for the value {@code Long.MIN_VALUE} which can be
357     * handled as an unsigned long of 2^63.</p>
358     *
359     * @param value Value.
360     * @return {@code true} if a power of 2
361     */
362    private static boolean isPowerOf2(final long value) {
363        return value != 0 && (value & (value - 1)) == 0;
364    }
365}