Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 5 | // Flags: --random-seed=20 --nostress-opt --noalways-opt --predictable |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | })(); |