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

- Add a math library. Currently it mostly matches the Math class in dart:core.
- Add a useable Random number generator.
Committed: https://code.google.com/p/dart/source/detail?r=7860

[Ivan Posva, 2012-05-15 17:46:27]

Some of this is purely mechanical (adding the dart:math library), other parts
are replicating the existing Math class with only the Random number generator
interface and default implementation being truly new.

The plan is that once this split is in we can massage the dart:math library
interfaces and implementation and deprecate the use of the class Math in
dart:core.

-Ivan

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

Hi Ivane,

I have a bunch of comments for you.

Josh

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart
File lib/math/random.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:12: * semi-open range [0, max).
I'd say this comment (about nextInt) doesn't belong at the class level (but only
at the method level).

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:18: * the random stream can change between releases of the
library.
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?

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:27: */
Might want to say "We anticipate that this constructor will be used primarily
for testing" or some such.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:31: * Generates a random integer in the semi-open range [0,
max). The default
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.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:32: * implementation uses a [max] of ((1<<32) - 1) if no
[max] value is supplied.
I would say "2<sup>32</sup> - 1" rather than "((1<<32) - 1)" because this is
about math, not bitwise manipulation.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:35: double nextDouble();
Presumably you want to document nextDouble and nextBool.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:44: seed = new Date.now().value;
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());
	}
}

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:61: _seed = ((_A * (_seed & _MASK_32)) + (_seed >> 32)) &
_MASK_64;
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).

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:63: return (max == null) ? (_seed & _MASK_32) : ((_seed %
max) & _MASK_32);
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

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:67: return nextInt() / _MASK_32_M1;
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:19]

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart
File lib/math/random.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:12: * semi-open range [0, max).
On 2012/05/15 20:19:17, jjb wrote:
> I'd say this comment (about nextInt) doesn't belong at the class level (but
only
> at the method level).

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

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:18: * the random stream can change between releases of the
library.
On 2012/05/15 20:19:17, jjb wrote:
> 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?

Done.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:27: */
On 2012/05/15 20:19:17, jjb wrote:
> Might want to say "We anticipate that this constructor will be used primarily
> for testing" or some such.

Done.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:31: * Generates a random integer in the semi-open range [0,
max). The default
On 2012/05/15 20:19:17, jjb wrote:
> 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.

Done.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:44: seed = new Date.now().value;
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:
> 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();
> 	 &nbsp; &nbsp;for (int i = 0; i < 100; i++)
> 	 &nbsp; &nbsp; &nbsp; &nbsp;s.add(randomInteger());
> 	 &nbsp; &nbsp;System.out.println(s.size());
> 	}
> 
> 	private static Integer randomInteger() {
> 	 &nbsp; &nbsp;return new Integer(new Random().nextInt());
> 	}
> }

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:63: return (max == null) ? (_seed & _MASK_32) : ((_seed %
max) & _MASK_32);
On 2012/05/15 20:19:17, jjb wrote:
> 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
> 

Done.

https://chromiumcodereview.appspot.com/10389150/diff/1/lib/math/random.dart#n...
lib/math/random.dart:67: return nextInt() / _MASK_32_M1;
On 2012/05/15 20:19:17, jjb wrote:
> 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).

Done.

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

