)]}'
{
  "commit": "c00ea1103d58eaf542b0b83a1f558819e59c4a7d",
  "tree": "a402050d8c9fb40dc20c2d3aa35a527b7f975c84",
  "parents": [
    "05fe9245c35f8f28e69ae964d65680e7f352e08b"
  ],
  "author": {
    "name": "Devin Jeanpierre",
    "email": "jeanpierreda@google.com",
    "time": "Mon Dec 07 17:01:14 2020 -0800"
  },
  "committer": {
    "name": "GitHub",
    "email": "noreply@github.com",
    "time": "Mon Dec 07 17:01:14 2020 -0800"
  },
  "message": "More clearly define randomness in timing_array.h\n\nThis is a Linear Congruential Generator. See e.g. https://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine and compare the formula ;)  i.e. we\u0027re basically reimplementing `std::linear_congruential_engine\u003c113, 100, 256\u003e`\r\n\r\nThis is an important observation, because it implies further restrictions on the number 113 -- it shouldn\u0027t just be odd, but in fact *prime* (or at least co-prime with the modulus), and 112 needs to satisfy several tests (in particular, divisible by 2 and 4, but not 8). This also informs us how we can extend this to arbitrary sizes rather than 256.\r\n\r\nThe most obvious next step, if we want to reuse this for non-256-sized arrays, is to make it a PCG over the next-biggest sized power of 2 (and step the PCG until an in-range value is found). Alternatively, any other PRNG that supports O(1) seek and can have its period set arbitrarily small would suffice.\r\n\r\nI\u0027m not sure what these are called in computer science -- in math, it\u0027s just called a permutation. As in, I want a permutation over the integers 0..n -- a bijection from 0..n to 0..n. But if I google for permutation functions, I get algorithms for shuffling vectors instead of int-\u003eint permutations. :/",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "73ee752e3bbf95349a85f541ee7a1bd415462d64",
      "old_mode": 33188,
      "old_path": "demos/timing_array.h",
      "new_id": "6a94a2033f78ec22518a9f199b6ba17a84a5e0a9",
      "new_mode": 33188,
      "new_path": "demos/timing_array.h"
    }
  ]
}