nextInt is not uniform

[Quijx]

nextInt(n) does not generate uniform random numbers for larger n.

The issue is with the following line:

xrandom_dart/lib/src/21_base32.dart

Line 88 in 8b4b47b

for (int u = r; u - (r = u % max) + m < 0; u = nextRaw32()) {}

If I'm not mistaken the line should be for (int u = r; u - (r = u % max) + max > (1 << 32); u = nextRaw32()) {}. Not sure what the point of m = max-1 is, but i don't think its needed.

Since u % max is always <= u, u-(u%max) is never negative. And since m is also never negative, u-(r=u%max)+m will never be less than 0. So essentially only nextRaw32() % max will every be returned. This is approximately uniform for small m but for larger m, it is not. This can easily experimentally be verified.

The following program prints lower: 6665204, upper: 3334796 even though there should be approximately an equal amout of numers below the midpoint as above.

import 'package:xrandom/xrandom.dart';

void main() {
  final random = Xrandom(42);

  const mid = (1 << 32) ~/ 3;
  const max = mid * 2;
  var lower = 0;
  var upper = 0;
  for (var i = 0; i < 10000000; i++) {
    if (random.nextInt(max) < mid) {
      lower++;
    } else {
      upper++;
    }
  }
  print('lower: $lower, upper: $upper');
}

[rtmigo]

Thanks for pointing this out. Indeed there was a problem.

It seemed to happen for all max exceeding the range of a signed int32 (for max from 1<<31 to 1<<32).

As a quick fix, I patched this method with the standard algorithm from the Dart SDK. And also added tests with a uniformity check for a given range of max.