- Add a math library. Currently it mostly matches the Math class in dart:core.

lib/math/random.dart

+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// A part of the dart:math library.
+
+/**
+ * A random number generator. The default implementation supplies a stream of
+ * pseudo-random bits which is not suitable for cryptographic purposes.
+ *
+ * The basic function nextInt([int max]) generates a random integer in the
+ * semi-open range [0, max).

[jjb, 2012/05/15 20:19:17]

I'd say this comment (about nextInt) doesn't belong at the class level (but only
at the method level).

[Ivan Posva, 2012/05/16 00:13:20]

I'll rely on you cleaning up the comments in another go.

+ */
+interface Random default _Random {
+  /** 
+   * Creates a random-number generator. The optional parameter [seed] is used
+   * to initialize the internal state of the generator. The implementation of
+   * the random stream can change between releases of the library.

[jjb, 2012/05/15 20:19:17]

Each implementation (including the default) should specify how many bits of the
seed it actually uses. I would do this via an "implementation note" if it may
change in a subsequent release. I notice that for this implementation, it's only
32 bits.  That can't be enough!  (Only 4 billion sequences.)  How about 64 bits?

[Ivan Posva, 2012/05/16 00:13:20]

Done.

+   */
+  Random([int seed]);
+
+  // TODO(iposva): Do we really need this?
+  /**
+   * Creates a random-number generator which does not change between releases.
+   * This random-number generator is potentially not as fast as the default
+   * implementation, but it allows creating repeatable random-number sequences.
+   */

[jjb, 2012/05/15 20:19:17]

Might want to say "We anticipate that this constructor will be used primarily
for testing" or some such.

[Ivan Posva, 2012/05/16 00:13:20]

Done.

+  Random.stable([int seed]);
+
+  /** 
+   * Generates a random integer in the semi-open range [0, max). The default

[jjb, 2012/05/15 20:19:17]

The phrase should be "half-open" rather than "semi-open."  (Google backs me up
by a margin of 4,000 :) Alternatively, you could say "a positive random integer
uniformly distributed on the range from 0, inclusive, to max, exclusive." I
believe this would be understandable to more people.

[Ivan Posva, 2012/05/16 00:13:20]

Done.

+   * implementation uses a [max] of ((1<<32) - 1) if no [max] value is supplied.

[jjb, 2012/05/15 20:19:17]

I would say "2<sup>32</sup> - 1" rather than "((1<<32) - 1)" because this is
about math, not bitwise manipulation.

+   */
+  int nextInt([int max]);
+  double nextDouble();

[jjb, 2012/05/15 20:19:17]

Presumably you want to document nextDouble and nextBool.

+  bool nextBool();
+}
+
+class _Random implements Random {
+
+  _Random([int seed = null]) {
+    if (seed == null) {
+      // TODO(iposva): Use system to get a random seed.
+      seed = new Date.now().value;

[jjb, 2012/05/15 20:19:17]

I would save the last seed used in a static variable, and add one to if the new
one is the same as the last one.  Otherwise, you'll suffer from this Java
Puzzler (which was fixed in 2004):

2.1. “Random Behavior”
public class RandomSet {
	public static void main(String[] args) {
	    Set s = new HashSet();
	    for (int i = 0; i < 100; i++)
	        s.add(randomInteger());
	    System.out.println(s.size());
	}

	private static Integer randomInteger() {
	    return new Integer(new Random().nextInt());
	}
}

[Ivan Posva, 2012/05/16 00:13:20]

Fixed as we had discussed previously. Use a per-isolate PRNG to get the initial
seed values. The TODO just moved to the initialization of that per-isolate PRNG.

On 2012/05/15 20:19:17, jjb wrote:

+    }
+    do {
+      seed = (seed + 0x5A17) & _MASK_32;
+    } while (seed == 0);
+    _seed = seed;
+  }
+
+  factory _Random.stable([int seed = null]) {
+    if (seed == null) {
+      // If no seed is set use a predefined value.
+      seed = 103055;
+    }
+    return new _Random(seed);
+  }
+
+  int nextInt([int max = null]) {
+    _seed = ((_A * (_seed & _MASK_32)) + (_seed >> 32)) & _MASK_64;

[jjb, 2012/05/15 20:19:17]

Please put a reference (URL, literature, or whatever) to the RNG in a comment. 
In fact, I'd put it in a publicly visible comment, as an "implementation note"
(i.e., we reserve the right to change it, but let you know what you're getting,
as of this release).

+    // TODO(iposva): Fix handling of max.
+    return (max == null) ? (_seed & _MASK_32) : ((_seed % max) & _MASK_32);

[jjb, 2012/05/15 20:19:17]

Why are you doing the & after the %? And shouldn't you to validity testing on
max, as well as specify what the valid values are? I would seriously consider
making this method support arbitrary positive values of max (using multiple
calls to the underlying 32-bit PRNG if need be). 

Also, as we discussed, the code falls prey to this puzzler:

public static void main(String[] args) {
    int n = 2 * (Integer.MAX_VALUE / 3);
    int low = 0;
    for (int i = 0; i < 1000000; i++)
        if (random(n) < n/2)
            low++;

    System.out.println(low);
}

You might expect it to print ~500,000, but it actually prints ~666,666

To fix is I recommend code like this:
     int rndInt32;
     int result;
     do {
         rndInt = nextInt32();
         result = rndInt32 % max;
     } while(rndInt32 - result + max >= (1 << 32));
     return result;

Two things you might want to do:

(1) You might eliminate the default value on the parameter of nextInt, and make
nextInt32 public.

(2) You might make a special case for max a power of 2:

    if ((max  & -max) == max) // max is a power of 2
        return nextInt() & (max - 1);

Of course the above code assumes that 0 < max < 2^32

[Ivan Posva, 2012/05/16 00:13:20]

Done.

+  }
+
+  double nextDouble() {
+    return nextInt() / _MASK_32_M1;

[jjb, 2012/05/15 20:19:17]

Use 53 bits instead of 32 (the precision of the float.  Also, the mask should be
the power of two, not the power of two - 2 (i.e., 1 << 53).

[Ivan Posva, 2012/05/16 00:13:20]

Done.

+  }
+
+  bool nextBool() {
+    return (nextInt() & 1) == 0;
+  }
+
+  static final _MASK_32 = 0xffffffff;
+  static final _MASK_32_M1 = _MASK_32 - 1;
+  static final _MASK_64 = 0xffffffffffffffff;
+  static final _A = 0xffffda61;
+  var _seed;  
+}