random.nextBool() always returns true

[DartBot]

This issue was originally filed by jjinux...@google.com

---

Every time I run this program, it prints the same value, true:

import "dart:math";

main() {   print(new Random().nextBool()); }

Dart Editor Version 0.1.0.201210010959, build 13075 Dart SDK version 13075

[DartBot]

This comment was originally written by jjinux...@google.com

---

Changed the title to: "random.nextBool() always returns true".

[lrhn]

Seems genuine. Only the first call is always true when run with the 'dart' binary from the SDK. Further calls (e.g., by duplicating the line in "main") give different values on different runs. Ditto if you create the Random object once and calls four times on it - first result is always true, rest may differ.

If you do nextInt(64) instead, the first values differ, but are always odd.

It does not reproduce with the 'dart' I built myself - I get different first values from nextBook().

Are there less bits in the system seed we use to initialize the Random object with than expected?

(All tested on 64-bit Linux)

[lrhn]

Removed Area-Library label. Added Area-VM label.

[iposva-google]

Lasse, can you clarify what you mean by: It does not reproduce with the 'dart' I built myself - I get different first values from nextBook().

Have you changed the Random algorithm? There should be nothing in the algorithm that should change from build to build.

---

Set owner to @iposva-google. Added this to the M2 milestone. Added Accepted label.

[iposva-google]

cc @lrhn. Added NeedsInfo label.

[iposva-google]

JJ, I am not able to reproduce this problem in a current, local VM build. Can you please try to reproduce in your setup with the code below. This should produce 20 random numbers in 20 different isolates, which should be equivalent to launching the same example multiple times:

import "dart:math"; import "dart:isolate";

printNextBool() {   print(new Random().nextBool()); }

main() {   for (var i = 0; i < 20; i++) {     spawnFunction(printNextBool);   } }

[lrhn]

Running the isolate code in the editor, or using the dart binary shipped with the editor, gives 20 times "true". Changing the print line to   print(new Random().nextInt(256).toRadixString(2)); consistently give even numbers (with no other obvious pattern).

A little while later, it starts printing all "false" and all odd numbers.

It seems the Random object is being seeded with something time-specific, and it's not random enough.

This is probably fixed on bleeding_edge! It is broken in the build that comes with the editor (r14167), and if I check out r14166 and build it locally, it has the same problem. If I build locally from tip of bleeding_edge, the problem is not there.

If it was fixed accidentally, it would be good to know what the problem was, so we can avoid regressions.

[lrhn]

A quick bisect tells me that the problem was fixed in r14235, which indeed affected Random.

[DartBot]

This comment was originally written by jjinux...@google.com

---

If it's fixed, we should probably have a test that it stays fixed. For instance, if you run new Random().nextBool() 100 times, you shouldn't get the same answer every time.

[iposva-google]

Regarding comment 9: If you get the same answer every time, then it would not be very random and exactly what this bug initially was about. That the initial value for nextBool() was predictable.

I'll try to answer the questions in comments 7 & 8 after more analysis.

---

Added Accepted label.

[DartBot]

This comment was originally written by jjinux...@google.com

---

Regarding comment 9: If you get the same answer every time, then it would not be very random and exactly what this bug initially was about. That the initial value for nextBool() was predictable.

Yes, that's my point. Did you somehow misread what I wrote?

[iposva-google]

Removed this from the M2 milestone. Added this to the M3 milestone.

[iposva-google]

Removed this from the M3 milestone. Added this to the M4 milestone.

[larsbak]

Removed this from the M4 milestone. Added this to the M5 milestone.

[iposva-google]

Removed Priority-Medium label. Added Priority-Unassigned label.

[iposva-google]

Will be adding a testcase along these lines:

import "dart:math"; import "dart:isolate"; import "package:expect/expect.dart";

isolateMain() {   port.receive((_, reply) {     // Calculate a random coin toss and send it back.     var value = new Random().nextBool();     reply.send(value);     port.close();   }); }

main() {   var outstanding = 100;   var heads = 0;   var tails = 0;

  port.receive((value, reply) {     if (value) {       heads++;     } else {       tails++;     }     if (--outstanding > 0) {       // Need more samples, spawn another isolate.       spawnFunction(isolateMain).send(0, port);     } else {       // All samples collected. Verify result and shutdown the main isolate.       print("Heads: $heads\n"             "Tails: $tails\n"             "Ratio: ${heads/tails}\n");       Expect.approxEquals(1.0, heads/tails, 0.3);       port.close();     }   });

  // Start the initial isolate, which will trigger the remaining isolates being   // created until we have a large enough sample.   spawnFunction(isolateMain).send(0, port); }

[iposva-google]

Removed this from the M5 milestone.

[lrhn]

The test allows heads/tails to be in the range 0.7 .. 1.3 [1]. This would fail for 57 heads and 43 tails (or 41 heads, 59 tails, see [1]).

The standard deviation for the expected (binomial) distribution of 100 throws of a fair coin is 5, so this is within 2 times the deviation, and the test is expected to fail in up to 5% of runs, even with a completely fair random implementation. I would mark such a test as flaky.

I would reduce it to something like being outside of 6 standard distributions (expected to fail about 2 times in a billion runs).

That would be:   Expect.isTrue((heads-50).abs() < 30); // The current value is ~10.

If we increase N to 1000, the standard deviation becomes ~16, so we can do:   Expect.isTrue((heads-500).abs() < 96);

Increasing N might be counter-productive as a regression test, though. The original random generator was streaky in time, so increasing the count would increase the likelyhood that the test would overlap more than one streak and hide the problem.

How about counting alternations (where two following results are different). I don't know the distribution of that off-hand (but I'd wager that it's also binomial), and it would catch a long streaks of ones followed by an equally long streaks of zero, where just counting heads and tails won't.

[1] That range isn't symmetric in heads and tails. A better range would be 1/1.3 .. 1.3. The Expect.approxEquals is meant to be used for precision, not testing fractions.

[iposva-google]

Lasse, here is a slightly revised version which takes your analysis into account and also verifies for long streaks;

import "dart:math"; import "dart:isolate"; import "package:expect/expect.dart";

isolateMain() {   port.receive((_, reply) {     // Calculate a random coin toss and send it back.     var value = new Random().nextBool();     reply.send(value);     port.close();   }); }

main() {   var outstanding = 100;   var heads = 0;   var tails = 0;   var transitions = 0;   var previous = null;

  port.receive((value, reply) {     if (value) {       heads++;     } else {       tails++;     }     if ((previous != null) && (previous != value)) {       transitions++;     }     previous = value;

    if (--outstanding > 0) {       // Need more samples, spawn another isolate.       spawnFunction(isolateMain).send(0, port);     } else {       // All samples collected. Verify result and shutdown the main isolate.       print("Heads: $heads\n"             "Tails: $tails\n"             "Ratio: ${heads/tails}\n"             "Transitions: $transitions\n");       Expect.isTrue((heads-50).abs() < 30); //       Expect.isTrue(transitions > 30); // Avoid streaks.       port.close();     }   });

  // Start the initial isolate, which will trigger the remaining isolates being   // created until we have a large enough sample.   spawnFunction(isolateMain).send(0, port); }