rtmigo / xrandom_dart

Dart library with random number generators focused on the consistency, performance and reproducibility

xrandom

Classes implementing all-purpose, rock-solid random number generators.

Library priorities:

• generation of identical bit-accurate numbers regardless of the platform
• reproducibility of the random results in the future
• high-quality randomness
• performance

---

It has the same API as the standard Random

import 'package:xrandom/xrandom.dart';

final random = Xrandom();

var a = random.nextBool(); 
var b = random.nextDouble();
var c = random.nextInt(n);

var unordered = [1, 2, 3, 4, 5]..shuffle(random);

Creating the object

The library provides classes that differ in the first letter: Xrandom, Qrandom, Drandom.

If you just want a random number:

final random = Xrandom();

quoteOfTheDay = quotes[ random.nextInt(quotes.length) ];

If you want the same numbers each time:

final random = Drandom(); // D is for Dumb Determinism 

test("no surprises ever", () {
    expect(random.nextInt(100), 42);
    expect(random.nextInt(100), 17);
    expect(random.nextInt(100), 96);
});

If you are solving a computational problem:

final random = Qrandom(); // Q is for Quantifiable Quality

feedMonteCarloSimulation(random);

If you prefer a specific algorithm:

final random = Splitmix64(); // see list of algorithms below

feedMonteCarloSimulation(random);

Speed

Generating random numbers with AOT-compiled binary.

Sorted by nextInt fastest to slowest (numbers show execution time)

Class	nextInt	nextDouble	nextBool
Xrandom	627	640	391
Random (dart:math)	895	929	662
Qrandom / Drandom	933	1219	398

Additions to Random

nextFloat

nextFloat() generates a floating-point value in the range 0.0 ≤ x <1.0.

Unlike the nextDouble, nextFloat prefers speed to precision. It's still a double, but it has four billion shades instead of eight quadrillions.

Speed comparison

Sorted by nextDouble fastest to slowest (numbers show execution time)

JS	Class	nextDouble	nextFloat
	Xorshift64	569	353
	Xorshift128p	635	389
✓	Xrandom	640	221
	Splitmix64	658	398
✓	Xorshift128	815	339
	Mulberry32	841	301
✓	Random (dart:math)	929
	Xoshiro256pp	1182	713
✓	Qrandom / Drandom	1219	539

nextRaw

These methods return the raw output of the generator uncompromisingly fast. Depending on the algorithm, the output is a number consisting of either 32 random bits or 64 random bits.

Xrandom combines small integers or splits large ones. The methods work with any of the generators.

JS	Method	Returns	Equivalent of
✓	nextRaw32()	32-bit unsigned	nextInt(pow(2,32))
✓	nextRaw53()	53-bit unsigned	nextInt(pow(2,53))
	nextRaw64()	64-bit signed	nextInt(pow(2,64))

Speed comparison

Sorted by nextInt fastest to slowest
(numbers show execution time)

JS	Class	nextInt	nextRaw32	nextRaw64
✓	Xrandom	627	280	549
✓	Xorshift128	726	341	782
	Xorshift64	748	346	491
	Mulberry32	767	307	709
	Xorshift128p	772	383	529
	Splitmix64	838	398	500
✓	Random (dart:math)	895
✓	XrandomHq	933	537	1186
	Xoshiro256pp	1138	703	1072

Since nextInt's return range is always limited to 32 bits, only comparison to nextRaw32 is "apples-to-apples".

Algorithms

Native	JS	Class	Algorithm	Introduced	Alias
✓	✓	Xorshift32	xorshift32	2003	Xrandom
✓		Xorshift64	xorshift64	2003
✓	✓	Xorshift128	xorshift128	2003
✓		Splitmix64	splitmix64	2015
✓		Xorshift128p	xorshift128+ v2	2015
✓		Mulberry32	mulberry32	2017
✓		Xoshiro256ss	xoshiro256** 1.0	2018
✓	✓	Xoshiro128pp	xoshiro128++ 1.0	2019	Qrandom, Drandom
✓		Xoshiro256pp	xoshiro256++ 1.0	2019

