2
$\begingroup$

Here, $n$ could be a few hundreds, or even thousands, so it is not possible to pregenerate a list of $$\{0, 1, \dots, 2^n-1\}$$ and shuffle it. Because it is traversal, no number should be visited twice. I want the process of generating the next number as fast as possible.

I was trying to use LCG, but it was too slow ($O(n^2)$) to generate the next number. Linear feedback shift register (LFSR) might be a choice in terms of efficiency ($O(n)$), but I cannot ensure the LFSR always in maximum repeating period for arbitrary $n$. Is there any way to achieve this job effectively?

Improve this question
$\endgroup$
  • $\begingroup$ Why not just use a good standard random number generator? Also, why must your RNG produce $n$ bits at a time, you could just use a standard 64-bit RNG to fill $n$ bits using $\lceil \frac{n}{64}\rceil$ 64-bit numbers? Is there a particular reason you're asking such a specific question? It might be easier to answer if there was more context. (See also The X-Y problem.) $\endgroup$ – Kirill Oct 15 '17 at 19:47
  • 2
    $\begingroup$ What is random order? Here an algorithm which is simple, may be you can use it: Let $m=2^n-1$ and $p$ a random prime $<m$ which does not devide $m$. Iterate $x_{n+1} = (x_n +p) \bmod m$. Here an example for $n=5$ with $p=13:$ $[19, 1, 14, 27, 9, 22, 4, 17, 30, 12, 25, 7, 20, 2, 15, 28, 10, 23, 5, 18, 0, 13, 26, 8, 21, 3, 16, 29, 11, 24, 6, 19]$ $\endgroup$ – gammatester Oct 15 '17 at 20:09
  • 1
    $\begingroup$ Very relevant, posted less than one month ago: lemire.me/blog/2017/09/18/… $\endgroup$ – Federico Poloni Oct 16 '17 at 6:51
  • $\begingroup$ The OP of this Question posed a closely related one the day before. $\endgroup$ – hardmath Oct 17 '17 at 1:52
  • $\begingroup$ @hardmath Yes. Random traversal is the initial problem I tried to solve. That question was after I implement the LCG and noticed some weird behaviors. $\endgroup$ – user62783 Oct 17 '17 at 7:30
5
$\begingroup$

A random number generator will give you random numbers that you can tweak to be between zero and 2^n and consequently it will allow you to sample random locations in your interval. These numbers may, in principle, repeat themselves -- so they are not a traversal, but that may not matter for the following reason:

  • If $n$ is large (in the thousands), you will not be able to visit all numbers in the interval of interest anyway. For example, for $n=1000$, there are $2^{1000}\approx 10^{100}$ integers in this interval, but on a single processor you will at the very most be able to visit about $10^9$ per second -- so $10^{100}$ is out of the question.

  • If you really used a random order, there is no way you could even store which numbers you have already visited.

Consequently, there is little actual difference between a random order, or using the first few billion or trillion elements of an actual (non-repeating) permutation.

Improve this answer
$\endgroup$
  • $\begingroup$ To be clear, I think this is the right answer (or at least the basis of it, because appropriate behaviour needs to be defined for small values of $n$ as well). I added my answer after this one was not accepted, because I thought the question might be purely academic. $\endgroup$ – sh1 Oct 19 '17 at 5:35
1
$\begingroup$

Use a trivial $n$-bit counter, and encrypt it using a block cipher in any configuration other than ECB or CTR, starting with the least-significant bits as your first block so the small change propagates to all the other bits of the result.

If $n$ is not divisible by the size of your block cipher then you'll need to treat the remainder using format-preserving encryption, because the output must be the same size as the input.

This gives you your new index.

If you have the means to decrypt the counter then you can trivially prove that this sequence visits every value exactly once: if any two input states mapped to the same output then you would not be able to decrypt the counter and the encryption itself would be demonstrably broken.

One caveat is that if you jump ahead in the sequence by, eg., $2^{256}$ (presumed to be a multiple of your block cipher size), then the first $2^{256}$ bits of the encrypted count would not change. If you're not happy with this then reverse the order of the bits and encrypt it a second time. Still O(n), but a little more complicated.

Obviously cryptographic primitives aren't a great way to speed things up, but it shows how to make things linear. If you take that construction but replace the block cipher with something more economical (eg., a 64-bit perfect hash) then you can recover a lot of that lost performance.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.