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

lib/math/random.dart

Index: lib/math/random.dart
===================================================================
--- lib/math/random.dart	(revision 0)
+++ lib/math/random.dart	(revision 0)
@@ -0,0 +1,122 @@
+// 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.
+ */
+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.
+   *
+   * Implementation note: The default implementation uses up to 64-bits of seed.
+   */
+  Random([int seed]);
+
+  // TODO(iposva): Do we really need this?

[jjb, 2012/05/16 21:50:10]

No; when in doubt, leave it out.  Upon reflection, I believe it encourages
people to write bad tests. Sorry I told you to put it in.

[Ivan Posva, 2012/05/16 22:54:34]

Removed.

+  /**
+   * 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.
+   *
+   * We anticipate that this random-number generator will be primarily used in
+   * testing.
+   */
+  Random.stable([int seed]);
+
+  /** 
+   * Generates a positive random integer uniformly distributed on the range
+   * from 0, inclusive, to [max], exclusive.
+   *
+   * Implementation note: The default implementation supports [max] values
+   * between 1 and ((1<<32) - 1) inclusive.
+   */
+  int nextInt(int max);
+
+  /** 
+   * Generates a positive random floating point value uniformly distributed on
+   * the range from 0.0, inclusive, to 1.0, exclusive.
+   */
+  double nextDouble();
+
+  /** 
+   * Generates a random boolean value.
+   */
+  bool nextBool();
+}
+
+class _Random implements Random {
+
+  _Random([int seed = null]) {
+    if (seed == null) {
+      seed = _nextSeed();
+    }
+    do {
+      seed = (seed + 0x5A17) & _MASK_64;
+    } while (seed == 0);
+    _seed = seed;
+  }
+
+  factory _Random.stable([int seed = null]) {
+    if (seed == null) {
+      // Nothing up my sleeve: Default seed value is the code review id.
+      seed = 10389150;
+    }
+    return new _Random(seed);
+  }
+

[jjb, 2012/05/16 21:50:10]

As per previous comment, I'd really like to see a reference for this PRNG in the
comment.

[Ivan Posva, 2012/05/16 22:54:34]

Done.

+  int _nextInt32() {
+    _seed = ((_A * (_seed & _MASK_32)) + (_seed >> 32)) & _MASK_64;
+    return _seed & _MASK_32;
+  }
+
+  int nextInt(int max) {
+    // TODO(iposva): Check incoming arguments.

[jjb, 2012/05/16 21:50:10]

For now, wouldn't it be sufficient to say:

    if (max <= 0 || max > _POW2_32)
      throw new IlegalArumentException("max must be positive and < 2^32: $max");

or some such?  Longer term, I do think it makes sense to support larger moduli
(max-values), and it's not all that hard: just figure out how many 32-bit chunks
you need, jam them together, and proceed.

[Ivan Posva, 2012/05/16 22:54:34]

Added the check. Adding bits together eventually makes total sense.

+    if ((max & -max) == max) {

[jjb, 2012/05/16 21:50:10]

Might want to put in a comment saying that this special-cases powers of two;
it's a bit esoteric.

[Ivan Posva, 2012/05/16 22:54:34]

Done.

+      return _nextInt32() & (max - 1);
+    }
+    
+    var rnd32;
+    var result;
+    do {
+      rnd32 = _nextInt32();
+      result = rnd32 % max;
+    } while (rnd32 - result + max >= _POW2_32);
+    return result;
+  }
+
+  double nextDouble() {
+    // TODO(iposva): Handle 53-bits of value.

[jjb, 2012/05/16 21:50:10]

Can remove TODO, right?  You are handling 53 bits.

[Ivan Posva, 2012/05/16 22:54:34]

Done.

+    return ((nextInt(1 << (26)) << 27) + nextInt(1 << 27)) / _POW2_53;

[floitsch, 2012/05/16 20:40:22]

_POW2_53_D

[Ivan Posva, 2012/05/16 22:54:34]

That's what I get for not rerunning tests before uploading. Fixed.

+  }
+
+  bool nextBool() {
+    return nextInt(1) == 0;
+  }
+
+  static final _MASK_32 = (1 << 32) - 1;
+  static final _MASK_64 = (1 << 64) - 1;
+  static final _POW2_32 = 1 << 32;
+  static final _POW2_53_D = 1.0 * (1 << 53);
+
+  static final _A = 0xffffda61;
+
+  var _seed;

[jjb, 2012/05/16 21:50:10]

This field should be called _state rather than seed; it starts out as the seed,
but becomes the state.

[Ivan Posva, 2012/05/16 22:54:34]

Done.

+
+  int _nextSeed() {
+    if (_prng == null) {
+      // TODO(iposva): Use system to get a random seed.
+      _prng = new _Random(new Date.now().value);
+    }
+    // Trigger the PRNG once to change the internal state.
+    _prng._nextInt32();
+    return _prng._seed;

[jjb, 2012/05/16 21:50:10]

Presumably the space between prng. and seed should be an underscore?

[Ivan Posva, 2012/05/16 22:54:34]

Looks like an underscore to me.

+  }
+
+  static var _prng = null;
+}