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}