DBC. (I'm pretty sure you would have found that one alone though...)

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dart
File lib/math/random.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:95: return ((nextInt(1 << (26)) << 27) + nextInt(1 << 27))
/ _POW2_53;
_POW2_53_D

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

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dart
File lib/math/random.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:21: // TODO(iposva): Do we really need this?
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.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:72: 
As per previous comment, I'd really like to see a reference for this PRNG in the
comment.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:79: // TODO(iposva): Check incoming arguments.
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.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:80: if ((max & -max) == max) {
Might want to put in a comment saying that this special-cases powers of two;
it's a bit esoteric.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:94: // TODO(iposva): Handle 53-bits of value.
Can remove TODO, right?  You are handling 53 bits.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:109: var _seed;
This field should be called _state rather than seed; it starts out as the seed,
but becomes the state.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:118: return _prng._seed;
Presumably the space between prng. and seed should be an underscore?

[Ivan Posva, 2012-05-16 22:54:33]

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dart
File lib/math/random.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:21: // TODO(iposva): Do we really need this?
On 2012/05/16 21:50:10, jjb wrote:
> 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.

Removed.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:72: 
On 2012/05/16 21:50:10, jjb wrote:
> As per previous comment, I'd really like to see a reference for this PRNG in
the
> comment.

Done.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:79: // TODO(iposva): Check incoming arguments.
On 2012/05/16 21:50:10, jjb wrote:
> 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.

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

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:80: if ((max & -max) == max) {
On 2012/05/16 21:50:10, jjb wrote:
> Might want to put in a comment saying that this special-cases powers of two;
> it's a bit esoteric.

Done.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:94: // TODO(iposva): Handle 53-bits of value.
On 2012/05/16 21:50:10, jjb wrote:
> Can remove TODO, right?  You are handling 53 bits.

Done.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:95: return ((nextInt(1 << (26)) << 27) + nextInt(1 << 27))
/ _POW2_53;
On 2012/05/16 20:40:22, floitsch wrote:
> _POW2_53_D
That's what I get for not rerunning tests before uploading. Fixed.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:109: var _seed;
On 2012/05/16 21:50:10, jjb wrote:
> This field should be called _state rather than seed; it starts out as the
seed,
> but becomes the state.

Done.

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/random.dar...
lib/math/random.dart:118: return _prng._seed;
On 2012/05/16 21:50:10, jjb wrote:
> Presumably the space between prng. and seed should be an underscore?
Looks like an underscore to me.

[jjb, 2012-05-17 00:59:10]

lgtm

[Ben Laurie (Google), 2012-05-21 10:48:09]

Is there a reason not to make the PRNG cryptographically strong?

[Ivan Posva, 2012-05-21 15:12:17]

On 2012/05/21 10:48:09, Ben Laurie (Google) wrote:
> Is there a reason not to make the PRNG cryptographically strong?

Efficiency. The crypto library should be supplying a good implementation of this
interface.

-Ivan

[kasperl, 2012-05-23 12:40:46]

Sorry for being so slow, but this LGTM with a few trivial comments:

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/math.dart
File lib/math/math.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/8001/lib/math/math.dart#...
lib/math/math.dart:1: #library("math");
This should have a copyright header too.

https://chromiumcodereview.appspot.com/10389150/diff/8001/tests/lib/math/low_...
File tests/lib/math/low_test.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/8001/tests/lib/math/low_...
tests/lib/math/low_test.dart:29: print("$low, $diff");
Debug printing?

https://chromiumcodereview.appspot.com/10389150/diff/8001/tests/lib/math/pi_t...
File tests/lib/math/pi_test.dart (right):

https://chromiumcodereview.appspot.com/10389150/diff/8001/tests/lib/math/pi_t...
tests/lib/math/pi_test.dart:28: print("$pie");
Debug printing?

[ahe, 2013-04-18 10:12:43]

https://chromiumcodereview.appspot.com/10389150/diff/17001/tests/lib/lib.status
File tests/lib/lib.status (right):

https://chromiumcodereview.appspot.com/10389150/diff/17001/tests/lib/lib.stat...
tests/lib/lib.status:9: math/*: Skip
Should these tests run in dart2js now?

[floitsch, 2013-05-04 22:54:04]

Found this in my inbox...
A little bit late, but this still applies.

https://chromiumcodereview.appspot.com/10389150/diff/17001/tests/lib/lib.status
File tests/lib/lib.status (right):

https://chromiumcodereview.appspot.com/10389150/diff/17001/tests/lib/lib.stat...
tests/lib/lib.status:9: math/*: Skip
On 2013/04/18 10:12:43, ahe wrote:
> Should these tests run in dart2js now?
Hmm. probably they should.
Currently 5 of the 8 tests pass.