Daniel Lemire's blog

, 3 min read

Benchmarking algorithms to visit all values in an array in random order

5 thoughts on “Benchmarking algorithms to visit all values in an array in random order”

  1. Sean O'Connor says:

    https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Additive_recurrence

  2. Max says:

    “and we set prime to be an adequately chosen random number that is coprime with n and not too small.”
    Fun fact: So how to count down?
    Choose start value to be 0 and the coprime to be n-1.

  3. CamelCoder says:

    Isn’t it possible to create an LCG with the modulo of n?
    That would only cost one more multiplication and have the same time complexity that the additive method, whiles having way higher quality randomness. The initialization times are worse, though that should be benchmarked separately, as one can reuse the a constant and only compute new values for c to visit if the array length stays the same.

    I wanted to try this my self, but your code seems to be not quite right:

    static uint32_t productOfAllPrimeDivisors(uint32_t val) {
    uint32_t pot = 2;
    uint32_t answer = 1;
    while ((uint64_t)pot <= val / 2) {
    if (IsPrime(pot)) { // but pot is never modified
    answer *= pot;
    while ((val % pot) == 0) {
    val /= pot;
    }
    }
    }
    return answer;
    }

    1. Daniel Lemire says:

      Isn’t it possible to create an LCG with the modulo of n?

      Yes but I expect you will find that it is slower.

  4. Simon Labrecque says:

    That’s awesome. Thanks!