1// Copyright 2015 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Flags: --random-seed=12 --nostress-opt --noalways-opt --predictable
6
7(function() {
8  var kHistory = 2;
9  var kRepeats = 100;
10  var history = new Uint32Array(kHistory);
11
12  function random() {
13    return (Math.random() * Math.pow(2, 32)) >>> 0;
14  }
15
16  function ChiSquared(m, n) {
17    var ys_minus_np1 = (m - n / 2.0);
18    var chi_squared_1 = ys_minus_np1 * ys_minus_np1 * 2.0 / n;
19    var ys_minus_np2 = ((n - m) - n / 2.0);
20    var chi_squared_2 = ys_minus_np2 * ys_minus_np2 * 2.0 / n;
21    return chi_squared_1 + chi_squared_2;
22  }
23  for (var predictor_bit = -2; predictor_bit < 32; predictor_bit++) {
24    // The predicted bit is one of the bits from the PRNG.
25    for (var random_bit = 0; random_bit < 32; random_bit++) {
26      for (var ago = 0; ago < kHistory; ago++) {
27        // We don't want to check whether each bit predicts itself.
28        if (ago == 0 && predictor_bit == random_bit) continue;
29        // Enter the new random value into the history
30        for (var i = ago; i >= 0; i--) {
31          history[i] = random();
32        }
33        // Find out how many of the bits are the same as the prediction bit.
34        var m = 0;
35        for (var i = 0; i < kRepeats; i++) {
36          for (var j = ago - 1; j >= 0; j--) history[j + 1] = history[j];
37          history[0] = random();
38          var predicted;
39          if (predictor_bit >= 0) {
40            predicted = (history[ago] >> predictor_bit) & 1;
41          } else {
42            predicted = predictor_bit == -2 ? 0 : 1;
43          }
44          var bit = (history[0] >> random_bit) & 1;
45          if (bit == predicted) m++;
46        }
47        // Chi squared analysis for k = 2 (2, states: same/not-same) and one
48        // degree of freedom (k - 1).
49        var chi_squared = ChiSquared(m, kRepeats);
50        if (chi_squared > 24) {
51          var percent = Math.floor(m * 100.0 / kRepeats);
52          if (predictor_bit < 0) {
53            var bit_value = predictor_bit == -2 ? 0 : 1;
54            print(`Bit ${random_bit} is ${bit_value} ${percent}% of the time`);
55          } else {
56            print(`Bit ${random_bit} is the same as bit ${predictor_bit} ` +
57              `${ago} ago ${percent}% of the time`);
58          }
59        }
60        // For 1 degree of freedom this corresponds to 1 in a million.  We are
61        // running ~8000 tests, so that would be surprising.
62        assertTrue(chi_squared <= 24);
63        // If the predictor bit is a fixed 0 or 1 then it makes no sense to
64        // repeat the test with a different age.
65        if (predictor_bit < 0) break;
66      }
67    }
68  }
69})();
70