You can use any generator from the library in the same way as in the examples with the Xrandom class.

final random = Mulberry32();

quoteOfTheDay = quotes[ random.nextInt(quotes.length) ];

Compatibility

TL;DR Xrandom, Qrandom, Drandom work on all platforms. Others may not work on JS.

The library is written in pure Dart. Therefore, it works wherever Dart works.

But some of the classes need full support for 64-bit integers. JavaScript* actually only supports 53 bits. If your target platform is JavaScript, then the selection will have to be narrowed down to the options marked with [✓] checkmark in the JS column. Trying to create a incompatible object in JavaScript-transpiled code will lead to UnsupportedError.

If your code compiles to native (like in Flutter apps for Android and iOS*), 64-bit* generators will work best for you. For example, Xorshift64 for speed or Xoshiro256pp for quality.

More benchmarks

nextInt fastest to slowest (numbers show execution time)

JS	Class	nextInt	nextDouble	nextBool
✓	Xrandom	627	640	391
✓	Xorshift128	726	815	394
	Xorshift64	748	569	386
	Mulberry32	767	841	391
	Xorshift128p	772	635	394
	Splitmix64	838	658	392
✓	Random (dart:math)	895	929	662
✓	Qrandom / Drandom	933	1219	398
	Xoshiro256pp	1138	1182	406

All the benchmarks on this page are from AOT-compiled binaries running on AMD A9-9420e with Ubuntu 20.04. Time is measured in milliseconds.

The tables are created using the tabular library.

Consistency

The library has been thoroughly tested to match reference numbers generated by the same algorithms implemented in C++. Not only ints, but also numbers converted to double including all decimal places that the compiler takes into account.

The sources in C are taken directly from scientific publications or the reference implementations by the authors of the algorithms. The Xorshift128+ results are also matched to reference values from JavaScript xorshift library, which tested the 128+ similarly.

Therefore, the sequence generated for example by the Xoshiro128pp.nextRaw32() with the seed (1, 2, 3, 4) is the same as the C99 code will produce with the same seed.

The double values will also be the same as if the upper bits of uint64_t type were converted to double_t in C99 by unsafe pointer casting. No matter how exotic pointer casting sounds for Dart, and even more so for JavaScript. JavaScript doesn't even have any upper bits of uint64_t. But doubles are the same type everywhere, and their random values will be the same.

Testing is done in the GitHub Actions cloud on Windows, Ubuntu, and macOS in VM and Node.js modes.

xrandom_dart's Issues

Add Xoshiro256StarStar

Hello

Could you please add xoshiro256ss pseudorandom generator?
https://xoshiro.di.unimi.it/xoshiro256starstar.c

I understand it is mostly reusing xoshiro256pp but with a slight change.

Thank you in advance!

Limit for max in nextInt should be 2^31 inclusive, not exclusive

If nextInt(1 << 32) is called on Xrandom() a RangeError is thrown. The same call on the dart Random() works fine because the limit for max is defined as 1 << 32 inclusively. The generated values will of course be in the range from 0 (inclusive) to 1 << 32 exclusive, so exactly 32 random bits.

The Problem is in the lines:

xrandom_dart/lib/src/21_base32.dart

Lines 83 to 84 in 8b4b47b

	if (max < 1 || max > 0xFFFFFFFF) {
	throw RangeError.range(max, 1, 0xFFFFFFFF);

nextInt is not uniform

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');
}

Int is not a true 64 bit - other type needed

Hello

The four seed parameters defined for Xoshiro256ss are int each.
However, in dart the int type is only 2^63-1 max value, because 1 bit is used for defining the sign (https://stackoverflow.com/a/53591126/346488).
Which means int is not a proper type to use as an input, as it is not possible to pass each part as a true 64-bit integer.

E.g. I have an issue passing one as:
int.parse('f78207dec08eba34', radix:16)
It returns an error:
[ERROR:flutter/lib/ui/ui_dart_state.cc(209)] Unhandled Exception: FormatException: Positive input exceeds the limit of integer

It looks like the right approach would be to use BigInt as input parameters type and then check inside that each parameter is within 64 bits.

Could you please check on this?
Thank you!